INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A31

A STUDY OF EULERIAN NUMBERS FOR PERMUTATIONS IN THE ALTERNATING GROUP

Shinji Tanimoto

Department of Mathematics, Kochi Joshi University Kochi 780-8515, Japan

                       tanimoto@cc.kochi-wu.ac.jp

Received: 5/9/06, Accepted: 10/15/06, Published: 10/20/06

Abstract

The cardinalities of the sets of even and odd permutations with a given ascent number are investigated by an operator that was introduced by the author. We will deduce the recurrence relations for such Eulerian numbers of even and odd permutations, and deduce divisibility properties by prime powers concerning them and some related numbers.

Keywords: Eulerian numbers; inversions; recurrence relations

1. Introduction

An ascent (or descent) of a permutation a_{1}a_{2} ⋯ a_{n} of [n] = {1, 2, …, n} is an adjacent pair such that a_{i} < a_{i+1} (or a_{i} > a_{i+1}) for some i (1 ≤ i ≤ n − 1). Let E(n, k) be the set of all permutations of [n] with exactly k ascents, where 0 ≤ k ≤ n − 1. Its cardinality is the classical Eulerian number;

A_{n,k} = |E(n, k)|,

whose properties and identities can be found in [2-6], for example.

An inversion of a permutation A = a_{1}a_{2} ⋯ a_{n} is a pair (i, j) such that 1 ≤ i < j ≤ n and a_{i} > a_{j}. Let us denote by inv(A) the number of inversions in a permutation A, and by E_{e}(n, k) or E_{o}(n, k) the subsets of all permutations in E(n, k) that have, respectively, even or odd numbers of inversions.

The aim of this paper is to investigate their cardinalities;

B_{n,k} = |E_{e}(n, k)| and C_{n,k} = |E_{o}(n, k)|.

Obviously we have A_{n,k} = B_{n,k} + C_{n,k}, while the differences D_{n,k} = B_{n,k} − C_{n,k} are called signed Eulerian numbers in [1], where the descent number was considered instead of the ascent number. Therefore, the identities for D_{n,k} presented here correspond to those in [1] that are obtained by replacing k with n − k − 1.

In order to study these numbers, we make use of an operator on permutations in [n], which was introduced in [9]. The operator σ is defined by adding one to all entries of a permutation and by changing n + 1 into one. However, when n appears at either end of a permutation, it is removed and one is put at the other end. That is, for a permutation a_{1}a_{2} ⋯ a_{n} with a_{i} = n for some i (2 ≤ i ≤ n − 1), we have

(i) σ(a_{1}a_{2} ⋯ a_{n}) = b_{1}b_{2} ⋯ b_{n},

where b_{i} = a_{i} + 1 for all i (1 ≤ i ≤ n) and n + 1 is replaced by one. However, for a permutation a_{1}a_{2} ⋯ a_{n−1} of [n − 1], we have:

(ii) σ(a_{1}a_{2} ⋯ a_{n−1}n) = 1b_{1}b_{2} ⋯ b_{n−1};

(iii) σ(na_{1}a_{2} ⋯ a_{n−1}) = b_{1}b_{2} ⋯ b_{n−1}1,

where b_{i} = a_{i} + 1 for all i (1 ≤ i ≤ n − 1). We denote by σ^{ℓ}A the repeated ℓ applications of σ to a permutation A. It is obvious that the operator preserves the numbers of ascents and descents in a permutation, that is, σA ∈ E(n, k) if and only if A ∈ E(n, k).

Let us observe the number of inversions of a permutation when σ is applied. When n appears at either end of a permutation A = a_{1}a_{2} ⋯ a_{n} as in (ii) or (iii), it is evident that

inv(σA) = inv(A).

Next let us consider the case (i). When a_{i} = n for some i (2 ≤ i ≤ n − 1), we get σ(a_{1}a_{2} ⋯ a_{n}) = b_{1}b_{2} ⋯ b_{n}, where b_{i} = 1 is at the ith position. In this case, n − i inversions (i, i + 1), …, (i, n) of A vanish and, in turn, i − 1 inversions (1, i), …, (i − 1, i) of σA occur. Hence the difference between the numbers of inversions is

