Séminaire Lotharingien de Combinatoire 65 (2011), Article B65b

GENERATOR SETS FOR THE ALTERNATING GROUP

AVIV ROTBART^{†}

Abstract. Although the alternating group is an index 2 subgroup of the symmetric group, there is no generating set that gives a Coxeter structure on it. Various generating sets were suggested and studied by Bourbaki, Mitsuhashi, Regev and Roichman, Vershik and Vserminov, and others. In a recent work of Brenti, Reiner and Roichman, it is explained that palindromes in Mitsuhashi’s generating set play a role similar to that of reflections in a Coxeter system.

We study in detail the length function with respect to the set of palindromes. Results include an explicit combinatorial description, a generating function, and an interesting connection to Broder’s restricted Stirling numbers.

1. Introduction

The study of parameters (statistics) of the symmetric group and other related groups is a very active branch of combinatorics in recent years. A major step was made about one hundred years ago, when MacMahon [6] showed that the parameters major index and inversion number are equi-distributed on the symmetric group, S_{n}. This important result is the foundation of the field, and stimulated many subsequent generalizations and refinements.

It is well known that several statistics on S_{n} may be defined via its Coxeter generators (simple reflections) {s_{i} = (i, i+1) | 1 ≤ i ≤ n−1}, or via the transpositions (reflections) {t_{ij} = (i, j) | 1 ≤ i < j ≤ n}. Unfortunately, the alternating group A_{n} ⊆ S_{n} is not a Coxeter group. Our goal is to study generating sets for the alternating group that play a role similar to that of reflections in the symmetric group, and to explore the combinatorial properties of A_{n} based on these sets.

A good candidate is the set {s_{1}s_{i+1} = (1, 2)(i+1, i+2) | 1 < i < n−1}. Mitsuhashi [7] pointed out that these generators for the alternating group play a role similar to that of the above Coxeter generators of S_{n}. Regev and Roichman [8] describe a canonical presentation of the elements in A_{n} based on this set. They also calculate the generating functions of length and other statistics, with respect to this set of generators.

Our work deals with A_{n}-statistics calculated with respect to a new set of generators, {s_{1}t_{ij} = (1, 2)(i, j) | 1 ≤ i < j ≤ n}. This set consists of palindromes in Mitsuhashi’s generators discussed above. As Brenti, Reiner and Roichman [3] explain, these palindromes play a role similar to that of reflections in the symmetric group. The following diagram describes the relations between the four generating sets mentioned above.

† Department of Mathematics, Bar-Ilan University, Ramat Gan 52900, Israel.

Email: aviv.rotbart@gmail.com.

This paper is part of the author’s MSc thesis, which was written at Bar-Ilan University under the supervision of Prof. R. M. Adin and Prof. Y. Roichman.

S_{n}-Coxeter

conjugate by S_{n} ⟶

S_{n}-Transpositions

C = {s_{i} | 1 ≤ i ≤ n − 1}  T = {t_{ij} | 1 ≤ i < j ≤ n}

↓ multiply by s_{1}  ↓ multiply by s_{1}

A_{n}-Coxeter (Mitsuhashi) take palindromes ⟶

A_{n}-Transpositions

C(A_{n}) = {s_{1}s_{i+1} | 1 < i ≤ n − 1}  T (A_{n}) = {s_{1}t_{ij} | 1 ≤ i < j ≤ n}

Various aspects of the generating set T (A_{n}) are studied in this work, including: canonical forms of elements in A_{n} with respect to T (A_{n}); length of elements and the relation between length and number of cycles; a generating function for length expectation and variance for length; and finally a connection with Broder’s restricted Stirling numbers [2].

The methods used in this work include: manipulations on generating functions of Stirling numbers; theorems on the number of cycles of a permutation and on the number of permutations of a given length in S_{n}; bijections between certain subsets of permutations in A_{n}, S_{n} and permutations with Broder’s property (see Definition 2.13).

The paper is organized as follows. Detailed background and notations for the symmetric and alternating groups, as well as for Stirling numbers, is given in Section 2. In Section 3 we present the main results achieved in this work. The A canonical presentation is analyzed in Section 4. In Section 5 we discuss refined counts of permutations in A_{n}, while the relation between length and the number-of-cycles statistic is analyzed in Section 6. In Section 7 we calculate the generating function of length with respect to the generating set T (A_{n}). The expectation and variance of the length function are studied in Section 8. The relation between our results and restricted Stirling numbers is analyzed in Section 9.

2. Background

2.1. The Symmetric Group. In this subsection, we present the main notations, definitions and theorems on the symmetric group, denoted by S_{n}.

Notation 2.1. Let n be a nonnegative integer, then [n] := {1, 2, 3, …, n} (where [0] := ∅).

Definition 2.2. Denote by ℕ the set of natural numbers. The symmetric group on n ∈ ℕ letters (denoted by S_{n}) is the group consisting of all permutations on n letters, with composition as the group operation.

Definition 2.3. Given a permutation v ∈ S_{n}, we say that a pair (i, j) ∈ [n] × [n] is an inversion of v if i < j and v(i) > v(j). If (i, i + 1) is a transposition of v, then it is called an adjacent transposition.

Definition 2.4. The Coxeter generators of S_{n} are

{s_{i} = (i, i + 1) | 1 ≤ i ≤ n − 1},

i.e., all the adjacent transpositions.

