Séminaire Lotharingien de Combinatoire 85 (2021), Article B85b

GENERATING FUNCTIONS OF PERMUTATIONS WITH RESPECT TO THEIR ALTERNATING RUNS

MIKLÓS BÓNA

Abstract. We present a short, direct proof of the fact that the generating function of all permutations of a fixed length n ≥ 4 with respect to the number of their alternating runs is divisible by (1 + z)^{m}, where m = ⌊(n − 2)/2⌋.

1. Introduction

Let p = p_{1}p_{2} ⋯ p_{n} be a permutation. For an index i ∈ [2, n − 1], we say that p changes directions at i if p_{i−1} < p_{i} > p_{i+1} or p_{i−1} > p_{i} < p_{i+1}. Furthermore, we say that p has k alternating runs if p changes directions a total of k − 1 times.

Let run(p) be the number of alternating runs of p, and let

R_{n}(z) = ∑_{p} z^{run(p)},

where the sum is taken over all permutations of length n. In this note, we prove that, for n ≥ 4, the polynomial R_{n}(z) is divisible by a high power of (1 + z), namely by (1 + z)^{m}, where m = ⌊(n − 2)/2⌋.

This result was known before, by an analytic proof given by Herbert Wilf [5] (which can also be found as Theorem 1.42 in [2] on page 31) that was based on the relation between the Eulerian polynomials and R_{n}(z), and also by an induction proof by Richard Ehrenborg and the present author [1] that touched upon Eulerian polynomials. However, in this paper, we provide a direct, non-inductive proof. This proof differs from the previous ones in that it is algebraic (it uses enumeration under group action), and it shows a clear reason for the high multiplicity of −1 as a root of R_{n}(z).

2. A group action on permutations

Let p = p_{1}p_{2} ⋯ p_{n} be a permutation. The complement of p is the permutation \overline{p} = n + 1 − p_{1} n + 1 − p_{2} ⋯ n + 1 − p_{n}. For instance, the complement of 425613 is 352164. It is clear that p and \overline{p} have the same number of alternating runs, since the diagram of \overline{p} is just the diagram of p reflected through a horizontal line. In what follows, we will say flipped instead of reflected through a horizontal line. Note that this symmetry implies that all coefficients of R_{n}(z) are even for n ≥ 2.

Date: May 31, 2021.

Let s be a string of entries in p that are in consecutive positions. Let S be set of entries that occur in s, in other words, the underlying set of s. Then the complement of s relative to S is the string obtained from s so that, for each j, the jth smallest entry of S is replaced by the jth largest entry of S. For example, if s = 24783, then the complement of s relative to its underlying set S is 84327.

We will use a similar notion for sets. Let T ⊆ U be finite sets. Let T = {t_{1}, t_{2}, …, t_{j}}, where the t_{i} are listed in increasing order. Let us assume that t_{i} is the a_{i}th smallest element of U. Then the vertical complement of T with respect to U is the set consisting of the a_{i}th largest elements of U, for all i. For instance, if T = {1, 4, 6}, and U = {1, 2, 3, 4, 6, 8, 9}, then the vertical complement of T with respect to U is {3, 4, 9}. Indeed, T consists of the first, fourth, and fifth smallest elements of U, so its vertical complement with respect to U consists of the first, fourth, and fifth largest elements of U.

Definition 2.1. For 1 ≤ i ≤ n, let c_{i} be the transformation on the set of all permutations p = p_{1}p_{2} ⋯ p_{n} that leaves the string p_{1}p_{2} ⋯ p_{i−1} unchanged, and replaces the string p_{i}p_{i+1} ⋯ p_{n} by its complement relative to its underlying set.

Note that c_{1}(p) = \overline{p} and c_{n}(p) = p for all p.

Example 2.2. Let p = 315462. Then c_{3}(p) = 314526, while c_{5}(p) = 315426.

Proposition 2.3. Let n ≥ 4, and let 3 ≤ i ≤ n − 1. Let p be any permutation of length n. Then one of p and c_{i}(p) has exactly one more alternating run than the other.

