Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Ac

MAGIC SQUARES, ROOK POLYNOMIALS AND PERMUTATIONS

FANJA RAKOTONDRAJAO

Abstract. We study in this paper the set of magic squares and their relation with some restricted permutations. Résumé. Nous étudions dans cet article l’ensemble des carrés magiques et leur relation avec des permutations spéciales.

1. Introduction

The oldest magic square ( \begin{matrix}4 & 9 & 2 \\ 3 & 5 & 7 \\ 8 & 1 & 6 \end{matrix} ) first appeared in ancient Chinese literature under the name Lo Shu two thousands years BC. The reader is likely to have encountered such objects, which following Ehrhart [2] are referred to as historical magic squares. These are square matrices of order n whose entries are nonnegative integers {1, …, n^{2}} and whose rows and columns and the main diagonals sum up to the same number, which is called the magic sum. MacMahon [7] and Stanley [10] defined magic squares in modern combinatorics as square matrices of order n whose entries are nonnegative integers and whose rows and columns sum up to the same number, which is called the line sum. In this paper we will study the magic squares following the next definition.

Definition 1.1. A magic square is a square matrix of order n, whose entries are nonnegative integers and the sum of each row, each column and both the main diagonals adds up to the same number, which is called the magic sum.

Example 1.2. ( \begin{matrix}3 & 6 & 0 \\ 0 & 3 & 6 \\ 6 & 0 & 3 \end{matrix} ) is a magic square of order 3 and whose magic sum is equal to 9.

MacMahon [7] has already enumerated the number of all magic squares of order 3 in 1915, and it was not until 2002 that Ahmed et al. [1] could find the number of magic squares of order 4 for a given magic sum. The number of magic squares of order n ≥ 5 with magic sum s ≥ 2 is a challenge! We will introduce notions on magic permutations, which are generators of all magic squares. In 1879, Hertzsprung [5] defined the number of magic permutations as well as the number of permutations without fixed points and without reflected points, well before the development of rook theory ([3], [4], [8], [11]) as a method for enumeration of permutations with restricted positions. Riordan [8] in 1958 and Simpson [9] in 1995 recalled these recurrence relations. We will use weighted rook polynomials to generalize the results on generalized restricted permutations and we will give an unexpected relation which relates derangements and restricted permutations. We will denote by MS_{n} the set of magic squares of order n.

Key words and phrases. Magic squares, magic sum, magic permutations, rook polynomial.

The author was supported by the International Science Programme during her stay at the Mittag-Leffler Institute, Sweden in March 2005.

2. Magic permutations

We will recall the following definitions:

Definition 2.1. A permutation σ of order n is a bijection over n objects.

We will denote by [n] the set {1, …, n}, and by 𝔖_{n} the set of all permutations over [n].

Definition 2.2. We say that an integer i is a fixed point for the permutation σ if σ(i) = i.

Definition 2.3. We say that an integer i is a reflected point for the permutation σ if σ(i) = n − i + 1.

We will denote by Fix(σ) the set of the fixed points of the permutation σ, and by Rfl(σ) the set of its reflected points.

Definition 2.4. We say that an integer i is a pivot point if i is a fixed reflected point.

Remark 2.5. If n is even, no permutation of length n has a pivot point.

Remark 2.6. The only pivot point of a permutation of length n is the integer

\frac{n + 1}{2} if n is odd.

Example 2.7. For the permutation σ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 6 & 5 & 4 & 2 & 7 & 3 \end{matrix} ), we have

Fix(σ) = {1, 4} and Rfl(σ) = {2, 3, 4} .

We will write a permutation σ of length n as a square matrix of order n such that the i-th column is represented by the vector column e_{σ(i)} where

e_{1} = (1 0 ⋮ 0) , e_{2} = (0 1 ⋮ 0) , …, e_{n−1} = (0 ⋮ 1 0) and e_{n} = (0 ⋮ 0 1) .

Example 2.8. If we consider the permutation in Example 2.7, we have:

σ = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix} )

Remark 2.9. The reflected points and the fixed points of a permutation σ are shown in the matrix representation of the permutation σ as the occurrence of the integer 1 on the main diagonals.

