18.212 Algebraic Combinatorics, Lecture 10: Statistics on Permutations and More

18.212: Algebraic Combinatorics February 27 This is a reminder that the problem set is due on Monday, so we should start it soon. A few bonus problems were also added that are a bit more challenging. Next Wednesday, we will discuss the problem set in class. Professor Postnikov is pretty lenient with late problem sets, but don’t turn them in after we discuss the solutions. Last time, we started discussing statistics on permutations. We defined inv(w ) to be the number of inversions and cyc(w ) to be the number of cycles, and we found some generating functions X X q inv(w ) = [n]q !, x cyc w = x(x + 1) · · · (x + n − 1). w ∈Sn w ∈Sn Definition 1 Let a descent of a permutation w = (w1 , · · · , wn ) be an index 1 ≤ i ≤ n − 1 such that wi > wi+1 . Denote the number of descents to be des(w ). For example, des(2, 5, 7, 3, 1, 6, 8, 4) = 3. The form of the generating function is a bit less nice, though. Definition 2 The generating function X x des(w ) w ∈Sn is called the Eulerian polynomial. So we have a number of inversions, cycles, and descents. Here’s a meta-mathematical claim: interesting permutation statistics are likely equidistributed with one of these classes! Fact 3 Things related to inversions are called “Mahonian statistics.” Cycles are related to Stirling numbers, but there’s no common name. Descent-related statistics are called “Eulerian statistics.” 1 Definition 4 Let the major index of w ∈ Sn be maj(w ) = X i. i descent of w For example, the permutation w = (2, 5, 7, 3, 1, 6, 8, 4) has descents in position 3, 4, and 7, so maj(w ) = 3 + 4 + 7 = 14. Theorem 5 inv(w ) and maj(w ) are equidistributed. This is a bonus problem from the problem set! Both of these are named after Major Percy MacMahon, who wrote a famous book on combinatorics. So major is named that way for the military rank. Definition 6 A record of a permutation w is an entry greater than all entries to the left. Define rec(w ) to be the number of records of w . For example, w = (2, 5, 7, 3, 1, 6, 8, 4) has records 2, 5, 7, 8, so rec(w ) = 4. Theorem 7 rec(w ) and cyc(w ) are equidistributed. This can be proved by induction: for example, show the generating functions satisfy the same recurrence relation. But we prefer combinatorial proofs: maybe we can find a transformation with a bijective argument! Proof. We’ll find some bijection f : Sn → Sn sending w → w̃ such that cyc(w ) = rec(w̃ ). Write permutations in cycle notation: if w = (a1 · · · )(a2 · · · )(a3 · · · ) · · · , there are many ways we can write this permutation down. Write w such that each ai is the maximal element in its cycle, and sort them such that a1 < a2 < · · · . Then w̃ is just w , but instead of viewing it as cycle notation, view it as one-line notation! For example, w = (125)(3784)(6) =⇒ w = (512)(6)(8437) =⇒ w̃ = (5, 1, 2, 6, 8, 4, 3, 7). Notice that a1 , a2 , · · · will be the records of w̃ , so the number of cycles of w is the number of records of w̃ , as desired. This is bijective (to go backwards, find the records and put parentheses back), so we’re done! Definition 8 An exceedance in w is an index 1 ≤ i ≤ n such that wi > i . Let exc(w ) be the number of exceedances of w . For example, in (2, 5, 7, 3, 1, 6, 8, 4), we have 4 exceedances (not counting 6, which is a “weak exceedance”), so exc(w ) = 4. 2 Theorem 9 exc(w ) and des(w ) are equidistributed. In other words, “the number of exceedances is an Eulerian statistic.” Proof. Let’s start with a related idea: Definition 10 Define an anti-exceedance to be an index i such that wi < i . This is equidistributed with the number of exceedances. Why? Take the inverse permutation. If w (i ) > i , then w −1 (w (i )) < w (i ): this means that i is an exceedance in w means w (i ) is an exceedance in w −1 . Claim 10.1. Given a map w → w̃ that converts cycle notation to one-line notation, the number of anti-exceedances in w is the number of descents in w̃ . This is because i being a descent in w̃ means that because the i + 1th entry is not larger than w̃ , i and i + 1 are in the same cycle. Then that means that i goes to something smaller than itself, making it an anti-exceedance! Let’s look a bit at Stirling numbers now. There are two kinds of Stirling numbers: the first kind and the second kind. Definition 11 Define the Stirling numbers of the first kind for 0 ≤ k ≤ n s(n, k) = (−1)n−k c(n, k), where c(n, k) is the signless Stirling numbers of the first kind c(n, k) = the number of permutations ∈ Sn with k cycles. By convention, let s(0, 0) = 1 and s(n, 0) = 0 for all n ≥ 1. Here, fixed points are included as cycles (of length 1). Fact 12 The generating function for the Stirling numbers n X c(n, k)x k = x(x + 1) · · · (x + n − 1), k=0 and we can equivalently find that n X s(n, k)x k = x(x − 1) · · · (x − n + 1). k=0 The first expression is called “raising power of x,” while the second is called the “falling power of x.” The latter is sometimes denoted (x)n . Definition 13 Define the Stirling number of the second kind S(n, k) = number of set-partitions of [n] into k non-empty blocks. 3 We also use the convention S(0, 0) = 1 and S(n, 0) = 0 for n ≥ 1. Example 14 One set-partition is π = (125|3478|6). The main di˙erence between this and cyclic notation is that the order within each group doesn’t matter. The Stirling numbers of the second kind are always positive: there’s no negative signs like in the first kind. Theorem 15 n X S(n, k)(x)k = x n . k=0 Compare this to the generating function for Stirling numbers of the first kind: in that one, we input powers of x, and get falling powers of x, and in this one, we input falling powers of x and get powers of x! This is a kind of duality. 4