Proof. As c_{i} does not change the number of runs of the string p_{1}p_{2} ⋯ p_{i−1} or the number of runs of the string p_{i}p_{i+1} ⋯ p_{n} and its image, all changes occur within the four-element string p_{i−2}p_{i−1}p_{i}p_{i+1}. There are only 24 possibilities for the pattern of these four entries, and it is routine to verify the statement for each of the possible 12 pairs. In fact, checking the six pairs in which p_{i−2} < p_{i−1} is sufficient, for symmetry reasons. □

It follows immediately from the proposition that z^{run(p)} + z^{run(c_{i}(p))} is divisible by 1 + z.

The following lemma is crucial for our purposes.

Lemma 2.4. Let 1 ≤ i ≤ j − 2 ≤ n − 2. Then, for all permutations p of length n, the identity c_{i}(c_{j}(p)) = c_{j}(c_{i}(p)) holds.

Proof. Neither c_{i} nor c_{j} acts on any part of the initial segment p_{1}p_{2} ⋯ p_{i−1}, so that segment, unchanged, will start both c_{i}(c_{j}(p)) and c_{j}(c_{i}(p)). The ending segment p_{j}p_{j+1} ⋯ p_{n} gets flipped twice by both c_{i}c_{j} and c_{j}c_{i}, so in the end, the pattern of the last n − j + 1 entries will be the same in c_{i}(c_{j}(p)) and c_{j}(c_{i}(p)), because in both permutations it will be the same pattern as it was in p. The middle segment p_{i}p_{i+1} ⋯ p_{j} will get flipped once by both c_{i}c_{j} and c_{j}c_{i}, so on both sides the pattern of entries in positions i, i + 1, …, j will be the complement of the pattern of p_{i}p_{i+1} ⋯ p_{j}.

Finally, the set of entries in the last n − j + 1 positions is the same in both c_{i}(c_{j}(p)) and c_{j}(c_{i}(p)), since both sets are equal to the vertical complement of the set {p_{j}, p_{j+1}, …, p_{n}} with respect to the set {p_{i}, p_{j+1}, …, p_{n}}. □

Note that c_{i}(c_{j}(p)) ≠ p, since the segment p_{i} ⋯ p_{j−1} is of length at least two, and gets flipped at least once.

Example 2.5. Continuing Example 2.2, we get that c_{3}(c_{5}(315462)) = c_{5}(c_{3}(315462)) = 314562.

Now let n ≥ 4 be any integer. If n is even, let

C_{n} = {c_{3}, c_{5}, c_{7}, …, c_{n−1}}.

If n is odd, let

C_{n} = {c_{3}, c_{5}, c_{7}, …, c_{n−2}}.

In both cases, C_{n} consists of m = ⌊(n − 2)/2⌋ operators. Each of these operators are involutions, and, by Lemma 2.4, they pairwise commute. No element of C_{n} can be generated by the other elements of C_{n}. Therefore, the elements of C_{n} define a group G_{m} ≅ ℤ_{2}^{m} that acts on the set of all permutations of length n. Note that the action of the individual c_{i} on the set of all permutations of length n is independent in the following sense. If p is a permutation and c_{i}(p) has one more alternating run than p, then c_{j}(c_{i}(p)) also has one more alternating run than c_{j}(p).

The action of G_{m} on the set of all permutations of length n creates orbits of size 2^{m}.

Lemma 2.6. Let A be any orbit of G_{m} on the set of all permutations of length n. Then the equality

∑_{p∈A} z^{run(p)} = z^{a}(1 + z)^{m}

holds, where a is a nonnegative integer.