It is a well-known fact that the symmetric group is a Coxeter group with respect to the above generating set. The following natural statistic describes the length of permutations in the symmetric group, with respect to the Coxeter generating set:

Definition 2.5. The length of a permutation v ∈ S_{n} with respect to the Coxeter generators is defined to be

ℓ_{C}(v) := min{ r ≥ 0 | v = s_{i_{1}} … s_{i_{r}} for some i_{1}, …, i_{r} ∈ [n − 1] }.

Definition 2.6. The inversion number of v ∈ S_{n} is

inv(v) := |{(i, j) | 1 ≤ i < j ≤ n, v(i) > v(j)}|.

Fact 2.7. For each v ∈ S_{n}, we have

inv(v) = ℓ_{C}(v).

Another important set of generators for S_{n} is the set of all transpositions.

Notation 2.8. Denote by T the set of all transpositions in S_{n}, i.e.,

T = {(i, j) | 1 ≤ i < j ≤ n}.

The definition of length with respect to T is similar.

Definition 2.9. Let v ∈ S_{n}, then

ℓ_{T} (v) := min{ r ≥ 0 | v = t_{1} … t_{r}, t_{i} ∈ T }.

A well known result describes the connection between the number of cycles and this length statistics in S_{n}.

Theorem 2.10. If cyc(v) is the number of cycles in v ∈ S_{n}, then

ℓ_{T} (v) + cyc(v) = n

This result will be useful in some of the proofs in this work.

2.2. The Alternating Group. In this section we define the alternating group, which is a subgroup of the symmetric group. We also describe a known generating set for this group and the corresponding generating function of length.

Definition 2.11. The Alternating Group on n letters, denoted by A_{n}, is the group consisting of all even permutations in the symmetric group S_{n}; i.e., A_{n} := {v ∈ S_{n} | sign(v) = 1}.

Following Mitsuhashi [7] we let

a_{i} := s_{1}s_{i} = (1, 2)(i, i + 1) (2 ≤ i ≤ n − 1).

The set C(A_{n}) := {a_{i} | 2 ≤ i ≤ n − 1} generates the alternating group on n letters, A_{n}.

Regev and Roichman [8] used Mitsuhashi’s generators to describe a covering map f : A_{n+1} → S_{n}, which allows us to translate S_{n}-identities into corresponding A_{n+1}- identities. They gave a formula for the generating function of length with respect to these generators.

Proposition 2.12 ([8, Thm. 6.1]). Denoting by ℓ_{C(A_{n})}(·) is the length with respect to Mitsuhashi’s generators, we have

∑_{w∈A_{n+1}} q^{ℓ_{C(An)}(w)} = (1 + 2q)(1 + q + 2q^{2}) ⋯ (1 + q + … + q^{n−2} + 2q^{n−1}).

2.3. Stirling Numbers. For basic properties of Stirling numbers the reader is referred to [9]. In this subsection we describe one important generalization of them, Broder’s [2] restricted Stirling numbers.

Definition 2.13. The unsigned r-restricted Stirling number of the first kind, denoted by \left[{n \atop k}\right]_{r}, is the number of permutations of the set \{1, 2, …, n\} with k disjoint cycles, with the restriction that the numbers 1, 2, …, r belong to distinct cycles. The case r = 1 gives the usual unsigned Stirling numbers of the first kind.

Definition 2.14. The Kronecker delta function is defined as follows:

δ_{i,j} = \begin{cases}1, & if i = j; \\ 0, & otherwise. \end{cases}

Claim 2.15. r-Stirling numbers of the first kind satisfy the same recurrence relation as unsigned Stirling numbers of the first kind, except for the initial conditions:

\left[{n \atop k}\right]_{r} = (n − 1)\left[{n − 1 \atop k}\right]_{r} + \left[{n − 1 \atop k − 1}\right]_{r}, (r < k < n),

with the following initial conditions:

\left[{n \atop k}\right]_{r} = 0,  (k < r or n < k);
\left[{n \atop r}\right]_{r} = \frac{(n − 1)!}{(r − 1)!},  (r ≤ n);
\left[{n \atop n}\right]_{r} = 1,  (r ≤ n).

Theorem 2.16 ([2, §6.9]). The generating function of unsigned r-restricted Stirling numbers of the first kind is

∑_{k=0}^{n} \left[{n \atop k}\right]_{r} · x^{k} = \begin{cases}x^{r}(x + r)(x + r + 1) ⋯ (x + n − 1) & if 1 ≤ r ≤ n; \\ 0 & otherwise. \end{cases}

Definition 2.17. The r-restricted Stirling number of the second kind, denoted by \left\{{n \atop k}\right\}_{r}, is the number of ways to partition the set {1, 2, …, n} into k nonempty disjoint subsets with the restriction that the numbers 1, 2, …, r belong to distinct subsets. The case r = 1 gives the usual Stirling numbers of the second kind.

Claim 2.18. r-restricted Stirling numbers of the second kind satisfy the same recurrence relation as Stirling numbers of the second kind, except for the initial conditions.

\left\{{n \atop k}\right\}_{r} = k · \left\{{n − 1 \atop k}\right\}_{r} + \left\{{n − 1 \atop k − 1}\right\}_{r}, (r < k < n),

with the following initial conditions:

