BIJECTIVE PROOFS FOR THE SHUFFLE COMPATIBILITY OF DESCENT STATISTICS By Duff Baker-Jarvis A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of Mathematics – Doctor of Philosophy 2019 ABSTRACT BIJECTIVE PROOFS FOR THE SHUFFLE COMPATIBILITY OF DESCENT STATISTICS By Duff Baker-Jarvis Define a permutation to be any sequence of distinct positive integers. Given two permuta- tions π and σ on disjoint underlying sets, we denote by π  σ the set of shuffles of π and σ, that is, the set of all permutations obtained by interleaving the two permutations. A permu- tation statistic is a function St whose domain is the set of permutations and has the property that St(π) only depends on the relative order of the elements of π. A permutation statistic is shuffle compatible if the distribution of St on π  σ depends only on the lengths of π and σ and St(π) and St(σ) rather than on the individual permutations themselves. This notion is implicit in the work of Stanley [9] when he developed his theory of P -partitions, where P is a partially ordered set. The definition was explicitly given by Gessel and Zhuang [3] who proved that various permutation statistics were shuffle compatible using mainly algebraic means. This work was continued by Grinberg [5]. The purpose of the present work is to use bijective techniques to give demonstrations of shuffle compatibility. In particular, we show how a large number of permutation statistics can be shown to be shuffle compatible using a few simple bijections. Our approach also leads to a method for constructing such bijective proofs rather than having to treat each one in an ad hoc manner. Finally, we are able to prove a conjecture of Gessel and Zhuang about the shuffle compatibility of a certain statistic. ACKNOWLEDGMENTS I would like to thank my advisor Dr. Bruce Sagan for his support and suggestions. I would also like to thank Nicholas Ovenhouse for some discussions. As well, I would like to thank my family for their support. iii TABLE OF CONTENTS LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CHAPTER 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . CHAPTER 2 PERMUTATION STATISTIC DEFINITIONS . . . . . . . . . . . . . CHAPTER 3 A GENERAL APPROACH . . . . . . . . . . . . . . . . . . . . . . . v 1 7 9 CHAPTER 4 SET VALUED STATISTICS . . . . . . . . . . . . . . . . . . . . . . 14 CHAPTER 5 THE MAJOR INDEX . . . . . . . . . . . . . . . . . . . . . . . . . 18 CHAPTER 6 PEAK STATISTICS . . . . . . . . . . . . . . . . . . . . . . . . . . 28 CHAPTER 7 FUTURE WORK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 iv LIST OF FIGURES Figure 5.1: A schematic drawing for the case when 1 ≤ x ≤ des(δ) + 1 and j + 2 (cid:54)= k. Figure 5.2: A schematic drawing for the case when des(δ) + 2 ≤ x ≤ |δ| + 1 modulo |δ| + 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 24 Figure 6.1: An illustration of the case when σa (cid:54)= ∅ and σb = σc = ∅. . . . . . . . . 30 Figure 6.2: An illustration of the case when σa, σb, and σc are all nonempty. . . . . . 31 v CHAPTER 1 INTRODUCTION Let P be the positive integers. To denote the cardinality of a set we employ #U or |U|, whichever is most convenient. All subsets of P should be assumed to be finite unless otherwise noted. For a subset U ⊂ P a permutation of U is a linear order π = π1π2 . . . πn on the elements of U . We denote the set of all linear orders on U by L(U ) = {π | π is a linear order on U}. The length of a permutation is the cardinality of its underlying set, i.e. |U|, which we denote by |π|. The domain of a permutation π ∈ L(U ) is the set U , and we write dom(π) = U . For n, i, j ∈ P with i < j, we use the notation [n] = {1, 2, . . . , n}, and [i, j] = {i, i + 1, . . . , j} with the convention that if i > j then [i, j] = ∅. Also let [n] + i = {k + i | k ∈ [n]}. For sets, U(cid:116)V = W indicates that W is the disjoint union of U and V . Double braces indicate a multiset, that is, a family of elements where repetition is allowed. We will sometimes use multiplicity notation for multisets, e.g. {{1, 24, 33}} is the multiset that contains 1, 2 four times, and 3 three times. To compare permutations on different sets of the same size we have the following defini- tion. Definition 1.1. Let U, V ⊆ P be two subsets of the positive integers such that |U| = |V |. Let π ∈ L(U ). Define the standardization to V of π = π1π2 . . . π(cid:96) to be stdV (π) = f (π1)f (π2) . . . f (π(cid:96)) where f : U → V is the unique strictly increasing bijection. Let n = |U|. Then, if no subscript is given, define std π := std[n](π) to be the standardization of π to {1, 2, . . . ,|U|}. (cid:3) 1 Two permutations π ∈ L(U ), and π(cid:48) ∈ L(V ) are said to have the same relative order if stdV (π) = π(cid:48), or equivalently, stdU (π(cid:48)) = π. For example if U = {1, 7, 8}, V = {2, 3, 9}, π = 781, π(cid:48) = 392, then π and π(cid:48) have the same relative order since stdU (392) = 781. Equivalently, std π = std π(cid:48) = 231. A permutation statistic is a map St with domain (cid:71) U⊂P |U|<∞ L(U ) such that whenever π and π(cid:48) have the same relative order, then St(π) = St(π(cid:48)). It is useful to extend the notation for permutation statistics to sets of permutations by defining, for a set of permutations Π, St(Π) to be the multiset St(Π) = {{St(π) | π ∈ Π}}. We call this multiset the distribution of St over the set Π. The basic example of a (set-valued) permutation statistic is that of the descent set, Des. For a permutation π, a descent of π is a position i such that πi > πi+1. Then the descent set of π is Des(π) = {i : i is a descent of π}. The descent number of π is des(π) = # Des(π). Another important statistic is the major index, maj given by maj(π) = (cid:88) i. i∈Des(π) For example, given the permutation π = 2157364 ∈ L([7]) we have Des(π) = {1, 4, 6} and maj(π) = 1 + 4 + 6 = 11. We call a permutation statistic, St, a descent statistic if it is a permutation statistic such that Des(π) = Des(π(cid:48)) implies St(π) = St(π(cid:48)). Both Des and maj are examples of descent statistics. There are many permutation statistics in the literature which are not descent statistics. One such statistic is inv(π) = #{i < j : πi > πj} 2 which counts the number of inversions in a permutation. For example 132 and 231 are two permutations that have the same descent set {2}, but inv(132) = 1 whereas inv(231) = 2. Given a permutation π, a subword of π is a subsequence of not necessarily consecutive elements, whereas a factor is a subsequence whose elements are consecutive. For two permu- tations with disjoint domains, a shuffle of π and σ is a permutation τ ∈ L(dom(π)(cid:116) dom(σ)) such that both π and σ occur as subwords. The shuffle set of π and σ is π  σ = {τ | τ is a shuffle of π, σ} (cid:1). As an example, if π = 132 and σ = 76 then which always has cardinality(cid:0)|π|+|σ| which has size(cid:0)3+2 |π| π  σ = {13276, 13726, 13762, 17326, 17362, 17632, 71326, 71362, 71632, 76132} (cid:1) = 10. Whenever we write a shuffle set π  σ we will implicitly assume 3 that the permutations π and σ have disjoint domains. It is an interesting fact that the statistics maj and inv have the same distribution over the shuffle set π  σ; see [2]. It is helpful to have a way to discuss and distinguish individual shuffles without carrying the entire information of both permutations along. To do this, we will use words in the two letter alphabet A = {a, b}. Denote by A∗ = {α1α2 . . . αk | k ≥ 0, αi ∈ A} the set of words in the letters of A. This is called the Kleene closure of A. Suppose that |π| = m and |σ| = n. Then we will associate to each permutation τ ∈ π  σ a word ω(τ ) ∈ A∗ of length m + n obtained by replacing the elements of π with the letter a and elements of σ with the letter b. Call ω(τ ) the word of τ . For example if π = 132, σ = 4589 and τ = 1453829, then ω(τ ) = abbabab. It is true that ω(τ ) depends on both π and σ, but these will always be clear from context. We now introduce the definition which will be our fundamental object of study. It was first introduced by Gessel and Zhuang in [3]. Definition 1.2. Assume π, π(cid:48), σ, σ(cid:48) are permutations such that |π| = |π(cid:48)|, |σ| = |σ(cid:48)| and dom(π)∩dom(σ) = dom(π(cid:48))∩dom(σ(cid:48)) = ∅. Call a permutation statistic St shuffle compatible 3 if for all such permutations which also satisfy St(π) = St(π(cid:48)) and St(σ) = St(σ(cid:48)) we have St(π  σ) = St(π(cid:48)  σ(cid:48)). Being shuffle compatible is also equivalent to the existence of a bijection Θ : π  σ → π(cid:48)  σ(cid:48) with the property that St(Θ(τ )) = St(τ ) for all τ ∈ π  σ. We call a map with this property (cid:3) St preserving. As an illustration of this, let us consider the maj statistic with π = 4312, π(cid:48) = 2341, σ = 76 and σ(cid:48) = 98. These satisfy maj(π) = maj(π(cid:48)) = 3 and maj(σ) = maj(σ(cid:48)) = 1. Then one can check that maj(π  σ) = maj(π(cid:48)  σ(cid:48)) = {{4, 5, 62, 72, 83, 92, 102, 11, 12}}. The maj statistic is indeed shuffle compatible as we will show later. The standard q-analogue of the nonnegative integer n is [n]q = 1 + q + q2 + . . . + qn−1 where q is a variable. Given integers 0 ≤ k ≤ n the corresponding q-binomial coefficient is (cid:20)n (cid:21) k q = [n]q! [k]q![n − k]q! [n]q! = [1]q[2]q ··· [n]q. given by where Let and(cid:88) τ∈πkσ Stanley [9], gave proofs of the identities π k σ = {τ ∈ π  σ | des(τ ) = k}. (cid:20)|π| + |σ| (cid:21) (cid:88) (cid:20)|π| − des(π) + des(σ) (cid:21) qmaj τ = qmaj π+maj σ |π| τ∈πσ qmaj τ = qmaj π+maj σ+(k−des π)(k−des σ) k − des(π) q (cid:20)|σ| − des(σ) + des(π) (cid:21) k − des(σ) q q 4 which imply in particular that the permutation statistic maj is shuffle compatible. He utilized P -partitions to obtain them, and later bijective proofs were given by Goulden [4], Guha and Padmanabhan [6], and Novick [7]. A recent paper by Gessel and Zhuang [3] introduced the idea of a shuffle compatible permutation statistic and proceeded to show that many permutation statistics in fact do have this property. In addition they showed that a descent statistic being shuffle compatible is equivalent to the existence of a shuffle algebra that is also a quotient algebra of the Hopf algebra QSym of quasisymmetric functions. The algebra QSym can itself be identified as the shuffle algebra of the descent set statistic Des. The methods of Gessel and Zhuang were primarily algebraic using noncommutative sym- metric functions, quasisymmetric functions, and variants of quasisymmetric functions to prove that statistics were shuffle compatible. They were also able to characterize many of the shuffle algebras corresponding to these statistics. They conjectured that several per- mutation statistics were shuffle compatible. Some of these conjectures were then proven by Grinberg in [5] using enriched P -partitions similar to those developed by Stembridge in [10]. It was also conjectured in [3] that perhaps it is true that all shuffle compatible permutation statistics are descent statistics. This has been shown to be false as an example of a shuffle compatible permutation statistic that is not a descent statistic was given by O˘guz in [8]. In this dissertation we present a bijective approach to showing that permutation statistics are shuffle compatible. Our method has the following three advantages. First of all, it is uniform in that essentially the same steps are followed to achieve each result. In addition, our proofs tend to be shorter and more transparent than other methods. Finally, we are also able to prove shuffle compatibility for (udr, pk) one of the statistics conjectured to be shuffle compatible by Gessel and Zhuang which has resisted other techniques. We now give an outline of the format of this dissertation. Chapter 2 gives a summary of the definitions of the various permutation statistics that we study. Chapter 3 outlines the general approach we take to proving shuffle compatibility as well as proving one of the 5 main reductions that we will use repeatedly. Chapter 4 gives bijective proofs of the shuffle compatibility of the known shuffle compatible set valued statistics. Chapter 5 gives bijective proofs of the shuffle compatibility of those statistics related to the major index, des, maj, and (maj, des). Chapter 6 gives bijective proofs for those statistics related to peaks. We conclude with a chapter outlining possible future directions and work. 6 CHAPTER 2 PERMUTATION STATISTIC DEFINITIONS Let π ∈ L(U ) be a permutation. Set m = |U|. The following are all permutation statistics. We use the convention that when the name for a particular permutation statistic is capitalized it refers to a set valued statistic and we use lower case names for integer valued statistics. (i) Recall that the descent set, Des is defined by Des(π) = {i : i is a descent of π} ⊆ [m − 1] and the descent number is the number of descents in the permutation, des(π) = # Des(π). An ascent of a permutation is a position i such that πi < πi+1. The set of the positions of ascents is denoted Asc(π), and asc(π) is the number of ascents. Two additional permutations statistics that come from restricting the descent set are given by χ−(π) = χ+(π) = 1 1 0 0 if 1 ∈ Des(π), if 1 (cid:54)∈ Des(π) if m − 1 ∈ Asc(π), if m − 1 (cid:54)∈ Asc(π) For example, if π = 685934 then Des(π) = {2, 4} since 8 > 5 and 9 > 3. Therefore χ−(π) = 0, but χ+(π) = 1. (ii) Also as previously introduced, the major index is given by (cid:88) maj(π) = i. i∈Des(π) (iii) A peak of a permutation is a position i such that πi−1 < πi > πi+1. The peak set is Pk(π) = {i : πi−1 < πi > πi+1} ⊆ [2, m − 1]. 7 and pk(π) = # Pk(π) is the peak number. A valley of a permutation is a position i such that πi−1 > πi < πi+1. The valley set, Val(π), and the valley number val(π) are defined analogously to the peak set and peak number. Note that a peak or valley can only occur at positions 2 ≤ i ≤ m − 1. For example, if π = 685934 again, then Pk(π) = {2, 4}, pk(π) = 2, Val(π) = {3, 5}, and val(π) = 2. (iv) A left peak is a peak of 0π, a right peak is a peak of π0, and an exterior peak is a peak of 0π0. The initial 0 is added at position 0 and the final 0 is added at position m + 1. We then have the left peak set, Lpk, left peak number lpk, the right peak set Rpk, the right peak number, rpk, the exterior peak set, Epk, and the exterior peak number, epk. Continuing the previous example, Lpk(π) = {2, 4}, lpk(π) = 2, Rpk(π) = Epk(π) = {2, 4, 6}, and rpk(π) = epk(π) = 3. (v) A left valley is a valley of ∞π, a right valley is a valley of π∞, and an exterior valley is a valley of ∞π∞ similar to the peak statistics. The definitions of the following statistics for valleys are analogous to those for peaks: Rval, Lval, Eval, rval, lval, eval . In our running example, Rval(π) = {3, 5}, rval(π) = 2, Lval(π) = Eval(π) = {1, 3, 5}, and eval(π) = lval(π) = 3. (vi) A monotone factor of a permutations is a factor that is either strictly increasing or strictly decreasing. A birun is a maximal monotone factor. An up-down run is a birun of 0π. The number of updown runs is denoted udr. The number of biruns itself is not shuffle compatible, but it affords the most convenient definition of udr. As we will see in chapter 6, one can also define udr using a combination of pk, χ+, and χ−. Using the usual example, udr(π) = 5, where the 5 maximal monotone factors of 0π are 068, 85, 59, 93, and 34. 8 CHAPTER 3 A GENERAL APPROACH In this chapter we describe a method that is general enough to tackle most of the known shuffle compatible permutation statistics in a uniform and bijective manner. Let St be a descent statistic. In order to show it is shuffle-compatible bijectively we will use the following outline. (i) Reduce to showing only a special case of shuffle-compatibility using Corollary 3.2 (2) or (3) below, whichever is most convenient. For the rest of this outline we assume (2) is chosen and let m = |π|. (ii) Find a set Π ⊆ L([m]), called the set of canonical permutations, such that if π, π(cid:48) ∈ Π and the hypotheses of Definition 1.2 are satisfied with σ = σ(cid:48), then St(π  σ) = St(π(cid:48)  σ). (iii) Find a function d : L([m]) → N such that for any π (cid:54)∈ Π there is a π(cid:48) ∈ L([m]) with St(π(cid:48)) = St(π) and d(π(cid:48)) < d(π) as well as an St-preserving bijection π  σ → π(cid:48)  σ. We can think of d as a measure of how close a permutation is to being in the chosen canonical set. To see that this suffices to show shuffle-compatibility, repeatedly use the property from step (iii) by choosing permutations with d(π(cid:48)) < d(π) and finding the corresponding bijection π  σ → π(cid:48)  σ. This can only be done a finite number of times since the range of d is N which is well ordered. Upon termination we must have π(cid:48) ∈ Π with St(π(cid:48)) = St(π) and, via composition, an St-preserving bijection π  σ → π(cid:48)  σ where π is the permutation we started with. By step (ii), this is enough to prove shuffle compatibility. We also note that often the bijections in step (iii) will be constructed using (variations of) a map which we will call the fundamental bijection, see Definition 4.1. 9 The next lemma gives our first reduction. It is at the heart of the proof of Corollary 3.2 which is our main tool for reducing the number of cases under consideration. An example of its proof is given afterwards. Lemma 3.1. Let St be a descent statistic, and consider four permutations π, π(cid:48), σ, σ(cid:48) such that dom(π) ∩ dom(σ) = dom(π(cid:48)) ∩ dom(σ(cid:48)) = ∅. If std π = std π(cid:48) and std σ = std σ(cid:48) then St(π  σ) = St(π(cid:48)  σ(cid:48)). Proof. Our method of proof will reflect the philosophy of our general approach, but with some modifications since we are only showing a special case of shuffle compatibility and do not yet have the full power of Corollary 3.2. In place of (i) above, we reduce the possible domains of our permutations by observing that since permutation statistics only depend on the relative order we may assume without loss of generality that dom(π) (cid:116) dom(σ) = dom(π(cid:48)) (cid:116) dom(σ(cid:48)) = [m + n] where m = |π| = |π(cid:48)|, and n = |σ| = |σ(cid:48)|. Then set U = [m] and V = [n] + m. For (ii), our set of canonical permutations is Π = L(U ) × L(V ). In particular, we will produce an St-preserving bijection π  σ → stdU (π)  stdV (σ). For (iii), our measure of how close a pair of permutations is to being in this set is given by #O where O = {(i, j) ∈ dom(π) × dom(σ) | i > j}. A pair will have #O = 0 exactly when (π, σ) ∈ Π. Now if (π, σ) (cid:54)∈ Π we will produce a pair of permutations (π(cid:48)(cid:48), σ(cid:48)(cid:48)) with St(π) = St(π(cid:48)(cid:48)), St(σ) = St(σ(cid:48)(cid:48)) and a St-preserving bijection π  σ → π(cid:48)(cid:48)  σ(cid:48)(cid:48) that reduces #O. This suffices because repeatedly applying this operation will produce the pair of permutations (stdU (π), stdV (σ)), and (by composition) an St-preserving bijection π  σ → stdU (π)  10 stdV (σ). An analogous argument gives a St-preserving bijection π(cid:48)  σ(cid:48) → stdU (π(cid:48))  stdV (σ(cid:48)). Then, using the hypothesis of the lemma, we will have St(π  σ) = St(stdU (π)  stdV (σ)) = St(stdU (π(cid:48))  stdV (σ(cid:48))) = St(π(cid:48)  σ(cid:48)) as required. We now construct (π(cid:48)(cid:48), σ(cid:48)(cid:48)) and the St-preserving bijection. Since (π, σ) (cid:54)∈ Π, there exists a pair (i, i − 1) ∈ O such that i ∈ dom(π) and i − 1 ∈ dom(σ). Set π(cid:48)(cid:48) = (i, i − 1)π and σ(cid:48)(cid:48) = (i, i − 1)σ where (i, i − 1)π is the permutation π with i replaced by i − 1 and similarly for (i, i − 1)σ. Let τ ∈ π  σ. Then the bijection is given by if i, i − 1 are not adjacent in τ , (i, i − 1)τ Ti(τ ) = otherwise, where (i, i − 1)τ is τ with i and i − 1 interchanged. τ This map is its own inverse, hence a bijection. To see that the image of the map is in π(cid:48)(cid:48)  σ(cid:48)(cid:48) note that if i, i − 1 are not adjacent then Ti(τ ) ∈ π(cid:48)(cid:48)  σ(cid:48)(cid:48) since Ti(τ ) is the unique shuffle of π(cid:48)(cid:48) and σ(cid:48)(cid:48) whose word satisfies ω(Ti(τ )) = ω(τ ). And if i and i − 1 are adjacent in τ , then τ is easily seen to also be a shuffle of π(cid:48)(cid:48) and σ(cid:48)(cid:48). The map Ti is Des preserving because swapping the positions of i, i − 1 when i and i − 1 are not adjacent will not change the order relation between any adjacent pairs. Indeed, given any j (cid:54)∈ {i − 1, i} that is adjacent to one or both of i, i − 1, it is clear that either both j > i and j > i − 1, or j < i − 1 and j < i, and hence the inequalities are preserved when interchanging i, i − 1. It follows from the definition of a descent statistic that Ti is also St preserving. As an example, let U = {1, 2, 4}, V = {3, 7} and π = 241 and σ = 73. Then π  σ = {24173, 24713, 24731, 27413, 27431, 27341, 72413, 72431, 72341, 73241}. It follows that Pk(π  σ) = {{{2}2, {3}4, {4}2, {2, 4}2}}. 11 Now standardize to [m + n] by replacing σ with(cid:101)σ = 53, and V with (cid:101)V = {3, 5} to obtain π (cid:101)σ = {24153, 24513, 24531, 25413, 25431, 25341, 52413, 52431, 52341, 53241}. Then Pk(π (cid:101)σ) = Pk(π  σ). We next would like to change U to U(cid:48) = {1, 2, 3} and (cid:101)V to (cid:101)V (cid:48) = {4, 5}. This can be done using (4, 3) ∈ O. We apply T4(π (cid:101)σ) = {23154, 23514, 23541, 25314, 25431, 25341, 52314, 52431, 52341, 54231} where, for instance, T4(52413) = 52314 since 3 and 4 are not adjacent. On the other hand, T4(52341) = 52341 since 3, 4 are adjacent. One can check that the distribution with respect to Pk remains unchanged. The following corollary shows that in order to check shuffle compatibility, it suffices to check the special case when the domains of the permutation have some fixed relation with each other. This reduction greatly simplifies the required arguments for showing statistics are shuffle compatible. Corollary 3.2. Suppose St is a descent statistic. Then the following are equivalent (1) St is shuffle compatible. (2) If St(π) = St(π(cid:48)) where π, π(cid:48) ∈ L([m]), and σ ∈ L([n] + m) for some m, n ≥ 0, then St(π  σ) = St(π(cid:48)  σ). (3) If St(σ) = St(σ(cid:48)) where σ, σ(cid:48) ∈ L([n] + m), and π ∈ L([m]) and some m, n ≥ 0, then St(π  σ(cid:48)) = St(π  σ). Proof. It is clear that (1) implies (2) and (3) as these are special cases of the definition of shuffle compatibility. Assume (2) holds and let π, π(cid:48) be any two permutations of the same length m such that St(π) = St(π(cid:48)). Let σ, σ(cid:48) be two permutations of the same length n and 12 disjoint from π, π(cid:48) such that St(σ) = St(σ(cid:48)). Set U = [m], U + = [m] + n, V = [n], and V + = [n] + m. Then by Lemma 3.1 and our assumption, St(π  σ) = St(stdU (π)  stdV +(σ)) = St(stdU (π(cid:48))  stdV +(σ)) = St(stdU +(π(cid:48))  stdV (σ)) = St(stdU +(π(cid:48))  stdV (σ(cid:48))) = St(π(cid:48)  σ(cid:48)) by Lemma 3.1 by (2) by Lemma 3.1 by (2) by Lemma 3.1. The proof that (3) implies (1) is very similar. 13 CHAPTER 4 SET VALUED STATISTICS Our first main results are to give bijective proofs for the shuffle compatibility of some set valued statistics. The statistic Des was given a different bijective proof in [3], so the novelty here is the bijective proofs of the remaining set valued statistics as well as the uniform manner in which they are attained. Definition 4.1. Given permutations π, σ with disjoint domains and a third permutation π(cid:48) with |π| = |π(cid:48)|, define the fundamental bijection Φ : π  σ → π(cid:48)  σ Φ(τ ) = τ(cid:48) where τ(cid:48) ∈ π(cid:48)  σ is the unique permutation with ω(τ(cid:48)) = ω(τ ). This amounts to replacing the elements of π with the elements of π(cid:48) in the same order and positions as in τ . If instead one holds π fixed and replaces σ with σ(cid:48) then one obtains a bijection which we call (cid:101)Φ. (cid:3) For example, if π = 132, σ = 4589, τ = 1453829 ∈ π  σ and π(cid:48) = 361, then Φ(τ ) = 3456819. The following theorem establishes the shuffle compatibility of some set valued statistics. These were initially proven by Gessel and Zhuang in [3] and Gringberg in [5] by lengthier and primarily algebraic methods. An advantage of our approach is the directness and uniformity with which the results are obtained. Theorem 4.2. The set valued statistics Des, Pk, Lpk, Rpk, and Epk are all shuffle com- patible. Proof. By Corollary 3.2, part (2), we may reduce to showing that for π, π(cid:48) ∈ L([m]) and σ ∈ L([n] + m), if we have St(π) = St(π(cid:48)) then it follows that St(π  σ) = St(π(cid:48)  σ) for the five statistics listed above. 14 The fundamental bijection Φ : π  σ → π(cid:48)  σ will be the map we will use for all five statistics. Because these cases are so straightforward, we will not have to find a canonical set of permutations. For each of these statistics, St ∈ {Des, Pk, Lpk, Rpk, Epk}, we will give a complete list of the cases that determine whether a given position will contribute to St(τ ) for a shuffle τ ∈ π  σ. It will then be easy to check that St will be preserved by Φ. • Descent set, Des: Observe that in a shuffle τ ∈ π  σ we have i ∈ Des τ if and only if τiτi+1 equals one of 1. πjπj+1 where j ∈ Des π, 2. σkσk+1 where k ∈ Des σ, or 3. σkπj. It is now easy to check that the descent set is preserved in passing from τ to Φ(τ ). • Peak set, Pk: For a shuffle τ ∈ π  σ, we have i ∈ Pk τ if and only if τi−1τiτi+1 equals one of 1. πj−1πjπj+1 where j ∈ Pk π, 2. σk−1σkσk+1 where k ∈ Pk σ, 3. σkσk+1πj where k ∈ Asc σ, 4. πjσkσk+1 where k ∈ Des σ, 5. πjσkπj+1. This makes it simple to check that a peak in τ will remain one in Φ(τ ). For example, in case 3 we have σk < σk+1 > πj in τ so that the position of σk+1 is a peak of τ . Upon replacing π with π(cid:48) we have σk < σk+1 > π(cid:48) j since every element of π(cid:48) is less 15 than every element of σ. Therefore the position of σk+1 is a peak in Φ(τ ) at the same position as it was in τ . Using similar arguments and Φ−1, one sees that a position that is a peak of Φ(τ ) must also be a peak of τ and so Φ is peak preserving. • Left peak set, Lpk: For a shuffle τ ∈ π  σ, note that we have Pk(τ ) ⊆ Lpk(τ ) so that the above cases for the peak set show that for i ≥ 2 we have i ∈ Lpk(τ ) if and only if i ∈ Lpk(Φ(τ )). It therefore remains only to check what happens when i = 1. But 1 ∈ Lpk(τ ) if and only if 0τ1τ2 equals one of 1. 0π1π2 where 1 ∈ Lpk(π) 2. 0σ1σ2 where 1 ∈ Lpk(σ) 3. 0σ1π1 The check that left peaks at i = 1 are preserved is similar to the arguments for Pk. So in this and the following, we have left this verification to the reader. • Right peak set, Rpk: The argument is analogous to that of Lpk, except that we now need additional cases at the right end of τ . Note that m + n ∈ Rpk(τ ) if and only if τm+n−1τm+n0 equals one of 1. πm−1πm0 where m ∈ Rpk(π) 2. σn−1σn0 where n ∈ Rpk(σ) 3. πmσn0 • External peak set, Epk: Since Epk(τ ) = Lpk(τ ) ∪ Rpk(τ ) and the single bijection Φ preserves both Rpk and Lpk, we have that Epk is also preserved under Φ. 16 A couple of observations are appropriate here. Firstly, note that if there is a single bijection that shows the shuffle compatibility of two or more permutation statistics, then it follows immediately that any tuple of these statistics is also shuffle compatible. For example, since Lpk and Rpk are both shuffle co-patible by means of the bijection Φ, then so as well is (Lpk, Rpk). Therefore any tuple from the above five statistics is also shuffle compatible. This gives one answer to a question of Gessel and Zhuang in [3] as to when a tuple of statistics is shuffle compatible. Secondly, some statistics determine others. For example (Des, Pk) is shuffle compatible since Des is shuffle compatible and Pk can be determined from Des. Theorem 4.3. The statistics Asc, Val, Lval, Rval, and Eval are shuffle compatible. Proof. This proof closely parallels that of the previous theorem except we use part (3) of Corollary 3.2 in place of part (2), (cid:101)Φ in place of Φ, and ∞ in place of 0. Because of the similarity, we only indicate how to do Asc. Observe that in a shuffle, τ ∈ π  σ, we have i ∈ Asc τ if and only if τiτi+1 equals one of 1. πjπj+1 where j ∈ Asc π, 2. σkσk+1 where k ∈ Asc σ, or It is now easy to check that the ascent set is preserved in passing from τ to (cid:101)Φ(τ ). 3. πjσk. 17 CHAPTER 5 THE MAJOR INDEX For the next proof, we need to introduce a labeling on the spaces of a permutation. Let π be a permutation of length m with des(π) = k. Then by a space of π we mean the gap between two adjacent elements of π. There is, by convention, an initial space before the first element of π and a final space after the last element of the permutation. Label these spaces by assigning the right-most (final) space the label 0 then labeling the spaces after descents of π with the integers in [k] from right to left, then labeling the remaining spaces with the integers in [k + 1, m] from left to right. Equivalently, we label the spaces of π corresponding to descents of 0π0 from right to left and then the spaces of π corresponding to ascents of 0π0 from left to right using the elements of [0, m]. In what follows we make no distinction between a space and its label. For example if π = 265781 then the labeled permutation is 3246255768110 with the raised numbers being the labels of the spaces. If πi and πi+1 are the elements on either side of space x then we say there is a descent or ascent at space x if i ∈ Des(π) or i ∈ Asc(π), respectively. It is well known that inserting a number greater than max dom(π) in space i increases maj π by i. Continuing our example, inserting 9 in space 4 of π gives the permutation 2965781 with maj(2965781) = 11 = maj(265781) + 4. This fact is used in one of the standard proofs that the generating function for maj over the permutations of [n] is [n]q!. We will now see that this is a crucial tool for proving certain shuffle compatibility results. Theorem 5.1. The permutation statistics des and (maj, des) are shuffle compatible. Proof. Our first step is to use Corollary 3.2 part (3) to reduce to showing that π ∈ L(m) and σ, σ(cid:48) ∈ L([n] + m) with St(σ) = St(σ(cid:48)) implies St(π  σ) = St(π  σ(cid:48)) for each St ∈ 18 {des, (maj, des)}. The core of the proof is the existence of certain bijections that preserve des, lower maj by one, and allow us to replace σ with a permutation that is closer to being in our chosen set of canonical permutations, as outlined in the general approach. For the permutations with des σ = p we will use the canonical set Π = {σ ∈ L([n] + m) : Des(σ) = [p]} which consists of the permutations with a sequence of p descents followed by a sequence of ascents. Given two permutations σ, σ(cid:48) ∈ Π, we know by Theorem 5.1 that Des(π  σ) = Des(π  σ(cid:48)) and hence the same holds for any descent statistic. This shows that part (ii) of the general approach is satisfied. Our measure of how close a permutation is to being in Π is d : L([n] + m) → N given by d(σ) = maj(σ). Note that among all permutations in L([n] + m) with des σ = p, those in Π have the minimum possible maj, namely(cid:0)p+1 and lowers the major index of each τ by the same amount, namely maj(σ) −(cid:0)p+1 (cid:1). Our strategy will be to find a bijection (cid:1). This between shuffles τ ∈ π  σ and the shuffles of π with an element of Π which preserves des 2 2 will prove the theorem. To reduce a permutation to one in Π we will move their descents to the left one position at a time. More specifically, if σ (cid:54)∈ Π then there is at least one position i ≥ 2 such that σi−1 < σi > σi+1. Let σ(cid:48)(cid:48) be any permutation such that Des(σ(cid:48)(cid:48)) = (Des(σ) \ {i}) ∪ {i − 1}. Note that this preserves des but lowers maj by one in passing from σ to σ(cid:48)(cid:48) . The bijection we will define between π  σ and π  σ(cid:48)(cid:48) will have the same properties and so, by iteration, complete the proof. For τ ∈ π  σ, write τ as a concatenation τ = τ aτ bτ c where τ b is the factor of τ between but not including σi−1 and σi+1. Then τ a and τ c are the remaining initial and final factors of τ , respectively. Note that there is exactly one element of σ in τ b and that it is larger than all the elements of π. Consider the permutation δ that is τ b with σi removed. All spaces 19 will be spaces of δ. Let x be the space of δ from which σi was removed from and set (τ b)(cid:48)(cid:48) to be the permutation δ with σi inserted into the space x − 1 where x − 1 is taken modulo |δ| + 1. Define a map Θ : π  σ → π  σ(cid:48)(cid:48) by Θ(τ ) = τ(cid:48)(cid:48) where τ(cid:48)(cid:48) is the unique element of π  σ(cid:48)(cid:48) such that ω(τ(cid:48)(cid:48)) = ω(τ a(τ b)(cid:48)(cid:48)τ c). We now show that Θ has the desired properties, namely that it is des preserving and satisfies maj(Θ(τ )) = maj(τ ) − 1. There are two cases to check, based on the label x of the original space that σi occupied. 1. If 1 ≤ x ≤ des(δ) + 1 : First note that in this case δ cannot be empty if x exists in this range. Let τj be the element of τ directly before σi and let τk be the be the element of τ directly before space x − 1 of δ. The map Θ removes σi from the position after τj and inserts σ(cid:48)(cid:48) after τk while changing the order relation from σi−1 < σi > σi+1 to σ(cid:48)(cid:48) i+1. There are no descents l in τ with j + 2 ≤ l ≤ k − 1. Therefore we only have to analyze what happens at positions j, j + 1, k − 1, and k. First, assume that j + 2 (cid:54)= k. i in the position directly i−1 > σ(cid:48)(cid:48) i < σ(cid:48)(cid:48) An illustration of this case in a generic small example is shown in Figure 1. The left picture is an example of the initial state of τ b and the right picture is of the resulting part of τ(cid:48)(cid:48) after applying Θ. Each dot represents an element of τ or τ(cid:48)(cid:48), respectively, and the lines connecting them represent the order relation between adjacent elements. For example, a line with positive slope corresponds to the first element being smaller than the second. 20 • In τ : – j (cid:54)∈ Des(τ ): The position j is never a descent of τ since τj+1 = σi, and τj is either σi−1 or in π. In both cases τj < τj+1. – j + 1 ∈ Des(τ ): The position j + 1 is always a descent of τ since τj+1 = σi and τj+2 ∈ π because of the range of x. – k − 1 (cid:54)∈ Des(τ ). Since j + 2 (cid:54)= k, the definition of the space labeling and the range of x show that k − 1 is an ascent of τ . – k ∈ Des(τ ) if and only if x (cid:54)= 1. If x = 1, then τk ∈ π and τk+1 = σi+1 and so k is an ascent of τ . On the other hand, if x (cid:54)= 1, then k is a descent of τ by the definition of the space labeling and the range of x. • In τ(cid:48)(cid:48): – j ∈ Des(τ(cid:48)(cid:48)): The position j is always a descent of τ(cid:48)(cid:48) since τ(cid:48)(cid:48) or τ(cid:48)(cid:48) j ∈ π with j corresponding to the descent at space x of δ. j+1 ∈ π, and either τ(cid:48)(cid:48) j = σ(cid:48)(cid:48) i−1 – j + 1 (cid:54)∈ Des(τ(cid:48)(cid:48)): The position j+1 is never a descent of τ(cid:48)(cid:48) since τ(cid:48)(cid:48) or τ(cid:48)(cid:48) j+2 = σ(cid:48)(cid:48) j+2 ∈ π with j + 1 corresponding to an ascent of δ by the definition of j+1 ∈ π, and either τ(cid:48)(cid:48) i the space labeling and the range of x. – k − 1 (cid:54)∈ Des(τ(cid:48)(cid:48)) Since j + 2 (cid:54)= k we have τ(cid:48)(cid:48) i so that k − 1 is an ascent. k−1 ∈ π and τ(cid:48)(cid:48) k = σ(cid:48)(cid:48) 21 τj+1 = σi τk τj k = σ(cid:48)(cid:48) τ(cid:48)(cid:48) i τ(cid:48)(cid:48) k−1 j τ(cid:48)(cid:48) τ(cid:48)(cid:48) j+1 Figure 5.1: A schematic drawing for the case when 1 ≤ x ≤ des(δ) + 1 and j + 2 (cid:54)= k. – k ∈ Des(τ(cid:48)(cid:48)) if and only if x (cid:54)= 1. i . If x = 1 then τ(cid:48)(cid:48) We have τ(cid:48)(cid:48) the choice of σ(cid:48)(cid:48). On the other hand if x (cid:54)= 1, then τ(cid:48)(cid:48) σ(cid:48)(cid:48) i > τ(cid:48)(cid:48) k+1 = σ(cid:48)(cid:48) i+1 and hence k (cid:54)∈ Des(τ(cid:48)(cid:48)) by k+1 ∈ π and hence k = σ(cid:48)(cid:48) k+1. When j +2 = k, we have the same two lists but with the item concerning k−1 removed since k − 1 = j + 1 and so the item concerning j + 1 covers this case. Comparing the two lists, we have Des(τ(cid:48)(cid:48)) = (Des(τ ) \ {j + 1}) ∪ {j} (5.1) and, in particular, des(τ(cid:48)(cid:48)) = des(τ ). This relation between descent sets also makes it clear that maj(τ(cid:48)(cid:48)) = maj(τ ) − 1. 2. If des(δ) + 2 ≤ x ≤ |δ| + 1 modulo |δ| + 1: Define τj and τk as before. Again, the map Θ removes σi from the position after τj and inserts σ(cid:48)(cid:48) i in the position directly after τk while changing the order relation from σi−1 < σi > σi+1 to σ(cid:48)(cid:48) i−1 > σ(cid:48)(cid:48) i < σ(cid:48)(cid:48) i+1. Note however, that it is now possible for δ to be empty. In that case Θ just changes the peak at σi at position j + 1 in τ to a valley in τ(cid:48)(cid:48). So clearly equation (5.1) still holds. 22 Therefore assume δ (cid:54)= ∅ and note that all positions strictly between k and j will be descents in τ . It is easy to see that these positions will remain descents after applying Θ. So we only need to check what happens at positions j, j + 1 and k. An illustration of this case is given in Figure 5.2. The left picture is an illustration of an example of the initial state of τ b and the right picture is of the resulting part τ(cid:48)(cid:48) after applying Θ. • In τ : – j (cid:54)∈ Des(τ ): The position j is never a descent of τ since τj ∈ π and τj+1 = σi because of the range of x. – j + 1 ∈ Des(τ ): The position j + 1 is always a descent of τ since τj+1 = σi and τj+2 is σi+1 or is in π. In both cases τj+1 > τj+2. – k ∈ Des(τ ) if and only if x = des(δ) + 2. If x = des(δ) + 2, then x − 1 = des(δ) + 1 is the the space before δ. Hence τk = σi−1 and τk+1 ∈ π, so k ∈ Des(τ ). On the other hand, if x (cid:54)= des(δ) + 2, then k is an ascent of δ and hence τ by the definition of the space labeling and the range of x. • In τ(cid:48)(cid:48): – j ∈ Des(τ(cid:48)(cid:48)): The position j is always a descent of τ(cid:48)(cid:48) since τ(cid:48)(cid:48) or τ(cid:48)(cid:48) j = σ(cid:48)(cid:48) j ∈ π and j corresponds to the descent of δ at the space previous to x. j+1 ∈ π, and either τ(cid:48)(cid:48) i – j + 1 (cid:54)∈ Des(τ(cid:48)(cid:48)): The position j is never a descent of τ(cid:48)(cid:48) since τ(cid:48)(cid:48) or τ(cid:48)(cid:48) j+2 ∈ π and j + 1 corresponds to the ascent of δ at space x. j+1 ∈ π, and either τ(cid:48)(cid:48) j+2 = σ(cid:48)(cid:48) i+1 23 τj+1 = σi τk+1 τj−1 τk τj k+1 = σ(cid:48)(cid:48) τ(cid:48)(cid:48) i τ(cid:48)(cid:48) k τ(cid:48)(cid:48) j τ(cid:48)(cid:48) j+1 Figure 5.2: A schematic drawing for the case when des(δ) + 2 ≤ x ≤ |δ| + 1 modulo |δ| + 1. – k ∈ Des(τ(cid:48)(cid:48)) if and only if x = des(δ) + 2. If x = des(δ) + 2, then x − 1 = des(δ) + 1 is the the space before δ. Hence τ(cid:48)(cid:48) k = σ(cid:48)(cid:48) k+1 = σi, so k ∈ Des(τ ). On the other hand, if x (cid:54)= des(δ)+2 then τ(cid:48)(cid:48) k+1 = σ(cid:48)(cid:48) i−1 and τ(cid:48)(cid:48) k ∈ π and τ(cid:48)(cid:48) i , so that k (cid:54)∈ Des(τ(cid:48)(cid:48)). Thus in this case as well equation (5.1) continues to hold. This finishes the proof of the shuffle compatibility of des and (maj, des). In the above proof we proceeded to reduce permutations by moving descents to the left as far as we could. However, to show the shuffle compatibility of maj we must reduce the permutations even further since permutations with the same value of maj may have different numbers of descents. Theorem 5.2. The permutation statistic maj is shuffle compatible. Proof. As in the previous proof, our first step is to use Corollary 3.2 to reduce to showing that π ∈ L(m) and σ, σ(cid:48) ∈ L([n] + m) with maj(σ) = maj(σ(cid:48)) implies maj(π  σ) = maj(π  σ(cid:48)). We will use the same canonical permutation for every element of L([n] + m) by letting Π = {σ ∈ L([n] + m) : Des(σ) = ∅}. This set contains the unique increasing permutation. Our measure of how close a permutation is to being in Π is d : L([n] + m) → N given by d(σ) = maj(σ). Observe that σ ∈ Π if and only if maj(σ) = 0. Our strategy will be to find a bijection between shuffles τ ∈ π  σ and 24 shuffles with the element of Π which lowers the major index of each τ by the same amount, namely maj(σ). To reduce a permutation to one in Π we will move their descents to the left one position at a time until they are moved to position 0 at which point they vanish. More precisely, if σ (cid:54)∈ Π then there exists at least one position i ∈ Des(σ) such that i − 1 (cid:54)∈ Des(σ) and we allow the case i = 1. Fix any such i and let σ(cid:48)(cid:48) be any permutation such that (Des(σ) \ {i}) ∪ {i − 1} Des(σ) \ {1} if i ≥ 2, if i = 1. Des(σ(cid:48)(cid:48)) = The map Θ from the proof of Theorem 5.1 suffices when i ≥ 2, so we need only give a bijection (cid:101)Θ : π  σ → π  σ(cid:48)(cid:48) for the case i = 1 such that the image τ(cid:48)(cid:48) = (cid:101)Θ(τ ) satisfies maj(τ(cid:48)(cid:48)) = maj(τ ) − 1. (5.2) This means that if there is a descent at position 1 then we need a bijection which reduces maj by one by changing that descent to an ascent. Set (cid:101)σ = m + 1, σ1 + 1, σ2 + 1, . . . , σn + 1 ∈ L([n + 1] + m) (cid:101)σ(cid:48)(cid:48) = m + n + 1, σ(cid:48)(cid:48) 1 , σ(cid:48)(cid:48) n ∈ L([n + 1] + m). 2 , . . . , σ(cid:48)(cid:48) and For a permutation σ, let Sσ = {τ ∈ π  σ : τ1 = σ1} (5.3) be the subset of π  σ whose elements all have σ1 in the first position. There is a natural bijection ι : π  σ → S(cid:101)σ. Namely, for τ ∈ π  σ, let ι(τ ) = (m + 1)(cid:101)τ where(cid:101)τ is the unique permutation such that ω(τ ) = ω((cid:101)τ ), i.e., (cid:101)τ is π  σ with all elements of σ increased by 1. There is an analogous map ι(cid:48)(cid:48) : π  σ(cid:48)(cid:48) → S(cid:101)σ(cid:48)(cid:48). Note that Θ(S(cid:101)σ) = S(cid:101)σ(cid:48)(cid:48) since Des((cid:101)σ(cid:48)(cid:48)) = (Des((cid:101)σ) \ {2}) ∪ {1}. 25 maj(ι(τ )) = if τ1 = σ1 if τ1 = π1 maj(τ ) + des(τ ) + 1 maj(τ ) + des(τ ) des(τ ) π  σ It follows that we can define (cid:101)Θ by insisting that the following diagram commutes ⊆ π (cid:101)σ ⊆ π (cid:101)σ(cid:48)(cid:48) In other words, we define (cid:101)Θ = ι(cid:48)(cid:48)−1 ◦ Θ ◦ ι which is clearly bijective. To finish, it suffices to show that (cid:101)Θ reduces maj by 1. First of all, observe that we have π  σ(cid:48)(cid:48) S(cid:101)σ(cid:48)(cid:48) S(cid:101)σ (cid:101)Θ ι ι(cid:48)(cid:48) Θ since each descent is shifted to the right by 1 position and if τ1 = π1 there is an additional descent at position 1. By the previous theorem, maj(Θ(ι(τ ))) = maj(ι(τ )) − 1. Also des(Θ(ι(τ ))) = des(ι(τ )) = if τ1 = σ1 since, by the previous theorem, Θ was des preserving. Finally, for an element τ(cid:48)(cid:48) ∈ π (cid:101)σ(cid:48)(cid:48) if τ1 = π1 des(τ ) + 1 we have maj(ι(cid:48)(cid:48)−1(τ(cid:48)(cid:48))) = maj(τ(cid:48)(cid:48)) − des(τ(cid:48)(cid:48)) since each descent is moved to the left by 1 position. Thus, regardless of the first element of τ , maj(ι(cid:48)(cid:48)−1(Θ(ι(τ ))) = maj(Θ(ι(τ )) − des(Θ(ι(τ )) = (maj(ι(τ )) − 1) − des(Θ(ι(τ )) = maj(τ ) − 1. which finishes the proof. We can now recover the identity for the distribution of maj over the shuffle set. We start with a well-known result whose proof can be found in [1] Section 2.2.2. Bona’s treatment 26 deals with rearrangements of a multiset containing 1’s and 2’s, which is easily seen to be equivalent to shuffling two words, the first consisting only of 1’s and the second only of 2’s. One defines maj in the same way for words with repeated numbers. Theorem 5.3. Let e = (cid:122) (cid:125)(cid:124) (cid:123) Then the following identity holds.(cid:88) 11 . . . 1 m and f = (cid:122) (cid:125)(cid:124) (cid:123) 22 . . . 2 n qmaj(τ ) = τ∈ef be words of length m and n respectively. (cid:20)m + n (cid:21) m . q (5.4) The previous result will act as the base case for our inductive proof of the follow result cited in the introduction. Theorem 5.4. Let π and σ be permutations with disjoint domains and lengths m and n, respectively. Then (cid:88) τ∈πσ qmaj τ = qmaj π+maj σ (cid:20)m + n (cid:21) m . q Proof. Since we have shown that maj is shuffle compatible, we may assume that π ∈ L([m]) and σ ∈ L([n] + m). We will induct on maj(π) + maj(σ). If maj(π) + maj(σ) = 0 then π = 12 . . . m and σ = m + 1, m + 2, . . . , m + n. In this case, the result follows from Theorem 5.3. This is because replacing e with π and f with σ, respectively, in τ ∈ e  f turns a repeated pair 11 or 22 into an ascent, while descents remain descents since all elements of σ are larger than those of π. Now assume maj(π) + maj(σ) > 0. By Lemma 3.1 we can assume, without loss of generality, that maj(σ) > 0. So the map (cid:101)Θ : π  σ → π  σ(cid:48)(cid:48) of Theorem 5.2 is a bijection, where maj(σ(cid:48)(cid:48)) = maj(σ) − 1 and maj(τ(cid:48)(cid:48)) = maj(τ ) − 1 for τ(cid:48)(cid:48) = (cid:101)Θ(τ ). By induction, the desired equation holds for π  σ(cid:48)(cid:48). Multiplying the equality by q and substituting, shows that it also holds for π  σ. 27 CHAPTER 6 PEAK STATISTICS We now move on to statistics related to peaks. The proofs of statistic (udr, pk) is notable because it was previously only conjectured to be shuffle compatible and here we give a proof that is similar in nature to those for the other peak statistics. Theorem 6.1. The statistic pk is shuffle compatible. Proof. By Corollary 3.2 part (2) it suffices to prove that if π, π(cid:48) ∈ L([m]) and σ ∈ L([n] + m) with pk(π) = pk(π(cid:48)) then pk(π  σ) = pk(π(cid:48)  σ). For the permutations with pk π = p we will use the canonical set Π = {π ∈ L([m]) : Pk(π) = {2, 4, . . . , 2p} for some p ≥ 0} which contains exactly the permutations with p peaks which are as far to the left as possible. So if π, π(cid:48) ∈ Π then Pk(π) = Pk(π(cid:48)). It follows that Pk(π  σ) = Pk(π(cid:48)  σ) since Pk is shuffle compatible. Therefore pk(π σ) = pk(π(cid:48) σ) and the conclusion of (ii) of the general approach holds. Our measure of how close a permutation is to being in Π is d : L([m]) → N given by (cid:88) d(π) = k. k∈Pk(π) Note that among all permutations in L([m]) with pk π = p, the ones in Π have the minimum possible d, namely p(p+1). Our strategy will be to find a bijection between shuffles τ ∈ π σ and shuffles with an element of Π which preserves pk and lowers d by the proper amount, namely d(π) − p(p + 1). To reduce a permutation to one in Π we will move its peaks to the left one position at a time. More specifically, if π (cid:54)∈ Π then there is at least one position j ≥ 3 such that j ∈ Pk(π), but j − 2 (cid:54)∈ Pk(π). Thus there exists π(cid:48)(cid:48) ∈ L([m]) such that Pk(π(cid:48)(cid:48)) = Pk(π) \ {j} ∪ {j − 1}. (6.1) (cid:18) (cid:19) 28 Since d(π(cid:48)(cid:48)) < d(π), it suffices to give a pk-preserving bijection between π  σ and π(cid:48)(cid:48)  σ. For each τ ∈ π  σ, factor τ = τ aτ bτ c where τ b is the factor of τ between πj−2 and πj+1, not including πj−2 and πj+1. Then τ a is the remaining initial factor of τ and τ b is the final factor. Factor τ b even further as τ b = σaπj−1σbπjσc so that σa, σb, σc are the factors of σ that are between the corresponding elements of π. Note that it is possible for any or all of σa, σb, σc to be empty. Define the map Θ : π  σ → π(cid:48)(cid:48)  σ by  Θ(τ ) = (τ a)(cid:48)(cid:48)π(cid:48)(cid:48) j−1π(cid:48)(cid:48) j σa(τ c)(cid:48)(cid:48) (τ a)(cid:48)(cid:48)σcπ(cid:48)(cid:48) j−1π(cid:48)(cid:48) j (τ c)(cid:48)(cid:48) if σa (cid:54)= ∅ and σb = σc = ∅, if σa = σb = ∅ and σc (cid:54)= ∅, (6.2) Φ(τ ) otherwise where (τ a)(cid:48)(cid:48) is the unique permutation such that ω(τ a) = ω((τ a)(cid:48)(cid:48)) and (τ c)(cid:48)(cid:48) is the unique permutation such that ω(τ c) = ω((τ c)(cid:48)(cid:48)). It is clear from its definition that Θ is a bijection. So it only remains to show that Θ is pk preserving. Let s, t be such that τs = πj−2 and τt = πj+1 and set (cid:96) = |σa|. Note that, as in the proof of Theorem 4.2, for i ∈ [m + n]− [s, t] we have i ∈ Pk(τ ) if and only if i ∈ Pk(τ(cid:48)(cid:48)). So to show that Θ is pk preserving we just need to concentrate on those peaks in [s, t]. If σa (cid:54)= ∅ and σb = σc = ∅ then it is straightforwards to check, using the cases from the proof of Theorem 4.2 for Pk that the only peaks of τ in the set [s, t] occur as one of the following. (a) Every peak of σa is a peak of τ . (b) s + 1 ∈ Pk(τ ) if and only if 1 ∈ Des(σa) or (cid:96) = 1. 29 σa πj πj−2 = τs πj−1 σa π(cid:48)(cid:48) j−1 π(cid:48)(cid:48) j π(cid:48)(cid:48) j−2 πj+1 = τt π(cid:48)(cid:48) j+1 Figure 6.1: An illustration of the case when σa (cid:54)= ∅ and σb = σc = ∅. (c) For (cid:96) ≥ 2: s + (cid:96) ∈ Pk(τ ) if and only if (cid:96) − 1 ∈ Asc(σa). (d) t − 1 is always a peak of τ . We now compare this to the similar list for τ(cid:48)(cid:48). (a) Every peak of σa is a peak τ(cid:48)(cid:48). (b) s + 3 ∈ Pk(τ(cid:48)(cid:48)) if and only if 1 ∈ Des(σa) or (cid:96) = 1. (c) For (cid:96) ≥ 2: t − 1 ∈ Pk(τ(cid:48)(cid:48)) if and only if (cid:96) − 1 ∈ Asc(σa). (d) s + 1 is always a peak of τ(cid:48)(cid:48). Clearly these lists contain the same number of peaks. An illustration of this case is given in Figure 6.1. In the figure, jagged lines represent a part of σ. Next note that if σa = σb = ∅ and σc (cid:54)= ∅, then these two lists are swapped. So Θ is pk preserving in this case as well. Now if τ b is not in one of the previous two cases and σa, σb, and σc are not all simulta- neously empty the we can check lists similar to those above to see that the peaks of both τ and τ(cid:48)(cid:48) in the range [s, t] are exactly the peaks of σa, σb, and σc together with possibly their endpoints. An illustration of this case is given in Figure 6.2. Set (cid:96)a = |σa|, (cid:96)b = |σb|, and (cid:96)c = |σc|. (a) Every peak of σa, σb and σc is a peak of τ . 30 σa σb σc πj πj−2 = τs πj−1 σa σb σc πj+1 = τt π(cid:48)(cid:48) j−1 π(cid:48)(cid:48) j π(cid:48)(cid:48) j−2 π(cid:48)(cid:48) j+1 Figure 6.2: An illustration of the case when σa, σb, and σc are all nonempty. (b) s + 1 ∈ Pk(τ ) if and only if 1 ∈ Des(σa) or (cid:96)a = 1. (c) For (cid:96)a ≥ 2: s + (cid:96)a ∈ Pk(τ ) if and only if (cid:96)a − 1 ∈ Asc(σa). (d) s + (cid:96)a + 2 ∈ Pk(τ ) if and only if 1 ∈ Des(σb) or (cid:96)b = 1. (e) For (cid:96)b ≥ 2: s + (cid:96)a + (cid:96)b + 1 ∈ Pk(τ ) if and only if (cid:96)b − 1 ∈ Asc(σb). (d) s + (cid:96)a + (cid:96)b + 3 ∈ Pk(τ ) if and only if 1 ∈ Des(σc) or (cid:96)c = 1. (e) For (cid:96)c ≥ 2: s + (cid:96)a + (cid:96)b + (cid:96)c + 2 ∈ Pk(τ ) if and only if (cid:96)c − 1 ∈ Asc(σc). The list for τ(cid:48)(cid:48) is identical. Finally, if σa = σb = σc = ∅, then Pk(τ ) ∩ [s, t] = {t − 1} and Pk(τ(cid:48)(cid:48)) ∩ [s, t] = {t − 2}. Hence the number of peaks is again preserved. Theorem 6.2. The statistics lpk, rpk, epk, udr, and (udr, pk) are shuffle compatible. The proofs for these statistics are based on the same idea as that of Theorem 6.1, but additional variants of the bijection used there are needed. We again use Corollary 3.2 part (2). So it suffices to show that if π, π(cid:48) ∈ L([m]) and σ ∈ L([n] + m) with St(π) = St(π(cid:48)) 31 then St(π  σ) = St(π(cid:48)  σ(cid:48)) for each St ∈ {lpk, rpk, epk, udr, (udr, pk)}. The main tools for this proof are the bijection Θ of Theorem 6.1 and other similar bijections that preserve these statistics and allow us to replace π with a permutation that is closer to being in our chosen set of canonical permutations, as outlined in the general approach. Proof for lpk: To obtain the shuffle compatibility of lpk we reduce permutations to the canonical set Π = {π ∈ L([m]) : Lpk(π) = {1, 3, 5, . . . , 2p − 1} for some p ≥ 0}. The proof that two permutations in this set have the same lpk is similar to the analogous statement for pk and so is omitted. We use a measure d similar to that for pk, but summing over left peaks instead. So the minimal value for a permutation with lpk(π) = p is (cid:88) d(π) = k = p2. k∈Lpk(π) If π (cid:54)∈ Π then there exists a position j ≥ 2 such that j ∈ Lpk(π), but j − 2 (cid:54)∈ Lpk(π). Let π(cid:48)(cid:48) be any permutation such that Lpk(π(cid:48)(cid:48)) = (Lpk(π) \ {j}) ∪ {j − 1}. preserving. If j ≥ 3, then the bijection of the above proof for pk suffices. Thus, assume Then it suffices to give a bijection (cid:101)Θ : π  σ → π(cid:48)(cid:48)  σ that reduces d and is lpk j = 2. To construct (cid:101)Θ we proceed in a manner similar to the proof of Theorem 5.2. Set(cid:101)π = 0π and(cid:101)π(cid:48)(cid:48) = 0π(cid:48)(cid:48) and use the notation (6.3) Sπ = {τ ∈ π  σ | τ1 = π1}. Then we have the following commutative diagram. π  σ (cid:101)Θ π  σ(cid:48)(cid:48) ι ι(cid:48)(cid:48) S(cid:101)π Θ S(cid:101)π(cid:48)(cid:48) ⊆ (cid:101)π  σ ⊆ (cid:101)π  σ(cid:48)(cid:48) 32 Here ι is the bijection which identifies τ ∈ π  σ with 0τ ∈ S(cid:101)π. The map ι(cid:48)(cid:48) is defined similarly. The map Θ is the pk-preserving bijection used in the proof of pk to move the peak at position 3 to position 2. Then (cid:101)Θ = ι(cid:48)(cid:48)−1 ◦ Θ ◦ ι (6.4) is the required bijection. It is clear that this map reduces d by 1 since Θ has this property. The injection Θ ◦ ι is lpk preserving because Θ is pk preserving and position 2 in ι(τ ) is a peak if and only if position 1 is a left peak of τ . And similarly, position 1 in ι(cid:48)(cid:48)−1Θ(ι(τ ))) is a left peak if and only if it position 2 is a peak in Θ(ι(τ )) which proves the claim and (cid:3) completes the demonstration for lpk. Proof for rpk: To obtain the shuffle compatibility of rpk we use an approach similar to that of lpk by changing our set of canonical permutations to Π = {π ∈ L([m]) : Rpk(π) = {m, m − 2, m − 4, . . . , m − 2p} for some p ≥ 0} and change our measure d of how close a permutation is to being in Π to (cid:88) (m − k). d(π) = k∈Rpk(π) We have that the minimal value for a permutation with rpk(π) = p is d(π) = p(p + 1) and if two permutations π1, π2 ∈ Π satisfy Rpk(π1) = Rpk(π2), then by Theorem 4.2 they satisfy the conclusion of (ii) of the general approach. If π (cid:54)∈ Π then there exists a position j ≤ m− 1 such that j ∈ Rpk(π), but j + 2 (cid:54)∈ Rpk(π). Let π(cid:48)(cid:48) be any permutation such that Rpk(π(cid:48)(cid:48)) = (Rpk(π) \ {j}) ∪ {j + 1}. The remainder of the proof follows the same lines as for lpk except we move peaks to the (cid:3) right instead of left using the inverse bijections. 33 Proof for epk: The shuffle compatibility of epk follows from the combination of bijections in the proofs for pk, lpk, and rpk. We use the the canonical set of permutations Π = {π ∈ L([m]) : Epk(π) = {1, 3, 5, . . . , 2p − 1} for some p ≥ 0} and measure (cid:88) k∈Epk(π) k. d(π) = We move all peaks or right peaks as far to the left as possible using the bijections from pk, lpk and inverse of the bijection from rpk can be used to move a final ascent to the left. The (cid:3) remainder of the proof is analogous to those of lpk and rpk. Proof for udr: As a first step, we observe that for a permutation π ∈ L([m]) we have udr(π) = 2 lpk(π) + χ+(0π) (6.5) since every peak of 0π is a left peak of π and involves two distinct runs. The presence of χ+(0π) accounts for the possibilities of either a final increasing run or that |π| = 1. There is nothing to prove if π = ∅ and the proof for |π| = 1 is trivial, so we will assume for the remainder of this proof that |π| ≥ 2. In this case equation (6.5) simplifies slightly to udr(π) = 2 lpk(π) + χ+(π). (6.6) Considering this equation modulo two we see that the value of udr(π) determines both lpk(π) and χ+(π), as well as conversely. We use as our canonical sets of permutations Π = {π ∈ L([m]) : Lpk(π) = {1, 3, 5, . . . 2p − 1} for some p ≥ 0}. Note this is the same canonical set as was used in the proof of lpk. Take two permutations π, π(cid:48) ∈ Π with the same udr. So, as discussed in the previous paragraph, χ+(π) = χ+(π(cid:48)). 34 It follows that Lpk(π) = Lpk(π(cid:48)). So for any σ ∈ L([n] + m) we have udr(π  σ) = udr(π(cid:48)  σ) since the bijection Φ preserves both Lpk and χ+. Therefore part (ii) of the general approach is satisfied. Our measure of how close a permutation is to being in the canonical set will be the same as it was for lpk, d(π) = (cid:88) k. k∈Lpk(σ) A permutation with lpk(π) = p is in this canonical set if and only if d(π) = p2, which is the minimal value for a permutation with udr(π) = 2p + χ+(π). Since udr(π) is determined by lpk(π) and χ+(π), to complete the proof it will suffice to show that the bijection (cid:101)Θ from the definition of (cid:101)Θ that it suffices to check that Θ itself is χ+ preserving. This is because (6.4) used in the demonstration for lpk also preserves the statistic χ+. Note first that by ι and ι(cid:48)(cid:48) essentially prepend a 0 to a permutation and then remove it. This does not affect the order relation between the final two elements of a shuffle since we have assumed that |π| ≥ 2. Since definition (6.2) for Θ uses the bijection Φ, we first show that Φ is χ+-preserving when applied to π, π(cid:48)(cid:48) ∈ L([m]) that satisfy udr(π) = udr(π(cid:48)(cid:48)). As previously noted, the assumption about udr implies χ+(π) = χ+(π(cid:48)(cid:48)). Thus, the final two positions of π and π(cid:48)(cid:48) must satisfy the same order relation. It follows that for a shuffle τ ∈ π  σ, that replacing π with π(cid:48)(cid:48) to obtain τ(cid:48) = Φ(τ ) does not change the order relation of the final two positions of τ . This means that χ+ is also preserved under Φ. Now assume that π (cid:54)∈ Π. Choose π(cid:48)(cid:48) as in equation (6.3) with the additional restriction that udr(π) = udr(π(cid:48)(cid:48)). This implies χ+(π(cid:48)(cid:48)) = χ+(π). Let τ ∈ π  σ. If j ≤ m − 2 or τm+n ∈ σ, it is clear from the definition of Θ given in (6.2) that χ+(τ ) = χ+((cid:101)Θ(τ )) and χ+ is preserved. 35 It therefore remains to check that Θ is χ+ preserving in the case that j = m − 1 and τm+n = πm. Since we have already checked that Φ preserves χ+, we only need to deal with the first two cases in the definition of Θ. • If σa (cid:54)= ∅, σb = σc = ∅, then we have m−1σaπ(cid:48)(cid:48) so that both shuffles have a descent at position m + n − 1. σaπm−2πm−1πm m−2π(cid:48)(cid:48) Θ(cid:55)→ π(cid:48)(cid:48) m • If σa = σb = ∅, σc (cid:54)= ∅, then we have πm−2πm−1σcπm Θ(cid:55)→ σcπ(cid:48)(cid:48) m−2π(cid:48)(cid:48) m−1π(cid:48)(cid:48) m. Since πm−1 is a peak we have χ+(π(cid:48)(cid:48)) = χ+(π) = 0. So, again, both shuffles have a descent at position m + n − 1 From this we can conclude that the bijections Θ, and hence (cid:101)Θ, used in the proofs for the statistics pk and lpk respectively are also udr preserving. (cid:3) Proof for (udr, pk): For any permutation π with |π| ≥ 2, we can write lpk(π) = pk(π) + χ−(π) So (6.6) becomes udr(π) = 2 pk(π) + 2χ−(π) + χ+(π). (6.7) By a parity argument like the one used for (6.6) we see that the value of (udr(π), pk(π)) uniquely determines both χ−, and χ+. Let Π0 = {π ∈ L([m]) : Lpk(π) = {2, 4, . . . 2p} for some p ≥ 0} Π1 = {π ∈ L([m]) : Lpk(π) = {1, 3, 5, . . . 2p − 1} for some p ≥ 1} 36 We then use the canonical set the disjoint union Π = Π0 (cid:116) Π1. Note that if π, π(cid:48) ∈ Π satisfy (udr(π), pk(π)) = (udr(π(cid:48)), pk(π(cid:48))) then, by the observation in the first paragraph of the proof, they are either both in Π0 or both in Π1. It follows that Lpk(π) = Lpk(π(cid:48)). Now apply the bijection Φ : π  σ → π(cid:48)  σ where we have shown earlier that Φ preserves Lpk and χ+. Also, the assumption on π and π(cid:48) implies χ−(π) = χ−(π(cid:48)). It is easy to prove that in this case Φ preserves χ−. It follows that (udr, pk) is preserved by Φ and part (ii) of our method is satisfied. Now set d(π) = (cid:88) k. k∈Lpk(π) If π (cid:54)∈ Π then we use the map Θ from the proof for pk to map π  σ to π(cid:48)(cid:48)  σ where π(cid:48)(cid:48) is given by (6.1) and has smaller d. However, if j = 3 and π1 > π2 then we do not apply Θ. (And we do not need to do so by the choice of Π.) It follows that we can always choose π(cid:48)(cid:48) so that χ−(π) = χ−(π(cid:48)(cid:48)). One can now show that in this case Θ preserves χ− similarly to the proof that the map preserves χ+. Since Θ also preserves pk, it preserves the pair (udr, pk) (cid:3) and we are done. 37 CHAPTER 7 FUTURE WORK There are still many open questions to be answered in this relatively new line of inquiry. The first natural question is whether a proof similar to those above can be given for the statistic (udr, pk, des), which was conjectured to be shuffle compatible in [3]. Question. Can a bijective proof for the statistic (udr, pk, des) be given that follows the general approach given in this dissertation? We suspect it is possible to find such a demonstration, but will require a more careful analysis of the common aspects of the bijection used for des and for pk. The fundamental obstacle in our approach to this statistic is that our bijection for pk requires moves that may not preserve the number of descents in the permutation. Other notions of shuffle compatiblitly were introduced by Grinberg in [5], so one could ask whether the same general approach can be used to give bijective proofs for his shuffle compatibility analogues. One example are the concepts of left and right shuffle compatibility defined in [5]. Definition 7.1. A permutation statistic St is called left shuffle compatible if for any two disjoint nonempty permutations π and σ with the property that π1 > σ1, the multiset {{St(τ ) |τ ∈ π  σ, τ1 = π1 }} depends only on |π|, |σ|, St(π), and St(σ). (cid:3) An analogous definition can be given for right shuffle compatibility. Our theory here would need to be modified as even Lemma 3.1 no longer holds. The bijections used there can take a shuffle starting with τ1 = π1 and swap it to one with τ1 = σ1 which is no longer in the set of left shuffles. 38 Another possible extension of this work is to permit permutations with repeated elements. For example consider the statistic maj. Then π = 4212, π(cid:48) = 2221, σ = 76 and σ(cid:48) = 98 satisfy maj(π) = maj(π(cid:48)) and maj(σ) = maj(σ(cid:48)). Note that in this case maj(π  σ) = maj(π(cid:48)  σ(cid:48)) = {{4, 5, 62, 72, 83, 92, 102, 11, 12}}. One possible approach would be to to extend the standardization map to permutations with repetitions. One possible way to do this would be to replace each maximal constant subword of π with the elements i, i + 1, . . . , j for some i, j from left to right. For example, std 24212 = 25314. One would have to then show that our approach would still work with this more general notion. The existence of a shuffle compatible permutation statistic that is not a descent statistic as constructed by O˘guz in [8] raises the question as to how one would approach giving bijective proofs to such statistics. The proof for the statistic in [8] is by an exhaustive computation for all permutations of length 4 or less, so our approach is not needed there. However, if other such statistics exist our approach no longer works. Indeed, Lemma 3.1 only holds for descent statistics and so we lose the power of Corollary 3.2 which is allows us to drastically decrease the number of cases under consideration. 39 BIBLIOGRAPHY 40 BIBLIOGRAPHY [1] Mikl´os B´ona. Combinatorics of permutations. Chapman and Hall/CRC, 2016. [2] Dominique Foata and Marcel-Paul Sch¨utzenberger. Major index and inversion number of permutations. Mathematische Nachrichten, 83(1):143–159, 1978. [3] [4] Ira M Gessel and Yan Zhuang. Shuffle-compatible permutation statistics. Advances in Mathematics, 332:85–141, 2018. IP Goulden. A bijective proof of Stanley’s shuffling theorem. Transactions of the American Mathematical Society, 288(1):147–160, 1985. [5] D. Grinberg. Shuffle-compatible permutation statistics II: the exterior peak set. ArXiv e-prints, June 2018. [6] Sumanta Guha and Sriram Padmanabhan. A new derivation of the generating function for the major index. Discrete Mathematics, 81(2):211–215, 1990. [7] Mordechai Novick. A bijective proof of a major index theorem of Garsia and Gessel. The Electronic Journal of Combinatorics, 17(1):64, 2010. [8] Ezgi Kantarcı O˘guz. A counter example to the shuffle compatiblity conjecture. arXiv preprint arXiv:1807.01398, 2018. [9] Richard P. Stanley. Ordered structures and partitions. American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. [10] John Stembridge. Enriched P -partitions. Transactions of the American Mathematical Society, 349(2):763–788, 1997. 41