Proof. Let p ∈ A. Going through p from left to right, let us apply or not apply each element of C_{n} so as to minimize the number of alternating runs of the obtained permutation. That is, if application of c_{i} increases the number of alternating runs, then do not apply it, if it decreases the number of alternating runs, then apply it. Let q be the obtained permutation. Then we call q the minimal permutation in A, since, among all permutations in A, it is q that has the smallest number of alternating runs. Now elements of A with i more alternating runs than q can be obtained from q by applying exactly i elements of C_{n} to q. As there are \binom{m}{i} ways to choose i such elements, our statement is proved by summing over i. □

Theorem 2.7. For n ≥ 4, the equality

R_{n}(z) = (1 + z)^{m} ∑_{q} z^{run(q)}

holds, where the summation is over permutations q that are minimal in their orbit under the action of G_{m}. Here m = ⌊(n − 2)/2⌋.

Proof. This follows from Lemma 2.6 by summing over all orbits. □

3. Longest alternating subsequences

Following Richard Stanley [3, 4], we say that an alternating subsequence in a permutation is a subsequence a_{1}a_{2} ⋯ of entries, not necessarily in consecutive positions, so that a_{1} > a_{2} < a_{3} > · · ·. Let as(p) denote the length of the longest alternating subsequence of p. It is easy to see that, if p = p_{1}p_{2} ⋯ p_{n} is a permutation, and p_{1} > p_{2}, then 1 + run(p) = as(p), while, if p_{1} < p_{2}, then run(p) = as(p). In other words, if AS_{n}(z) = ∑_{p∈S_{n}} z^{as(p)}, then the equality

AS_{n}(z) = \frac{(1 + z)R_{n}(z)}{2}

holds. Comparing this with Theorem 2.7, it follows that AS_{n}(z) is divisible by (1 + z)^{m+1} = (1 + z)^{⌊n/2⌋} for all n ≥ 4. We would like to point out that it is possible to prove this statement directly, by defining

C′_{n} = C_{n} ∪ {c_{1}},

and then repeating the argument that was used to prove Lemma 2.6.

4. Numerical Data and Further directions

The first few polynomials R_{n}(z) are the following.

• R_{1}(z) = z,

• R_{2}(z) = 2z, • R_{3}(z) = 4z^{2} + 2z,

• R_{4}(z) = 2z(5z + 1)(z + 1),

• R_{5}(z) = 2z(16z^{2} + 13z + 1)(z + 1),

• R_{6}(z) = 2z(61z^{2} + 28z + 1)(z + 1)^{2},

• R_{7}(z) = 2z(272z^{3} + 297z^{2} + 60z + 1)(z + 1)^{2},

• R_{8}(z) = 2z(1385z^{3} + 1011z^{2} + 123z + 1)(z + 1)^{3},

• R_{9}(z) = 2z(7936z^{4} + 10841z^{3} + 3651z^{2} + 251z + 1)(z + 1)^{3},

• R_{10}(z) = 2z(50521z^{4} + 50666z^{3} + 11706z^{2} + 506z + 1)(z + 1)^{4}.

It would be interesting to find other applications for this group action in counting permutations according to various statistics. It would also be interesting to find another example for the significance of the n!/2^{m} minimal permutations defined in the proof of Lemma 2.6.

Acknowledgment

I am indebted to my anonymous referees for a careful reading of the manuscript, interesting suggestions, and providing the numerical data for Section 4. My research is partially supported by Simons Collaboration Grant 421967.

References

[1] M. Bóna, R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with k runs. J. Combin. Theory Ser. A 90 (2000), 293–303.

[2] M. Bóna, Combinatorics of Permutations, Second Edition, CRC Press, 2012.

[3] R. P. Stanley, Longest alternating subsequences of permutations, Michigan Math. J. 57 (2008), 675–687.

[4] R. P. Stanley, A survey of alternating permutations, Contemporary Mathematics 531 (2010), 165–196.

[5] H. Wilf, Real zeroes of polynomials that count runs and descending runs, unpublished manuscript, 1999.

Department of Mathematics, University of Florida, 358 Little Hall, P.O. Box 118105, Gainesville, FL, 32611 − 8105, USA.

Email address: bona@ufl.edu