\left\{{n \atop k}\right\}_{r} = 0,  (k < r or n < k);
\left\{{n \atop k}\right\}_{r} = r^{n−r},  (r ≤ n);
\left\{{n \atop n}\right\}_{r} = 1,  (r ≤ n).

Theorem 2.19 ([2, §6.10]). The generating function of r-restricted Stirling numbers of the second kind is

∑_{n=0}^{∞} \left\{{n \atop k}\right\}_{r} · x^{n} = \begin{cases}\frac{x^{k}}{(1−rx)(1−(r+1)x)···(1−kx)}, & if 1 ≤ r ≤ k; \\ 0, & otherwise. \end{cases}

Restricted Stirling numbers of the first and second kind satisfy the same orthogonality relation as the usual (unsigned) Stirling numbers, as described in the following theorem.

Theorem 2.20 ([2, §4.5]). We have

∑_{k=0}^{n} \left[{n \atop k}\right]_{r} · \left\{{k \atop m}\right\}_{r} · (−1)^{k} = \begin{cases}(−1)^{n} · δ_{m,n}, & if r ≤ m ≤ n; \\ 0, & otherwise. \end{cases}

2.4. Harmonic Numbers.

Definition 2.21. The n-th harmonic number, denoted by H_{n}, is the sum of the reciprocals of the first n positive integers:

H_{n} = 1 + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n}.

Definition 2.22. The generalized n-th harmonic number of order m, denoted by H_{n,m}, is

H_{n,m} = 1 + \frac{1}{2^{m}} + \frac{1}{3^{m}} + ⋯ + \frac{1}{n^{m}} .

3. Main Results

In this section we present the main results of this paper. Details and proofs will be given in Sections 4–8.

Let

a_{ij} := s_{1}t_{ij} = (12)(ij), (1 ≤ i < j ≤ n).

The set of A-transpositions

T (A_{n}) := {a_{ij} | 1 ≤ i < j ≤ n}

generates the alternating group on n letters. The length of an element v ∈ A_{n} can be naturally defined with respect to the above generators:

ℓ_{T (A_{n})}(v) = min{k ≥ 0 | v = v_{1} ⋯ v_{k}, v_{i} ∈ T (A_{n})}.

Notation 3.1. Denote by a(n, m) the number of elements of length m in A_{n}.

Our first result is a Stirling-type recursion for a(n, m).

Proposition 3.2 (Corollary 5.4).

a(n, m) = (n − 1) · a(n − 1, m − 1) + a(n − 1, m), (0 < m < n),

with initial conditions a(n, 0) = 1 for n ≥ 0, and a(n, n) = 0 for n > 0.

The following result relates the length function to the cycle number.

Proposition 3.3 (Corollary 6.4). Let v ∈ A_{n}, n ≥ 2, Then

ℓ_{T (A_{n})}(v) = \begin{cases}n − cyc(v) & if 1,2 are in different cycles of v; \\ n − cyc(v) − 1 & if 1,2 in the same cycle of v. \end{cases}

(For n ≤ 2, A_{n} contains only the identity permutation.)

Note that the length function ℓ_{T (A_{n})}(v) is odd if and only if 1, 2 are in the same cycle in v (see Corollary 6.2).

Proposition 3.4 (Theorem 7.2). For n ≥ 2, we have

∑_{v∈A_{n}} x^{ℓ_{T (An)}(v)} = ∑_{k=0}^{n} a(n, k) · x^{k}

= (1 + 2x)(1 + 3x) ⋯ (1 + (n − 1)x)

= ∏_{t=2}^{n−1}(1 + tx).

Theorem 3.5 (Theorem 8.4). The expected value of ℓ_{T (A_{n})} is

E[ℓ_{T (A_{n})}] = n − H_{n} − \frac{1}{2},

and its variance is

V ar[ℓ_{T (A_{n})}] = H_{n} − H_{n,2} − \frac{1}{4}.

Finally, we discuss a certain generalization of Stirling numbers and relate it to our statistic a(n, k). The generalization discussed is Broder’s restricted Stirling numbers [2], see Definitions 2.13 and 2.17. The connection was initially established using the On-Line Encyclopedia of Integer Sequences [11].

Proposition 3.6 (Theorem 9.2). For 0 ≤ k ≤ n − 2, we have

a(n, k) = \left[{n \atop n − k}\right]_{2}

4. The A Canonical Presentation

In this section we consider a canonical presentation of elements in A_{n} by the corresponding s_{1}t_{ij} generators.

4.1. A Generating Set for A_{n}. We let

a_{ij} := s_{1}t_{ij} = (12)(ij), (1 ≤ i < j ≤ n).

Denote by T (A_{n}) := {a_{ij} | 1 ≤ i < j ≤ n} the set of A-transpositions.

Definition 4.1. For n ≥ 3 define the following subset of permutations in A_{n}:

R_{n} = {(12)(in) | 1 ≤ i < n} ∪ {e}.

Note 4.2. R_{n} is a subset of T (A_{n}), R_{n} = (T (A_{n}) \ T (A_{n−1})) ∪ {e}.

Theorem 4.3. Let v ∈ A_{n}, n ≥ 3. Then there exist unique elements v_{i} ∈ R_{i}, 3 ≤ i ≤ n, such that v = v_{3} ⋯ v_{n}. Call it the canonical presentation of v.

Lemma 4.4. Let k ∈ ℕ, m_{1}, ⋯, m_{2k} ∈ {1, ⋯, n} be distinct and let