Definition 2.10. A magic permutation is a permutation σ whose matrix representation is a magic square of magic sum 1.

Proposition 2.11. A permutation σ is magic if σ has one fixed point and one reflected point.

Example 2.12. The following permutations σ_{1} and σ_{2} of length 9 are magic:

σ_{1} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 2 & 5 & 6 & 8 & 1 & 4 & 9 & 7 \end{matrix} )

and

σ_{2} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 4 & 9 & 7 & 5 & 1 & 8 & 3 & 6 \end{matrix} )

Proposition 2.13. There does not exist a magic permutation of length n for n = 2, 3.

Proposition 2.14. If a permutation σ is magic, then:

(1) σ^{−1} is magic,

(2) the reflected permutation σ′ of the permutation σ, defined by σ′(i) = n − σ(i) + 1, is magic.

Proof. Notice that a fixed point of the permutation σ remains a fixed point for σ^{−1} and becomes a reflected point for the reflected permutation σ′ and viceversa. Notice also that if the integer i is a reflected point for the permutation σ, then the integer i is a fixed point for the reflected permutation σ′ and the integer n − i + 1 is a reflected point for σ^{−1} and vice-versa. □

If we denote by a_{n} and x_{n} the number of magic permutations and the number of permutations without fixed points and without reflected points of length n respectively, we can find in the following table the first values of these numbers:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ a_{n} & 0 & 1 & 0 & 0 & 8 & 20 & 96 & 656 & 5568 \\ x_{n} & 1 & 0 & 0 & 0 & 4 & 16 & 80 & 672 & 4752 \end{matrix}

Hertzsprung [5] established the following theorem:

Theorem 2.15. The numbers a_{n} and x_{n} satisfy the following recurrences:

a_{2n} = n(x_{2n} − (2n − 3)x_{2n−1})
a_{2n+1} = (2n + 1)x_{2n} + 3nx_{2n−1} − 2n(n − 1)x_{2n−2},
x_{n} = (n − 1)x_{n−1} + 2(n − d)x_{n−e},

where (d, e) = (2, 4) if n is even, (1, 2) if n is odd.

We will generalize the theory of rook polynomials to enumerate some restricted permutations.

3. Rook polynomials

We will study in this section the number of permutations σ ∈ 𝔖_{n} where for each i, certain values of σ(i) are disallowed (namely, σ(i) ≠ i and σ(i) ≠ n − i + 1). We have a board 𝔅 ⊂ [n] × [n]. Each square s on 𝔅 has a weight ω_{s}. We define the rook numbers (actually polynomials) of 𝔅 by

r_{k} = ∑_{|A|=k} ∏_{s∈A} ω_{s}

where the sum is over all subsets A ⊂ 𝔅 of cardinality k with no two squares on the same row or column. We define the generalized hit numbers h_{i}:

h_{k} = ∑_{π} ω(π)

where the sum is over all permutations π of [n] with k hits (values of i such that (i, π(i)) ∈ 𝔅) and the weight ω(π) of the permutation π is the products ∏_{i=1}^{n} ω_{(i,π(i))} where ω_{(i,π(i))} is the weight of the square (i, π(i)) if (i, π(i)) ∈ 𝔅 and is 1 otherwise. The generalized hit polynomial is

H = ∑_{k} h_{k}.

We can find a relation between the hit polynomial H and the rook numbers r_{i} just as in the usual case. We claim that

H^{+} = ∑_{k} r_{k}(n − k)!  (⋆)

where H^{+} is the result of replacing each weight ω_{s} for the square s ∈ 𝔅 with ω_{s} + 1. To see this, note that r_{k}(n − k)! counts pairs (A, π) where A is a rook placement in 𝔅 of size k, and π extends A to a permutation of [n]. If we fix π and sum over all possible rook placement A, we are summing over all of the subsets of the hits of A and this gives H^{+}. If we replace each weight ω_{s} in (⋆) by ω_{s} − 1 we get

H = ∑_{k} r_{k}^{−}(n − k)!

where r_{k}^{−} is the result of replacing each ω_{s} with ω_{s} − 1.

Theorem 3.1 (The first main result). Let n = 2m and let 𝔅 the following board with weights as indicated. (This is the case n = 6)