inv(σA) − inv(A) = (i − 1) − (n − i) = 2i − (n + 1).  (1)

Therefore, if n is odd, the operator σ preserves the parity of all permutations of [n]. When n is even, however, each application of the operator changes the parity of permutations as long as n remains in the interior of permutations.

For convenience sake we denote by E_{e}^{−}(n, k) and E_{e}^{+}(n, k) the sets of permutations a_{1}a_{2} ⋯ a_{n} in E_{e}(n, k) with a_{1} < a_{n} and a_{1} > a_{n}, respectively. Similarly, E_{o}^{−}(n, k) and E_{o}^{+}(n, k) denote those in E_{o}(n, k), respectively. In E_{e}^{−}(n, k) and E_{o}^{−}(n, k) canonical permutations are defined as those of the form a_{1}a_{2} ⋯ a_{n−1}n, and in E_{e}^{+}(n, k) and E_{o}^{+}(n, k) as those of the form na_{1}a_{2} ⋯ a_{n−1}, where a_{1}a_{2} ⋯ a_{n−1} is a permutation of [n − 1].

In [8] and the references therein, even and odd permutations were classified by the anti-excedance number, not by the ascent number. An anti-excedance in a permutation a_{1}a_{2} ⋯ a_{n} means an inequality i ≥ a_{i}. Recurrence relations were given for the cardinalities P_{n,k} and Q_{n,k} of the sets of even and odd permutations, respectively, with anti-excedance number k. They hold for all natural integers n as follows:

P_{n,k} = kQ_{n−1,k} + (n − k)Q_{n−1,k−1} + P_{n−1,k−1};
Q_{n,k} = kP_{n−1,k} + (n − k)P_{n−1,k−1} + Q_{n−1,k−1}.

The recurrence relations for B_{n,k} and C_{n,k} seem not so simple, because they have different expressions according to the parity of n, as will be revealed in the following sections.

First we derive the recurrence relation for the signed Eulerian numbers D_{n,k} = B_{n,k} − C_{n,k}. The relation was conjectured in [7] and an analytic proof for it was given in [1]. In Section 4 we will derive it from a quite different point of view, based on the properties of the operator σ. Making use of it, the recurrence relations for B_{n,k} and C_{n,k} will be obtained.

In Section 5 it is shown that divisibility properties for B_{n,k}, C_{n,k} and some related numbers by prime powers can be obtained by our approach.

2. The Numbers B_{n,k} and C_{n,k}

The numbers B_{n,k} and C_{n,k} enjoy some symmetry properties according to the values of n. The permutation n ⋯ 21 ∈ E(n, 0) has n(n − 1)/2 inversions. Hence the values of B_{n,0} and C_{n,0} are given by