v = (m_{1}m_{2}) ⋯ (m_{2k−1}m_{2k}) ∈ S_{n}, m_{1} ≠ m_{2}, ⋯, m_{2k−1} ≠ m_{2k}

be a product of transpositions. Then, for every 1 ≤ i ≤ 2k, there exists a presentation of v as a product of transpositions in which m_{i} appears in the rightmost factor only.

Proof of Lemma 4.4. We provide a proof for i = 1. First we prove the assertion for the case k = 2, i.e., for the case where v is a product of two cycles. If {m_{1}, m_{2}}∩{m_{3}, m_{4}} = ∅, then v = (m_{1}m_{2})(m_{3}m_{4}) = (m_{3}m_{4})(m_{1}m_{2}), as required. Else, if m_{2} = m_{3}, then v = (m_{1}m_{2})(m_{2}m_{4}) = (m_{1}m_{2}m_{4}) = (m_{2}m_{4}m_{1}) = (m_{2}m_{4})(m_{4}m_{1}), as required. The case m_{2} = m_{4} is similar. Else, if m_{1} = m_{3}, then v = (m_{1}m_{2})(m_{1}m_{4}) = (m_{2}m_{1}m_{4}) = (m_{4}m_{2}m_{1}) = (m_{4}m_{2})(m_{2}m_{1}), as required. The case m_{1} = m_{4} is similar. If m_{1} = m_{3} and m_{2} = m_{4}, then v is the identity, thus its cycles are disjoint and commute with each other. All possible cases were checked and thus we are finished.

Now we turn to the general case, where v is a product of k cycles. By induction the lemma applies also for this case as we can perform the same steps described in the simple case repeatedly until the desired form of v is achieved. □

Proof of Theorem 4.3. We proceed by induction on n. For n = 3, we have

A_{3} = {(12)(13), (12)(23), e} = R_{3},

and thus the claim holds. Now assume that each w ∈ A_{n−1}, n ≥ 4, has a unique canonical presentation w = w_{3} ⋯ w_{n−1}, w_{i} ∈ R_{i}. We will show that, if v ∈ A_{n}, then v has a unique canonical presentation as well. This follows actually from Lemma 4.4. We assume that v ∈ A_{n} \ A_{n−1}, otherwise the proof follows immediately from the induction hypothesis. First we apply Lemma 4.4 to v to get n in the rightmost factor only. We have v = g_{1} ⋯ g_{k} = g_{1} ⋯ g_{k−1}(12)(12)g_{k} with n in g_{k} only. Now, since g_{1} ⋯ g_{k−1}(12) ∈ A_{n−1}, according to the induction hypothesis it has a unique canonical presentation, say w_{1} ⋯ w_{t}. Thus we have v = w_{1} ⋯ w_{t}(12)g_{k} and this is unique canonical presentation for v, because (12)g_{k} is unique. □

By Theorem 4.3, we obtain the following corollary.

Corollary 4.5. The set of A-transpositions, T (A_{n}) := {a_{ij} | 1 ≤ i < j ≤ n}, generates the alternating group on n letters.

Definition 4.6. For v ∈ A_{n} with the canonical presentation v = v_{3} ⋯ v_{n}, let

ℓ̂(v) = #{i | v_{i} ≠ e}.

Theorem 4.7. For all v ∈ A_{n},

ℓ̂(v) = ℓ_{T (A_{n})}(v).

In other words the length of the canonical presentation coincides with the natural length with respect to the generating set T (A_{n}).

Proof of Theorem 4.7. It suffices to show that, if ℓ̂(v) = r, then v can not be presented as a product of less than r generators. For n = 3 it was shown that A_{3} = R_{3}, thus all the elements in A_{3} are of length 1, except for the identity e whose length is 0. For n > 3 denote the length of the canonical presentation of v by ℓ̂(v) = r. Denote the shortest presentation of v by v_{2} = b_{1} ⋯ b_{k}, b_{i} ∈ T (A_{n}). Then ℓ_{T (A_{n})}(v) = k. Now we can apply the corollary of Lemma 4.4 described in the proof of Theorem 4.3 to turn v_{2} into a canonical presentation of v, say v′_{2}, with ℓ_{T (A_{n})}(v′_{2}) = k. Since v_{1} and v′_{2} are two canonical presentations of the same permutation, according to Theorem 4.2 they are actually the same presentation, i.e., r = k. □

In the rest of this paper, we explore the natural length function with respect to T (A_{n}). For this purpose, we use the equivalence to the length of the canonical expression proved above, as needed.

5. Counting Permutations in A_{n}

In this section we study the number of permutations in A_{n} of a given length with respect to T (A_{n}). A Stirling-type recurrence relation for this statistic is described.

Definition 5.1. Let

A(n, m) = {v ∈ A_{n} | ℓ_{T (A_{n})}(v) = m}

and

a(n, m) = |A(n, m)|.

Proposition 5.2. For n ≥ 3,

a(n, 1) = a(n − 1, 1) + n − 1.

Proof of Proposition 5.2. By Definition 4.1, R_{n} \ {e} is the subset of generators of A_{n} that do not belong to A_{n−1}; namely R_{n} \ {e} = (T (A_{n}) \ T (A_{n−1})) = {(12)(nj) | 1 ≤ j < n}. These are the generators that involve the new letter n. Thus |R_{n}| = n.