\begin{aligned}α & & & & & β \\ & α & & & β \\ & & α & β \\ & & β & α \\ & β & & & α \\ β & & & & & α \end{aligned}

By permuting the rows and columns we get

\begin{aligned}α & β \\ β & α \\ & & α & β \\ & & β & α \\ & & & & α & β \\ & & & & β & α \end{aligned}

We see that

∑_{k} r_{k}X^{k} = [1 + (2α + 2β)X + (α^{2} + β^{2})X^{2}]^{m} ,

so

∑_{k} r_{k}^{−}X^{k} = [1 + (2α + 2β − 4)X + ((α − 1)^{2} + (β − 1)^{2})X^{2}]^{m} ,  (⋆⋆)

∑_{k} r_{k}^{−}x^{k} = [1 + (2α + 2β − 4)x + ((α − 1)^{2} + (β − 1)^{2})x^{2}]^{m} and therefore we obtain the hit polynomial H = ∑_{k} r_{k}^{−}(n − k)! with r_{k}^{−} as above.

Theorem 3.2. The number x_{2m} of permutations in the symmetric group 𝔖_{2m} without reflected points and without fixed points is given by the formula

x_{2m} = ∑_{k} r_{k}^{−}(2m − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

∑_{k} r_{k}^{−}X^{k} = (1 − 4X + 2X^{2})^{m}.

Proof. To count permutations with no reflected points and no fixed points, we set α = β = 0 in the equation (⋆⋆) to get

∑_{k} r_{k}^{−}X^{k} = (1 − 4X + 2X^{2})^{m},

and we obtain the result. □

Theorem 3.3. The number a_{2m} of permutations of the symmetric group 𝔖_{2m} having one reflected point and one fixed point is given by the formula:

a_{2m} = ∑_{k} r_{k}^{−}(2m − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

4m(m − 1)X^{2}(1 − X)^{2}(1 − 4X + 2X^{2})^{m−2}.

Proof. To count permutations with one reflected point and one fixed point we look at the coefficient of αβ in the equation (⋆⋆). So we want the coefficient of αβ in

[1 + (2α + 2β − 4)X + ((α − 1)^{2} + (β − 1)^{2})X^{2}]^{m}

which is easily computed to be

4m(m − 1)X^{2}(1 − X)^{2}(1 − 4X + 2X^{2})^{m−2}.

And this gives the result. □

Theorem 3.4. The number of permutations of the symmetric group 𝔖_{2m} with no reflected points and one fixed point is given by the formula:

∑_{k} r_{k}^{−}(2m − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

2mX(1 − X)(1 − 4X + 2X^{2})^{m−1}.

Proof. To count permutations with no reflected points and one fixed point we set β = 0 in the equation (⋆⋆) and look at the coefficient of α. So we want the coefficient of α in

[1 + (2α − 4)X + ((α − 1)^{2} + 1)X^{2}]^{m}

which is easily computed to be

2mX(1 − X)(1 − 4X + 2X^{2})^{m−1}

and this gives the result. □

Theorem 3.5. The number of permutations in the symmetric group 𝔖_{2m} with two fixed points without reflected points is given by the formula:

∑_{k} r_{k}^{−}(2m − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

(2m^{2} − m − 4m^{2}X + 2m^{2}X^{2})X^{2}(1 − 4X + 2X^{2})^{m−2}.

Proof. To count permutations with two fixed points without reflected points, we look at the coefficient of α^{2} in the equation (⋆⋆) which is easily computed to be

2m(m − 1)X^{2}(1 − X)^{2}(1 − 4X + 2X^{2})^{m−2} + mX^{2}(1 − 4X + 2X^{2})^{m−1}

= (2m^{2} − m − 4m^{2}X + 2m^{2}X^{2})X^{2}(1 − 4X + 2X^{2})^{m−2}.
□

Theorem 3.6 (The second main result). For n odd we take the following board where we have a separate weight for the middle square

α  β
α  β
γ
β  α
β  α

By permuting the rows and columns we get

\begin{aligned}α & β \\ β & α \\ & & α & β \\ & & β & α \\ & & & & γ \end{aligned}

We see that

∑_{k} r_{k}X^{k} = (1 + γX) [1 + (2α + 2β)X + (α^{2} + β^{2})X^{2}]^{m} ,

so

∑_{k} r_{k}^{−}X^{k} = (1+(γ −1)X) [1 + (2α + 2β − 4)X + ((α − 1)^{2} + (β − 1)^{2})X^{2}]^{m} ,

(⋆ ⋆ ⋆)

and therefore H = ∑_{k} r_{k}^{−}(n − k)! with r_{k}^{−} as above and n = 2m + 1.

Theorem 3.7. The number x_{2m+1} of permutations in the symmetric group 𝔖_{2m+1} without fixed points and without reflected points is given by the formula

∑_{k} r_{k}^{−}(2m + 1 − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

(1 − X)(1 − 4X + 2X^{2})^{m}.

Proof. To count permutations with no reflected points and no fixed points, we set α = β = γ = 0 in the equation (⋆ ⋆ ⋆) to get

∑_{k} r_{k}^{−}X^{k} = (1 − X)(1 − 4X + 2X^{2})^{m}

and

x_{2m+1} = ∑_{k} r_{k}^{−}(2m + 1 − k)!.

□

Theorem 3.8. The number of permutations in the symmetric group 𝔖_{2m+1} with no reflected points and one fixed point is given by the formula:

∑_{k} r_{k}^{−}(2m + 1 − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

2mX(1 − X)(1 − 4X + 2X^{2})^{m−1}.

Proof. To count permutations with no reflected points and one fixed point we set β = γ = 0 in the equation (⋆ ⋆ ⋆) and look at the coefficient of α. So we want the coefficient of α in

(1 − X) [1 + (2α − 4)X + ((α − 1)^{2} + 1)X^{2}]^{m}

which is easily computed to be

2mX(1 − X)(1 − 4X + 2X^{2})^{m−1}.
□

Theorem 3.9. The number of permutations in the symmetric group 𝔖_{2m+1} with no reflected points and two fixed points is given by the formula:

∑_{k} r_{k}^{−}(2m + 1 − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

2m(m − 1)X^{2}(1 − X)^{3}(1 − 4X + 2X^{2})^{m−2} + mX^{2}(1 − X)(1 − 4X + 2X^{2})^{m−1}.

Proof. To count permutations with no reflected points and two fixed points, we set β = γ = 0 in the equation (⋆ ⋆ ⋆) and we look at the coefficient of α^{2} which is easily computed to be

2m(m − 1)X^{2}(1 − X)^{3}(1 − 4X + 2X^{2})^{m−2} + mX^{2}(1 − X)(1 − 4X + 2X^{2})^{m−1}.

□ Theorem 3.10. The number of permutations in the symmetric group 𝔖_{2m+1} having a pivot point and no other fixed or reflected points is equal to the number x_{2m}.

Proof. If the pivot point is removed from such a permutation, what remains is a permutation in 𝔖_{2m} with no fixed or reflected points. □

Corollary 3.11. The number a_{2m+1} of permutations in the symmetric group 𝔖_{2m+1} with one reflected point and one fixed point is given by the formula:

a_{2m+1} = x_{2m} + ∑_{k} r_{k}^{−}(2m + 1 − k)!

where the numbers r_{k}^{−} are the coefficients of the polynomial

4m(m − 1)X^{2}(1 − X)^{3}(1 − 4X + 2X^{2})^{m−2}.

Proof. First, to count permutations with one fixed point and one reflected point without pivot points, we set γ = 0 in the equation (⋆ ⋆ ⋆) and look at the coefficient of αβ in

(1 − X) [1 + (2α + 2β − 4)X + ((α − 1)^{2} + (β − 1)^{2})X^{2}]^{m}

to get

∑_{k} r_{k}^{−}X^{k} = 4m(m − 1)X^{2}(1 − X)^{3}(1 − 4X + 2X^{2})^{m−2}

and

a_{2m+1} = ∑_{k} r_{k}^{−}(2m + 1 − k)! + x_{2m}.

□

Remark 3.12. To count derangements, that is, permutations without fixed points, we set α = γ = 0 and β = 1 in the equation (⋆ ⋆ ⋆) to get the usual hit polynomial

(1 − X)^{n}.

Definition 3.13. We say that a subset F of the set [n] is:

(1) semi-reflected if there exists at least one element i ∈ F such that n − i + 1 ∈ F.

(2) self-reflected if n − i + 1 ∈ F, for all elements i in the subset F.

The proof of the following lemmas is a simple exercise of combinatorics.

Lemma 3.14. The number of pairs of disjoint subsets F and R of the set [2n] such that #(F ∪ R) = 2k and both F and R are self-reflected is equal to

2^{k}\binom{n}{k}.

Lemma 3.15. The number of pairs of disjoint subsets F and R of the set [2n] or [2n + 1] such that #(F ∪ R) = n and both F and R are not semi-reflected is equal to 2^{2n}.

Theorem 3.16. The number of permutations of length 2n whose set of all fixed or reflected points is of cardinality 2k, and is a self-reflected set, is equal

to \binom{n}{k}2^{k}x_{2(n−k)}.

Proof. We consider the following board with weights as indicated. We illustrate it with the case for 2n = 6.

\begin{aligned}α_{1} & & & & & β_{1} \\ & α_{2} & & & β_{2} \\ & & α_{3} & β_{3} \\ & & β_{4} & α_{4} \\ & β_{5} & & & α_{5} \\ β_{6} & & & & & α_{6} \end{aligned}

By permuting the rows and columns we get

\begin{aligned}α_{1} & β_{1} \\ β_{6} & α_{6} \\ & & α_{2} & β_{2} \\ & & β_{5} & α_{5} \\ & & & & α_{3} & β_{3} \\ & & & & β_{4} & α_{4} \end{aligned}

We see that

∑_{k} r_{k}X^{k} = ∏_{i=1}^{n}[1 + (α_{i} + α_{2n−i+1} + β_{i} + β_{2n−i+1})X

+ (α_{i}α_{2n−i+1} + β_{i}β_{2n−i+1})X^{2}],

so

∑_{k} r_{k}^{−}X^{k} = ∏_{i=1}^{n}[1 + (α_{i} + α_{2n−i+1} + β_{i} + β_{2n−i+1} − 4)X

+ ((α_{i} − 1)(α_{2n−i+1} − 1) + (β_{i} − 1)(β_{2n−i+1} − 1))X^{2}],

and therefore H = ∑_{k} r_{k}^{−}(n − k)! with r_{k}^{−} as above. To count exactly once each permutation of length 2n in which the set of fixed or reflected points is self-reflected and has cardinality 2k, we look first at the coefficient of ∏_{s=1}^{p} μ_{i_{s}} ∏_{s=p+1}^{k} ν_{i_{s}} where μ_{i_{s}} = α_{i_{s}}α_{2n−i_{s}+1} and ν_{i_{s}} = β_{i_{s}}β_{2n−i_{s}+1}. We should make {i_{1}, …, i_{p}} and {i_{p+1}, …, i_{k}} disjoint subsets of the set [n] and moreover we should take i_{1} < … < i_{p} and i_{p+1} < … < i_{k}, and by Lemma 3.14 the number of possible choices for the set {i_{1}, …, i_{p}} and {i_{p+1}, …, i_{k}} is equal to 2^{k}\binom{n}{k}. We can compute by induction the coefficient of ∏_{s=1}^{p} μ_{i_{s}} ∏_{s=p+1}^{k} ν_{i_{s}}

which is equal to X^{2k}(1 − 4X + 2X^{2})^{2(n−k)} and this gives the result. □

Theorem 3.17. The number of permutations of [2n + 1], in which the set of fixed or reflected points has cardinality 2k + 1 and is self-reflected, is equal to

\binom{n}{k}2^{k}x_{2(n−k)}.

Proof. Notice that if the cardinality of a self-reflected subset of the set [2n + 1] is odd, this subset contains the integer n + 1. Since the integer n + 1 must be fixed point, we can remove it to get one of the permutations counted by Theorem 3.16. □

4. Derangements

We will conclude this paper with an unexpected relation which relates derangements and restricted permutations.

Theorem 4.1. The number of permutations of [2n], in which the set of all fixed or reflected points has cardinality n and is not semi-reflected, is equal to 2^{2n}d_{n}.

Proof. We consider again a board as in the proof of Theorem 3.16. To count exactly once each permutation of length 2n in which the set of all fixed or reflected points is not semi-reflected and has cardinality n, we look first at the coefficient of ∏_{s=1}^{p} α_{i_{s}} ∏_{s=p+1}^{n} β_{i_{s}} from

∏_{i=1}^{n}[1 + (α_{i} + α_{2n−i+1} + β_{i} + β_{2n−i+1} − 4)X

+ ((α_{i} − 1)(α_{2n−i+1} − 1) + (β_{i} − 1)(β_{2n−i+1} − 1))X^{2}]

such that no occurrences of the form α_{ℓ}α_{2n−ℓ+1} or β_{ℓ}β_{2n−ℓ+1} appear in the products. By induction we deduce this coefficient which is equal to

X^{n}(1 − X)^{n}.

For the sequence {i_{1}, …, i_{n}}, we should make {i_{1}, …, i_{p}} and {i_{p+1}, …, i_{n}} disjoint subsets of the set [2n] and moreover we should take i_{1} < … < i_{p} and i_{p+1} < … < i_{n}. By Lemma 3.15 the number of possible choices for the set {i_{1}, …, i_{p}} and {i_{p+1}, …, i_{n}} is equal to 2^{2n} and this gives the result. □

Theorem 4.2. The number of permutations of [2n + 1], in which the set of all fixed or reflected points is not semi-reflected and has cardinality n, is equal to 2^{2n}d_{n+1}.

Proof. Notice that if the cardinality of a non semi-reflected subset of the set [2n + 1] is equal to n, this subset does not contain the integer n + 1. Since the integer n + 1 is not a fixed point, we can add it to get one of the permutations counted by Theorem 4.1. □

Theorem 4.3. The number of permutations of [2n + 1], in which the set of all fixed or reflected points contains the integer n + 1 and has cardinality n + 1 and is not semi-reflected if the element n + 1 is deleted, is equal to 2^{2n}d_{n}.

Proof. Notice that if the cardinality of a non semi-reflected subset of the set [2n+1] is equal to n+1, this subset contains the integer n+1. Since the integer n + 1 must be fixed point, we can remove it to get one of the permutations counted by Theorem 4.1. □

Acknowledgements. The author is very grateful to Ira Gessel for his kind advice during the author’s stay at the Institut Mittag-Leffler, Sweden. Thanks also to the referees for their comments and corrections to the original version of this paper.

References

[1] M. Ahmed, J. De Loera, R. Hemmecke. – Polyhedral cones of magic cubes and squares. – Algorithm combinat. 25,2003, pp. 25–41 arXiv:math.CO/0201108, 2002.

[2] E. Ehrhart. – Sur les carrés magiques. – C. R. Acad.Sci. Paris, 227 A, 1973, pp. 575–577.

[3] D. C. Fielder. – A generator of rook polynomials. – Mathematica J. 9, 2004, pp. 371–375.

[4] I. Gessel. – Generalised rook polynomials and orthogonal polynomials. – in q-Series and Partitions, ed. D. Stanton, The IMA Volumes in Mathematics and Its Applications, Vol. 18, 1989, Springer-Verlag, New York, pp. 159–176.

[5] S. Hertzsprung. – Løsning og Udvidelse af Opgave 402. – Tidsskrift for Math. 4, 1879, pp. 134–140.

[6] D. Knuth. – The art of computer programming 3. – Sorting and Searching 2nd Ed., Addison-Wesley, Reading, 1981.

[7] P. A. MacMahon. – Combinatory analysis. – Cambridge University Press, 1915.

[8] J. Riordan. – An introduction to combinatorial analysis. – John Wiley & Sons, New York, 1958.

[9] T. Simpson. – Permutations with unique fixed and reflected points. – Ars Combin. 39, 1995, pp 97–108.

[10] R. P. Stanley. – Enumerative combinatorics. – Vol. 1, Cambridge, 1997.

[11] A. Tucker. – Applied combinatorics. – John Wiley & Sons, New York, 2002.

Département de Mathématiques et Informatique, Université d’ Antananarivo, 101 Antananarivo, Madagascar

 E-mail address: frakoton@univ-antananarivo.mg