B_{n,0} = \{ \begin{matrix}1 & if n ≡ 0 or 1 (mod 4), \\ 0 & if n ≡ 2 or 3 (mod 4), \end{matrix}

and

C_{n,0} = \{ \begin{matrix}0 & if n ≡ 0 or 1 (mod 4), \\ 1 & if n ≡ 2 or 3 (mod 4). \end{matrix}

For a permutation A = a_{1}a_{2} ⋯ a_{n} we define its reflection by A^{∗} = a_{n} ⋯ a_{2}a_{1}. Using reflected permutations and the parity of n(n − 1)/2, the following symmetry properties between B_{n,k} and C_{n,k} are easily checked.

(i) n ≡ 0 or 1 ( mod 4). In this case, A ∈ E_{e}(n, k) if and only if A^{∗} ∈ E_{e}(n, n−k −1), and A ∈ E_{o}(n, k) if and only if A^{∗} ∈ E_{o}(n, n − k − 1), so we have

B_{n,k} = B_{n,n−k−1} and C_{n,k} = C_{n,n−k−1}.

(ii) n ≡ 2 or 3 ( mod 4). In this case, A ∈ E_{e}(n, k) if and only if A^{∗} ∈ E_{o}(n, n−k−1), and A ∈ E_{o}(n, k) if and only if A^{∗} ∈ E_{e}(n, n − k − 1), so we have

B_{n,k} = C_{n,n−k−1} and C_{n,k} = B_{n,n−k−1}.

The values of B_{n,k} and C_{n,k} for small n are shown in the next two tables. The integers in their top rows represent the values of k. In Section 4 a formula for calculating these numbers will be supplied by means of A_{n,k} and D_{n,k}.

B_{n,k}  0 1  2  3  4  5  6  7 8 9
n = 2 0 1
n = 3 0 2  1
n = 4 1 5  5  1
n = 5 1 14  30  14  1
n = 6 0 28 155  147  29  1
n = 7 0 56 605 1208  586  64  1
n = 8 1 127 2133 7819 7819 2133  127  1
n = 9 1 262 7288 44074 78190 44074 7288 262 1
n = 10 0 496 23947 227623 655039 655315 227569 23893 517 1
C_{n,k}  0 1  2  3  4  5  6  7 8 9
n = 2 1 0
n = 3 1 2  0
n = 4 0 6  6  0
n = 5 0 12  36  12  0
n = 6 1 29 147  155  28  0
n = 7 1 64 586 1208  605  56  0
n = 8 0 120 2160 7800 7800 2160  120  0
n = 9 0 240 7320 44160 78000 44160 7320 240 0
n = 10 1 517 23893 227569 655315 655039 227623 23947 496 0

3. The Case of Odd n

Throughout this section we assume that n is an odd integer. It was shown in [9] that to each permutation A of [n] there corresponds a smallest positive integer π(A) such that σ^{π(A)}A = A, which is called the period of A. Its trace

{σA, σ^{2}A, …, σ^{π(A)}A = A}

is called the orbit of A. The orbit of a permutation of E_{e}^{−}(n, k) under σ is entirely contained in E_{e}^{−}(n, k) and similarly for E_{e}^{+}(n, k), as is shown previously in the case of odd n. Here we mainly deal with the set E_{e}(n, k) = E_{e}^{−}(n, k)∪E_{e}^{+}(n, k) and its cardinality B_{n,k}, since the same arguments can also be applied to E_{o}(n, k) = E_{o}^{−}(n, k) ∪ E_{o}^{+}(n, k) and its cardinality C_{n,k}.

It was shown in [9] that the period satisfies the relation

π(A) = \{ \begin{matrix}(n − k) gcd(n, π(A)) & if A ∈ E_{e}^{−}(n, k) ∪ E_{o}^{−}(n, k), \\ (k + 1) gcd(n, π(A)) & if A ∈ E_{e}^{+}(n, k) ∪ E_{o}^{+}(n, k). \end{matrix}  (2)

It follows from (2) that the period of a permutation A ∈ E(n, k) is either d(n − k) or d(k + 1) for a positive divisor d of n, i.e., d = gcd(n, π(A)), although there may be no permutations having such periods for some divisors. In this paper, divisors of n always mean positive divisors.

For a divisor d of n, we denote by α_{d}^{k} the number of orbits of period d(n − k) in E_{e}^{−}(n, k) and by β_{d}^{k} that of orbits of period d(k + 1) in E_{e}^{+}(n, k). In the case of odd n the next theorem plays a fundamental role.

Theorem 3.1 Let n be an odd integer and let k be an integer satisfying 1 ≤ k ≤ n − 1. Then it follows that

B_{n−1,k−1} = ∑_{d|n} dα_{d}^{k},  (3)
B_{n−1,k} = ∑_{d|n} dβ_{d}^{k},  (4)
B_{n,k} = ∑_{d|n} d{(n − k)α_{d}^{k} + (k + 1)β_{d}^{k}}.  (5)

Proof. First let us consider permutations in E_{e}^{−}(n, k). In this case each orbit contains canonical permutations of the form a_{1}a_{2} ⋯ a_{n−1}n by (i) and (ii) of Section 1. It suffices to deal only with canonical ones in counting orbits. If A = a_{1}a_{2} ⋯ a_{n−1}n ∈ E_{e}^{−}(n, k), we see that a_{1}a_{2} ⋯ a_{n−1} ∈ E_{e}(n − 1, k − 1), since

inv(a_{1}a_{2} ⋯ a_{n−1}) = inv(A)

and n is deleted. Therefore, there exist B_{n−1,k−1} canonical permutations in E_{e}^{−}(n, k). It follows from (2) that the period of a permutation A ∈ E_{e}^{−}(n, k) is equal to d(n − k) for a divisor d of n. There exist n canonical permutations in {σA, σ^{2}A, …, σ^{n(n−k)}A = A} due to [9, Corollary 2], and hence each orbit {σA, σ^{2}A, …, σ^{d(n−k)}A = A} of a permutation A with period d(n − k) contains exactly d canonical permutations. This follows from the fact that the latter repeats itself n/d times in the former. Since there exist α_{d}^{k} orbits of period d(n − k) for each divisor d of n, classifying all canonical permutations of E_{e}^{−}(n, k) into orbits leads us to (3).

The proof of (4) is similar. To do this we consider permutations in E_{e}^{+}(n, k). In this case each orbit contains canonical permutations of the form na_{1}a_{2} ⋯ a_{n−1} by (i) and (iii) of Section 1. If A = na_{1}a_{2} ⋯ a_{n−1} ∈ E_{e}^{+}(n, k), we see that a_{1}a_{2} ⋯ a_{n−1} ∈ E_{e}(n − 1, k), since

inv(a_{1}a_{2} ⋯ a_{n−1}) = inv(A) − (n − 1)

and n − 1 is an even number by assumption. Therefore, the set of all canonical permutations in E_{e}^{+}(n, k) has cardinality B_{n−1,k}. Again using (2), the period of a permutation A ∈ E_{e}^{+}(n, k) is equal to d(k + 1) for a divisor d of n. By [9, Corollary 2] there exist n canonical permutations in {σA, σ^{2}A, …, σ^{n(k+1)}A = A} and hence, as above, there exist exactly d such permutations in each orbit {σA, σ^{2}A, …, σ^{d(k+1)}A = A} of a permutation A with period d(k + 1). There exist β_{d}^{k} orbits of period d(k + 1) for each divisor d of n. Hence, we can obtain (4) by classifying all canonical permutations in E_{e}^{+}(n, k) into orbits.

Considering the numbers of orbits and periods, we see that the cardinalities of E_{e}^{±}(n, k) are obtained by

|E_{e}^{−}(n, k)| = ∑_{d|n} d(n − k)α_{d}^{k} and |E_{e}^{+}(n, k)| = ∑_{d|n} d(k + 1)β_{d}^{k}.  (6)

Since the set E_{e}(n, k) is a disjoint union of E_{e}^{−}(n, k) and E_{e}^{+}(n, k), we conclude that

B_{n,k} = |E_{e}^{−}(n, k)| + |E_{e}^{+}(n, k)| = ∑_{d|n} d{(n − k)α_{d}^{k} + (k + 1)β_{d}^{k}},  (7)

which proves (5). This completes the proof. □

Let us denote by γ_{d}^{k} the number of orbits of period d(n − k) in E_{o}^{−}(n, k) and by δ_{d}^{k} that of orbits of period d(k + 1) in E_{o}^{+}(n, k). When n is odd, analogous relations to (3)-(6) hold for C_{n,k}, γ_{d}^{k} and δ_{d}^{k}, since the orbit of a permutation of E_{o}^{±}(n, k) under σ is also contained in E_{o}^{±}(n, k).

We state them for the sake of completeness;

C_{n−1,k−1} = ∑_{d|n} dγ_{d}^{k}, C_{n−1,k} = ∑_{d|n} dδ_{d}^{k},

and

|E_{o}^{−}(n, k)| = ∑_{d|n} d(n − k)γ_{d}^{k}, |E_{o}^{+}(n, k)| = ∑_{d|n} d(k + 1)δ_{d}^{k}.

Since the set E_{o}(n, k) is a disjoint union of E_{o}^{−}(n, k) and E_{o}^{+}(n, k), we obtain

C_{n,k} = |E_{o}^{−}(n, k)| + |E_{o}^{+}(n, k)| = ∑_{d|n} d{(n − k)γ_{d}^{k} + (k + 1)δ_{d}^{k}},  (8)

Making use of (3) and (4), we see that both cardinalities in (6) can be written simply by the notation B_{n,k} and their counterparts for E_{o}(n, k) also follow from the above relations in a similar manner.

Corollary 3.2 When n is odd, the cardinalities of E_{e}^{±}(n, k) and E_{o}^{±}(n, k) are given by

(i) |E_{e}^{−}(n, k)| = (n−k)B_{n−1,k−1} and |E_{o}^{−}(n, k)| = (n−k)C_{n−1,k−1} (1 ≤ k ≤ n−1),

(ii) |E_{e}^{+}(n, k)| = (k + 1)B_{n−1,k} and |E_{o}^{+}(n, k)| = (k + 1)C_{n−1,k} (0 ≤ k ≤ n − 2).

Using (7), (8) and this corollary, we can obtain the following two corollaries. The relations in Corollary 3.3 have the same form as the recurrence relation for classical Eulerian numbers A_{n,k} in [3];

A_{n,k} = (n − k)A_{n−1,k−1} + (k + 1)A_{n−1,k}.  (9)

Corollary 3.3 When n is odd, the following relations hold for B_{n,k} and C_{n,k}:

B_{n,k} = (n − k)B_{n−1,k−1} + (k + 1)B_{n−1,k};  (10)
C_{n,k} = (n − k)C_{n−1,k−1} + (k + 1)C_{n−1,k}.  (11)

Corollary 3.4 When n is odd, the following relations hold:

(i) |E_{e}^{−}(n, k)| − |E_{o}^{−}(n, k)| = (n − k)D_{n−1,k−1} (1 ≤ k ≤ n − 1);

(ii) |E_{e}^{+}(n, k)| − |E_{o}^{+}(n, k)| = (k + 1)D_{n−1,k} (0 ≤ k ≤ n − 2).

4. Recurrences for B_{n,k} and C_{n,k}

When n is even, neither equality (10) nor (11) holds, as is seen from the tables of Section 2. For example, an odd integer C_{10,4} cannot be written as a linear sum of C_{9,k}’s or B_{9,k}’s (1 ≤ k ≤ 7) with integral coefficients, since they are all even. Therefore, neither (10) nor (11) provide a recurrence relation of the numbers B_{n,k} or C_{n,k}.

As for the differences D_{n,k} = B_{n,k} − C_{n,k}, however, their recurrence relation was conjectured in [7] and an analytic proof for it was given in [1]. In our notation it is described as the next theorem, for which we provide another proof from a combinatorial point of view. Notice that there is a different flavor in the case of even n.

Theorem 4.1 The recurrence relation for D_{n,k} is given by

D_{n,k} = \{ \begin{matrix}(n − k)D_{n−1,k−1} + (k + 1)D_{n−1,k}, & if n is odd, \\ D_{n−1,k−1} − D_{n−1,k}, & if n is even. \end{matrix}  (12)

Proof. The first part of this relation follows immediately from (10) and (11) of Corollary 3.3. Assuming that n is even, we show the second part by means of the operator σ.

Recall that when n is even, the operator may change the parity of permutations of E(n, k), but it is a bijection on E_{e}^{−}(n, k) ∪ E_{o}^{−}(n, k) and on E_{e}^{+}(n, k) ∪ E_{o}^{+}(n, k), respectively.

First let us consider permutations A = a_{1}a_{2} ⋯ a_{n} in E_{e}^{−}(n, k) ∪ E_{o}^{−}(n, k) and divide all permutations in E_{e}^{−}(n, k) ∪ E_{o}^{−}(n, k) into the following two types:

(i) A = a_{1}a_{2} ⋯ a_{n−1}n, where a_{1}a_{2} ⋯ a_{n−1} is a permutation of [n − 1];

(ii) A = a_{1}a_{2} ⋯ a_{n} with a_{1} < a_{n}, where a_{i} = n for some i (2 ≤ i ≤ n − 1).

Suppose A ∈ E_{e}^{−}(n, k). If A is of type (i), then σA remains an even permutation, since inv(σA) = inv(A). We see that the cardinality of permutations of type (i) is B_{n−1,k−1}, since A is even and n is the last entry. However, if A ∈ E_{e}^{−}(n, k) is of type (ii), then we have σA ∈ E_{o}^{−}(n, k) by (1), since n + 1 is an odd integer. Therefore, the cardinality of permutations of type (ii) in E_{e}^{−}(n, k) is

|E_{e}^{−}(n, k)| − B_{n−1,k−1},  (13)

and precisely so many permutations change the parity from even to odd under σ.

Similarly, suppose A ∈ E_{o}^{−}(n, k). If A is of type (i), then σA remains an odd permutation. We see that the cardinality of permutations of type (i) is C_{n−1,k−1}. If A ∈ E_{o}^{−}(n, k) is of type (ii), then we have σA ∈ E_{e}^{−}(n, k) by (1). The cardinality of permutations of type (ii) in E_{o}^{−}(n, k) is

|E_{o}^{−}(n, k)| − C_{n−1,k−1},  (14)

and precisely so many permutations change the parity from odd to even under σ.

Since σ is a bijection on E_{e}^{−}(n, k) ∪ E_{o}^{−}(n, k), both cardinalities given by (13) and (14) must be equal. Hence we obtain

|E_{e}^{−}(n, k)| − |E_{o}^{−}(n, k)| = B_{n−1,k−1} − C_{n−1,k−1} = D_{n−1,k−1}.  (15)

Next let us consider permutations A = a_{1}a_{2} ⋯ a_{n} in E_{e}^{+}(n, k) ∪ E_{o}^{+}(n, k) and divide all permutations in E_{e}^{+}(n, k) ∪ E_{o}^{+}(n, k) into the following two types:

(iii) A = na_{1}a_{2} ⋯ a_{n−1}, where a_{1}a_{2} ⋯ a_{n−1} is a permutation of [n − 1];

(iv) A = a_{1}a_{2} ⋯ a_{n} with a_{1} > a_{n}, where a_{i} = n for some i (2 ≤ i ≤ n − 1).

If A ∈ E_{e}^{+}(n, k) is of type (iii), then σA remains an even permutation. We see that the cardinality of permutations of type (iii) is C_{n−1,k}, since inv(A)−inv(a_{1}a_{2} ⋯ a_{n−1}) = n−1 and n − 1 is odd. However, if A ∈ E_{e}^{+}(n, k) is of type (iv), then we have σA ∈ E_{o}^{+}(n, k) by (1). The cardinality of permutations of type (iv) in E_{e}^{+}(n, k) is

|E_{e}^{+}(n, k)| − C_{n−1,k},  (16)

and precisely so many permutations change the parity from even to odd under σ.

Similarly, if A ∈ E_{o}^{+}(n, k) is of type (iii), then σA remains an odd permutation. We see that the cardinality of permutations of type (iii) is B_{n−1,k} as above. If A ∈ E_{o}^{+}(n, k) is of type (iv), then we have σA ∈ E_{e}^{+}(n, k) by (1). The cardinality of permutations of type (iv) in E_{o}^{+}(n, k) is

|E_{o}^{+}(n, k)| − B_{n−1,k},  (17)

and precisely so many permutations change the parity from odd to even under σ.

Since σ is a bijection on E_{e}^{+}(n, k) ∪ E_{o}^{+}(n, k), both cardinalities given by (16) and (17) must be equal. Hence we obtain

|E_{e}^{+}(n, k)| − |E_{o}^{+}(n, k)| = −B_{n−1,k} + C_{n−1,k} = −D_{n−1,k}.  (18)

From (7) and (8), adding (15) and (18) yields B_{n,k} −C_{n,k} = D_{n,k} = D_{n−1,k−1} −D_{n−1,k}, which is the required relation. This completes the proof. □

Symmetry properties for D_{n,k} follow from the relations presented in Section 2:

(i) For n ≡ 0 or 1 (mod 4), D_{n,k} = D_{n,n−k−1};

(ii) For n ≡ 2 or 3 (mod 4), D_{n,k} = −D_{n,n−k−1}.

The values of D_{n,k} for small n is given below.

D_{n,k}  0  1  2  3  4  5  6  7 8 9
n = 2 −1  1
n = 3 −1  0  1
n = 4  1 −1 −1  1
n = 5  1  2 −6  2  1
n = 6 −1 −1  8 −8  1  1
n = 7 −1 −8 19  0 −19  8  1
n = 8  1  7 −27 19  19 −27  7  1
n = 9  1 22 −32 −86 190 −86 −32 22 1
n = 10 −1 −21 54 54 −276 276 −54 −54 21 1

Thus the values of B_{n,k} and C_{n,k} can be known through

B_{n,k} = \frac{A_{n,k} + D_{n,k}}{2} , C_{n,k} = \frac{A_{n,k} − D_{n,k}}{2} ,

using A_{n,k} and D_{n,k} that are calculated according to the respective recurrence relations (9) and (12). From these equalities, we can obtain the expressions of B_{n,k} and C_{n,k} by means of B_{n−1,k}’s and C_{n−1,k}’s in the case of even n, which constitute recurrence relations for B_{n,k} and C_{n,k} together with Corollary 3.3.

Corollary 4.2 When n is even, the following relations hold for B_{n,k} and C_{n,k}:

2B_{n,k} = (n − k + 1)B_{n−1,k−1} + kB_{n−1,k} + (n − k − 1)C_{n−1,k−1} + (k + 2)C_{n−1,k};
2C_{n,k} = (n − k + 1)C_{n−1,k−1} + kC_{n−1,k} + (n − k − 1)B_{n−1,k−1} + (k + 2)B_{n−1,k}.

From (15) and (18) we get a counterpart of Corollary 3.4.

Corollary 4.3 When n is even, the following relations hold:

(i) |E_{e}^{−}(n, k)| − |E_{o}^{−}(n, k)| = D_{n−1,k−1} (1 ≤ k ≤ n − 1);

(ii) |E_{e}^{+}(n, k)| − |E_{o}^{+}(n, k)| = −D_{n−1,k} (0 ≤ k ≤ n − 2).

5. Orbits and their Applications

Again assume that n is an odd integer. We examine the numbers of orbits of particular types and from them deduce divisibility properties for B_{n,k}, C_{n,k} and some related numbers by prime powers.

For a positive integer ℓ with gcd(ℓ, n) = 1, a canonical permutation of [n] of the form

P_{n}^{ℓ} = 1(1 + ℓ)(1 + 2ℓ) ⋯ (1 + (n − 1)ℓ)

can be defined, where ℓ, 2ℓ, …, (n − 1)ℓ represent numbers modulo n. According to whether P_{n}^{ℓ} is an even or odd permutation, let us put

ϵ_{n}^{ℓ} = \{ \begin{matrix}1 & if P_{n}^{ℓ} is even, \\ 0 & if P_{n}^{ℓ} is odd. \end{matrix}

Theorem 5.1 Let n be an odd integer and let k be an integer such that 1 ≤ k ≤ n − 1.

(i) If a divisor d of n satisfies gcd(k, n/d) > 1, then α_{d}^{k} = γ_{d}^{k} = 0.

(ii) If gcd(k, n) = 1, then α_{1}^{k} = ϵ_{n}^{n−k} and γ_{1}^{k} = 1 − ϵ_{n}^{n−k}.

Proof. In order to prove (i), suppose A is a permutation that belongs to E_{e}^{−}(n, k). From (2) its period π(A) satisfies π(A) = (n−k) gcd(n, π(A)). Then, putting d = gcd(n, π(A)), we have π(A) = d(n − k) and d = gcd(n, d(n − k)), which implies gcd(n − k, n/d) = 1 or gcd(k, n/d) = 1. Consequently, we see that there exist no permutations of period d(n − k), i.e., α_{d}^{k} = 0, if a divisor d of n satisfies gcd(k, n/d) > 1.

The same arguments can be applied to permutations in E_{o}^{−}(n, k) and we obtain the assertion that γ_{d}^{k} = 0 if d satisfies gcd(k, n/d) > 1.

Next, in order to prove (ii), suppose gcd(k, n) = 1. In case of d = 1, due to [9, Theorem 7], there exists a unique orbit of period n − k in E_{e}^{−}(n, k) ∪ E_{o}^{−}(n, k), which contains only one canonical permutation P_{n}^{n−k}. Hence, if it is an even permutation, then we have α_{1}^{k} = 1 and γ_{1}^{k} = 0. Otherwise, α_{1}^{k} = 0 and γ_{1}^{k} = 1. This completes the proof. □

From Theorem 5.1 we can derive a criterion under which B_{n−1,k−1}, C_{n−1,k−1} and D_{n−1,k−1} are divisible by a prime power.

Corollary 5.2 Suppose that p is a prime and that an odd integer n is divisible by p^{m} for a positive integer m. If k is divisible by p, then B_{n−1,k−1}, C_{n−1,k−1} and D_{n−1,k−1} are also divisible by p^{m}.

Proof. Without loss of generality we can assume that m is the largest integer for which p^{m} divides n. Suppose k is a multiple of p. In Theorem 5.1 (i) we have seen that α_{d}^{k} = 0 for a divisor d of n such that gcd(k, n/d) > 1. On the other hand, a divisor d for which gcd(k, n/d) = 1 must be a multiple of p^{m}, since k is a multiple of p. Therefore, equality (3) of Theorem 3.1 implies that B_{n−1,k−1} is divisible by p^{m}. By the same arguments we see that C_{n−1,k−1} and D_{n−1,k−1} are also divisible by p^{m}, if k is a multiple of p. This completes the proof. □

When k is not a multiple of a prime p in Corollary 5.2, B_{n−1,k−1} and C_{n−1,k−1} are not necessarily divisible by p. For example, the next result summarizes the case where n is a prime power.

Corollary 5.3 Let p be an odd prime and m a positive integer. Then

B_{p^{m}−1,k−1} ≡ \{ \begin{matrix}ϵ_{p^{m}}^{p^{m}−k} & (mod p), & if gcd(p, k) = 1, \\ 0 & (mod p^{m}), & if gcd(p, k) = p, \end{matrix}

C_{p^{m}−1,k−1} ≡ \{ \begin{matrix}1 − ϵ_{p^{m}}^{p^{m}−k} & (mod p), & if gcd(p, k) = 1, \\ 0 & (mod p^{m}), & if gcd(p, k) = p. \end{matrix}

Proof. Remarking Corollary 5.2, it suffices to treat the case where gcd(p, k) = 1. From equality (3) we get

B_{p^{m}−1,k−1} = ∑_{d|p^{m}} dα_{d}^{k},

and we know that α_{1}^{k} = ϵ_{p^{m}}^{p^{m}−k} by Theorem 5.1 (ii). Thus we get the first part. Similarly, the second one follows from the equality

C_{p^{m}−1,k−1} = ∑_{d|p^{m}} dγ_{d}^{k},

together with γ_{1}^{k} = 1 − ϵ_{p^{m}}^{p^{m}−k}. □

The final corollary easily follows from Corollaries 3.2 and 5.2.

Corollary 5.4 Under the same assumptions as Corollary 5.2 the following hold.

(i) If k is divisible by p^{i} for some i (1 ≤ i ≤ m), then |E_{e}^{−}(n, k)| and |E_{o}^{−}(n, k)| are divisible by p^{m+i}.

(ii) If k + 1 is divisible by p^{i} for some i (i ≥ 1), then |E_{e}^{+}(n, k)| and |E_{o}^{+}(n, k)| are divisible by p^{m+i}.

References

[1] J. Désarménien and D. Foata, The signed Eulerian numbers. Discrete Math. 99: 49-58, 1992.

[2] D. Foata and M.-P. Schützenberger, Théorie Géométrique des Polynômes Eulériens. Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, Berlin, 1970.

[3] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, 1989.

[4] A. Kerber, Algebraic Combinatorics Via Finite Group Actions. BI-Wissenschafts- verlag, Mannheim, 1991.

[5] D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley, Reading, 1973.

[6] L. Lesieur and J.-L. Nicolas, On the Eulerian numbers M_{n} = max_{1≤k≤n} A(n, k). Europ. J. Combin. 13: 379-399, 1992.

[7] J.-L. Loday, Opérations sur l’homologie cyclique des algèbres commutatives. Invent. Math. 96: 205-230, 1989.

[8] R. Mantaci, Binomial coefficients and anti-excedances of even permutations: A combinatorial proof. J. of Comb. Theory (A) 63: 330-337, 1993.

[9] S. Tanimoto, An operator on permutations and its application to Eulerian numbers. Europ. J. Combin. 22: 569-576, 2001.