For every n, A(n, 1) = T (A_{n}), and since T (A_{n}) = T (A_{n−1}) ∪ (R_{n} \ {e}) (this is a disjoint union), we conclude a(n, 1) = a(n − 1, 1) + n − 1. □

Theorem 5.3. We have

A(n, m) = A(n − 1, m − 1) · R_{n} ∪ A(n − 1, m),

where the union on the right-hand side is a disjoint union.

Proof of Proposition 5.3. We prove the claim by two-sided set inclusion. First we prove that A(n, m) ⊇ A(n − 1, m − 1) · R_{n} ∪ A(n − 1, m). Note that the right-hand side of the equation is a disjoint union, according to the properties of the A_{n} canonical presentation.

On the other hand, we also have A(n − 1, m) ⊆ A(n, m) because a permutation v of length m in A_{n−1} is also of length m in A_{n}. The new generators in A_{n} can not shorten the length of v because they involve the new letter n which is a fixed point in v.

Let v ∈ A(n−1, m−1), and consider its canonical presentation. Multiply v by w ∈ R_{n} from the right side to have the canonical presentation of a permutation v · w ∈ A_{n} of length m − 1 + 1 = m, i.e., v · w ∈ A(n, m).

We showed that each part of the union on the right-hand side of the equation is contained in the left-hand side, therefore the union itself is also contained in the lefthand side. This proves the first inclusion. Now we show that A(n, m) ⊆ A(n − 1, m − 1) · R_{n} ∪ A(n − 1, m). Let v ∈ A(n, m).

(1) If n is a fixed point in v, then v ∈ A(n − 1, m) with the same canonical presentation.

(2) Otherwise, n is not a fixed point, and therefore the canonical presentation of v reads as follows:

v = \underbrace{r_{1} ⋯ r_{k−1}}_{∈ A(n − 1, m − 1)} · \underbrace{r_{n}}_{∈ (R_{n} \ \{e\})}, r_{i} ∈ R_{i}, 1 ≤ i ≤ n.

We have r_{n} ∈ R_{n} \ {e} because n is not a fixed point and must appear in the presentation. The above canonical presentation of v establishes the required inclusion.

□

From Proposition 5.2 and Theorem 5.3 we can conclude the following relation.

Corollary 5.4. For 1 ≤ m ≤ n − 2, we have

a(n, m) = a(n − 1, m − 1) · (n − 1) + a(n − 1, m).

6. Relation between Length and Cycle Number

In this section we show that the length ℓ_{T (A_{n})}(·) and the number of cycles cyc(·) are strongly related statistics on A_{n}.

Observation 6.1. For n ≥ 3, and v ∈ A(n, 1), cyc(v) = n − 2.

In other words, the number of cycles in a generator of A_{n} is n − 2.

Proof of Observation 6.1. Every generator v ∈ A_{n} is of the form (12)(in), where 1 ≤ i < n. If i = 1, or i = 2, then v has one cycle of length 3 and n − 3 cycles of length 1 (fixed points). This sums to n − 2 cycles. Otherwise i > 2, and then v has two cycles of length 2 and n − 4 more cycles of length 1. This also sums to n − 2 cycles in v. □

Corollary 6.2. For every n ≥ 2 and v ∈ A_{n}, the letters 1, 2 are in the same cycle in v if and only if ℓ_{T (A_{n})}(v) is odd.

Proof of Corollary 6.2. If v ∈ A_{n} is of length one, 1, 2 share the same cycle since the structure of a generator is (12)(ij). In length two, 1, 2 appear in different cycles because of the multiplication process described in the proof of Theorem 5.3. For length three, 1, 2 are in the same cycle according to the same process, and so on and so forth. For odd length, the letters 1, 2 are in the same cycle, and for even length they are in different cycles. This proves both implications of the equivalence. □

Theorem 6.3. For n ≥ 3 and v ∈ A_{n}, we have

cyc(v) = \begin{cases}n − ℓ_{T (A_{n})}(v) & if ℓ_{T (A_{n})}(v) is even, \\ n − ℓ_{T (A_{n})}(v) − 1 & if ℓ_{T (A_{n})}(v) is odd. \end{cases}

Proof of Theorem 6.3. We proceed by induction on n. For n = 3, we have

A_{3} = {(12)(13) = (213), (12)(23) = (123), e = (1)(2)(3)},

and the claim follows. Assume that, for each v ∈ A_{n}, we have

cyc(v) = \begin{cases}n − ℓ_{T (A_{n})}(v) & if ℓ_{T (A_{n})}(v) is even, \\ n − ℓ_{T (A_{n})}(v) − 1 & if ℓ_{T (A_{n})}(v) is odd. \end{cases}

Now, w ∈ A_{n+1} can be obtained in two ways by Theorem 5.3. First, by multiplying v ∈ A_{n} by r ∈ R_{n+1}, and secondly by adding the letter n + 1 as fixed point to some v ∈ A_{n}. Both cases will be analyzed.

(1) In this case w = vr for v ∈ A_{n}, r ∈ R_{n+1}. If ℓ_{T (A_{n})}(v) is even, then, by Corollary 6.2, the letters 1, 2 are in different cycles in v, and therefore they will be in the same cycle in w, thus cyc(w) = cyc(v)−1 (see Theorem 5.3 for details). The length of w is ℓ_{T (A_{n+1})}(w) = ℓ_{T (A_{n})}(v) + 1. By the induction hypothesis,

cyc(w) = cyc(v) − 1 = n − ℓ_{T (A_{n})}(v) − 1 = n − ℓ_{T (A_{n+1})}(w) = (n + 1) − ℓ_{T (A_{n+1})}(w) − 1,

as required. If ℓ_{T (A_{n})}(v) is odd, then, by Corollary 6.2 and Theorem 5.3, cyc(w) = cyc(v) + 1 and ℓ_{T (A_{n+1})}(w) = ℓ_{T (A_{n})}(v) + 1. By the induction hypothesis,

cyc(w) = cyc(v)+1 = n−ℓ_{T (A_{n})}(v)−1+1 = n−ℓ_{T (A_{n+1})}(w)+1 = (n+1)−ℓ_{T (A_{n+1})}(w),

as required.

(2) In this case w = v for some v ∈ A_{n}, where the letter n + 1 is a fixed point in w. Here, cyc(w) = cyc(v) + 1 and ℓ_{T (A_{n+1})}(w) = ℓ_{T (A_{n})}(v). If ℓ_{T (A_{n})}(v) is even,

cyc(w) = cyc(v) + 1 = n − ℓ_{T (A_{n})}(v) + 1 = n − ℓ_{T (A_{n+1})}(w) + 1 = (n + 1) − ℓ_{T (A_{n+1})}(w),

as required, and, if ℓ_{T (A_{n})}(v) is odd,

cyc(w) = cyc(v)+1 = n−ℓ_{T (A_{n})}(v)−1+1 = n−ℓ_{T (A_{n+1})}(w) = (n+1)−ℓ_{T (A_{n+1})}(w)−1,

as required. In both cases the relation between cycle number and length holds, therefore the theorem is proved. □

Corollary 6.2 and Theorem 6.3 imply the following relation.

Corollary 6.4. Let v ∈ A_{n}.

(6.1)  ℓ_{T (A_{n})}(v) = \begin{cases}n − cyc(v) & if 1, 2 are in different cycles of v, \\ n − cyc(v) − 1 & if 1, 2 are in the same cycle of v. \end{cases}

Equation (6.1) provides a simple way to find the length of a permutation v given as a product of disjoint cycles.

Theorem 6.3 implies that all the permutations of the same length in A_{n} have the same number of cycles.

Definition 6.5.

m(n, k) = number of cycles in a permutation v ∈ A_{n} of length ℓ_{T (A_{n})}(v) = k.

7. Generating Function of Length in A_{n}

An explicit formula for the generating function of the length in A_{n}, with respect to the generating set T (A_{n}), is given in this section.

According to Theorem 6.3, the number m(n, k), of cycles in a permutation v ∈ A_{n} of length k, can be calculated by the following formula:

(7.1)  m(n, k) = \begin{cases}n − k, & if k is even, \\ n − k − 1, & if k is odd. \end{cases}

A well known result in S_{n} is

(7.2)  m(n, k) = n − k

where the length k is taken with respect to the generating set T = {(ij) | 1 ≤ i < j ≤ n}, that is, all the transpositions in S_{n}. Since the number of cycles in a permutation is independent of the generating set, from Equations (7.1) and (7.2) we can conclude that, for v ∈ A_{n}, we have

(7.3)  ℓ_{T} (v) = \begin{cases}ℓ_{T (A_{n})}(v), & if ℓ_{T (A_{n})}(v) is even, \\ ℓ_{T (A_{n})}(v) + 1, & if ℓ_{T (A_{n})}(v) is odd, \end{cases}

where ℓ_{T} (v) is the length with respect to T. Note that, in each of the cases, ℓ_{T} (v) is even, which complies with the fact that we deal with even permutations in S_{n}. From Equation (7.3) we can conclude that the number of permutations of even length k in S_{n} equals the sum of the number of permutations of lengths k and k − 1 in A_{n}. Since the number of permutations of length k in S_{n} with respect to T is the unsigned Stirling number of the first kind c(n, n − k), we can deduce the following equation for even k:

(7.4)  c(n, n − k) = a(n, k) + a(n, k − 1).

A further consequence is the following.

Claim 7.1. Equation (7.4) holds also for odd k ∈ ℕ.

Proof of Claim 7.1. Let k + 1 be even. Using the recursive relation of Stirling numbers, we can expand the left-hand of Equation (7.4) to obtain

c(n, n − (k + 1)) = c(n − 1, n − (k + 1) − 1) + c(n − 1, n − (k + 1)) · (n − 1)
= c(n − 1, n − 1 − (k + 1)) + c(n − 1, n − 1 − ((k + 1) − 1)) · (n − 1)
= c(n − 1, n − k − 2) + c(n − 1, n − 1 − k) · (n − 1).

Rearrangement of terms gives the following result:

(n − 1) · c(n − 1, n − 1 − k) = c(n, n − k − 1) − c(n − 1, n − k − 2).

The expressions at the right-hand side represent even length, so we can use Equation (7.4) and Conclusion 5.4 to obtain the desired result:

(n − 1)·c(n − 1, n − 1 − (k − 1)) = a(n, k) + a(n, k − 1) − a(n − 1, k) − a(n − 1, k − 1)
= a(n − 1, k − 1) · (n − 1) + a(n − 1, k) + a(n − 1, k − 2) · (n − 1)
+ a(n − 1, k − 1) − a(n − 1, k) − a(n − 1, k − 1)
= a(n − 1, k − 1) · (n − 1) + a(n − 1, k − 2) · (n − 1).

Dividing both sides by (n − 1), we deduce, for odd k, the equation

c(n − 1, n − 1 − k) = a(n − 1, k) + a(n − 1, k − 1).
□

The following generating function for unsigned Stirling numbers of the first kind is well known [4, pp. 213]:

(7.5)  ∑_{k=1}^{n} c(n, k) · x^{n−k} = (1 + x)(1 + 2x) ⋯ (1 + (n − 1)x).

By Equation (7.4), we have

∑_{k=0}^{n} c(n, n − k) · x^{k} = ∑_{k=0}^{n} a(n, k) · x^{k} + ∑_{k=0}^{n} a(n, k − 1) · x^{k}.

Using Equation (7.5) for the left-hand side, we obtain

(1 + x)(1 + 2x) ⋯ (1 + (n − 1)x)

= ∑_{k=0}^{n} a(n, k) · x^{k} + x · ∑_{k=0}^{n} a(n, k − 1) · x^{k−1} = (1 + x) · ∑_{k=0}^{n} a(n, k) · x^{k}.

Dividing both sides by (x + 1), we get the generating function of length in A_{n} with respect to the generating set T (A_{n}).

Theorem 7.2. We have

(7.6)  ∑_{k=0}^{n} a(n, k) · x^{k} = (1 + 2x)(1 + 3x) ⋯ (1 + (n − 1)x)

= ∏_{t=2}^{n−1}(1 + tx).

8. Expectation and Variance

In this section, the expectation and variance of the length function in A_{n} are studied.

Definition 8.1. Let A be a finite set, and s : A → ℝ a real function. The expectation of s is defined by

E[s] := \frac{1}{|A|} ∑_{a∈A} s(a),

and the variance of s is defined by

V ar[s] := E[s^{2}] − E^{2}[s].

Given a generating function of s, we can use it to calculate these statistics. The following formulas are well-known.

Proposition 8.2. Let

F_{s}(x) := ∑_{a∈A} x^{s(a)}

be the generating function of s. Then

E[s] = \frac{1}{|A|}F′_{s}(x)|_{x=1},

and

V ar[s] = \frac{1}{|A|}[F′′_{s}(x) + F′_{s}(x) − \frac{1}{|A|}(F′_{s}(x))^{2}]|_{x=1}.

Definition 8.3. We recall the definitions of harmonic numbers (see Definitions 2.21 and 2.22),

H_{n} = 1 + \frac{1}{2} + \frac{1}{3} + ⋯ + \frac{1}{n}

and generalized harmonic numbers,

H_{n,m} = 1 + \frac{1}{2^{m}} + \frac{1}{3^{m}} + ⋯ + \frac{1}{n^{m}}

Theorem 8.4. The expected value of ℓ_{T (A_{n})} is

E[ℓ_{T (A_{n})}] = n − H_{n} − \frac{1}{2},

and its variance is

V ar[ℓ_{T (A_{n})}] = H_{n} − H_{n,2} − \frac{1}{4}.

Proof of Theorem 8.4. Compute the derivative of the generating function with respect to length (see Theorem 7.2) as a product of functions:

( ∏_{t=2}^{n−1}(1 + tx))′ = ( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx}.

Thus, by Proposition 8.2,

E[ℓ_{T (A_{n})}] = \frac{1}{|A_{n}|}( ∏_{t=2}^{n−1}(1+tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx}|_{x=1} = \frac{2}{n!} · \frac{n!}{2}(n−2−∑_{t=2}^{n−1} \frac{1}{1 + t}) = n−H_{n}− \frac{1}{2}.

For the variance, we have

( ∏_{t=2}^{n−1}(1 + tx))′′ = [( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx}]′

= ( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx} ∑_{t=2}^{n−1} \frac{t}{1 + tx} + ( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{−t^{2}}{(1 + tx)^{2}} ,

and thus

V ar[ℓ_{T (A_{n})}] = \frac{1}{|A_{n}|}[( ∏_{t=2}^{n−1}(1 + tx))′′ + ( ∏_{t=2}^{n−1}(1 + tx))′ − \frac{1}{|A_{n}|}(( ∏_{t=2}^{n−1}(1 + tx))′)^{2}]_{x=1}

= \frac{2}{n!}[( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx} ∑_{t=2}^{n−1} \frac{t}{1 + tx} + ( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{−t^{2}}{(1 + tx)^{2}}

+ ( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx} − \frac{2}{n!}(( ∏_{t=2}^{n−1}(1 + tx)) ∑_{t=2}^{n−1} \frac{t}{1 + tx})^{2}]_{x=1}

= \frac{2}{n!}[\frac{n!}{2}(n − H_{n} − \frac{1}{2})^{2} + \frac{n!}{2}(2H_{n} + \frac{1}{4} − n − H_{n,2}) + \frac{n!}{2} (n − H_{n} − \frac{1}{2})

− \frac{2}{n!}(\frac{n!}{2}(n − H_{n} − \frac{1}{2})^{2}]

= H_{n} − H_{n,2} − \frac{1}{4}.

□

9. Connection with Restricted Stirling Numbers

This section discusses the relation between our statistic a(n, m) and 2-restricted Stirling numbers of the first kind (see Broder [2, §1]). This relation was initially observed using the On-Line Encyclopedia of Integer Sequences [11].

Recall Definition 2.13 of the r-restricted Stirling numbers of the first kind, \left[{n \atop k}\right]_{r}. We shall use it with r = 2. The number \left[{n \atop k}\right]_{1} = c(n, k) is the usual (unrestricted) Stirling number of the first kind.

Claim 9.1 (See Broder [2, § 3, Thm. 3] for a generalized version). We have

c(n, k) = \left[{n \atop k}\right]_{2} + \left[{n \atop k + 1}\right]_{2}.

Theorem 9.2. The number of permutations in A_{n} of length ℓ_{T (A_{n})}(·) = k is equal to a corresponding 2-restricted Stirling number. Namely,

a(n, k) = \left[{n \atop n − k}\right]_{2}, (0 ≤ k ≤ n − 2).

We give two proofs to Theorem 9.2. The first proof is algebraic, and the second consists of a direct bijection between two sets.

Proof of Theorem 9.2. From Claims 9.1 and 7.1 we can deduce the following equation:

a(n, k) + a(n, k − 1) = \left[{n \atop n − k}\right]_{2} + \left[{n \atop n − k + 1}\right]_{2}, (0 ≤ k ≤ n − 1).

Now the theorem can be proved by induction on k. By assumption, n ≥ 2. For k = 0, we have a(n, 0) = 1 and \left[{n \atop n}\right]_{2} = 1. The claim a(n, k) = \left[{n \atop n−k}\right]_{2} now follows by induction on k. □

Definition 9.3. Let

P (n, k) = {v ∈ S_{n} | cyc(v) = k and 1, 2 are in different cycles in v}.

We now present an explicit bijection between the sets A(n, k) and P (n, n − k).

A Bijective Proof of Theorem 9.2. Define a map f : A(n, k) → P (n, n − k) by

f(v) = \begin{cases}v & if ℓ_{T (A_{n})}(v) is even, \\ (1, 2)v & if ℓ_{T (A_{n})}(v) is odd. \end{cases}

We will show that f is one-to-one and onto P (n, n − k).

(1) Consider v_{1}, v_{2} ∈ A(n, k) with f(v_{1}) = f(v_{2}). If v_{1}, v_{2} are both of even length, or both of odd length, then, by the definition of f, v_{1} = v_{2}. If v_{1} is of even length and v_{2} is of odd length or vice versa, then, by the definition of f and the fact that f(v_{1}) = f(v_{2}), v_{1} = (1, 2)v_{2}. This contradicts the assumption that v_{1}, v_{2} ∈ A(n, k), and is therefore impossible. Since only the first case is feasible, v_{1} = v_{2} and f is one-to-one.

(2) Consider w ∈ P (n, n − k). The length of w in S_{n}, ℓ_{T} (w), is k. If k is even, then w ∈ A_{n}. By Corollaries 6.2 and 6.4, we have ℓ_{T (A_{n})}(w) = k, therefore w ∈ A(n, k) and f(w) = w. If k is odd, then (1, 2)w ∈ A_{n}. By Corollaries 6.2 and 6.4, we have ℓ_{T (A_{n})}((1, 2)w) = k, therefore (1, 2)w ∈ A(n, k) and f((1, 2)w) = w. This proves that f is onto P (n, n − k).

□

Acknowledgements

I wish to thank my supervisors Prof. Ron M. Adin and Prof. Yuval Roichman for their professional guidance, patience and for introducing me to the fascinating world of combinatorial research.

I want to thank my parents for their love and support. I would like to thank all those who helped me and supported me during this work.

References

[1] R. M. Adin, F. Brenti and Y. Roichman, Descent numbers and major indices for the hyperoctahedral group. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA 2000). Adv. in Appl. Math. 27 (2001), 210–224.

[2] A. Z. Broder, The r-Stirling numbers. Discrete Math. 49 (1984), 241–259

[3] F. Brenti, V. Reiner and Y. Roichman, Alternating subgroups of Coxeter groups. J. Comb. Theory, Series A 115 (2008), 845–877.

[4] L. Comtet, Advanced Combinatorics. D. Reidel Publishing Company, Dordrecht, Holland (1974).

[5] J. E. Humphreys, Reflection Groups and Coxeter Groups. Cambridge Studies in Advanced Mathematics. 29. Cambridge Univ. Press, Cambridge, 1990.

[6] P. A. MacMahon, Combinatory Analysis I-II. Cambridge Univ. Press, London/New-York, 1916. (Reprinted by Chelsea, New-York, 1960.)

[7] H. Mitsuhashi, The q-analogue of the alternating group and its representations. J. Algebra 240 (2001), 535–558.

[8] A. Regev and Y. Roichman, Permutation statistics on the alternating group. Adv. in Appl. Math. 33 (2004), 676–709.

[9] R. P. Stanley, Enumerative Combinatorics, vol. 1. Cambridge Univ. Press, 1998.

[10] A. Vershik and M. Vsemirnov, The local stationary presentation of the alternating groups and the normal form. J. Algebra 319 (2008), 4222–4229.

[11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, electronically available at

    http://www.research.att.com/~njas/sequences/Seis.html;

Sequences A001705, A143491, A143494.