COMBINATORIAL PROPERTIES OF PERMUTATIONS AND PERMUTATION STATISTICS By Quinn Minnich A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of Mathematicsβ€”Doctor of Philosophy 2023 ABSTRACT Some of the most interesting and fundamental objects in the study of combinatorics are permuta- tions. Permutations are typically defined to be an arrangement of the numbers {1, 2, . . . 𝑛}, and they appear in countless problems and applications throughout mathematics. Sometimes we are particu- larly interested in observing or counting some key property of a given permutation. A permutation statistic is a function that takes a particular permutation and returns specific information about it, such as how many numbers are only adjacent to smaller numbers. Each permutation statistic gives rise to many counting questions, such as finding all possible permutations which have that particular statistic, or perhaps finding a subset of those permutations where that statistic is maximized. These numbers can sometimes be described by generating functions or polynomials which give light to the beauty and structure of mathematics, sometimes even in fields outside combinatorics. Some examples of this will be given in Chapter 1. In the rest of this dissertation, we will explore several of these statistics including new ones and variations on some of the more well known statistics. In the Chapter 2, we focus on shuffle compatibility for cyclic permutations. The shuffle of two permutations is the set of all permutations that have both original permutations as sub-sequences. A statistic is said to be shuffle compatible if its values over all possible shuffles of two permutations is completely determined by the statistic on the two original permutations, together with their lengths. Shuffle compatibility is implicit in Stanley’s work on 𝑃-partitions and was also studied by Gessel and Zhuang. Shuffle compatibility is also useful in studying mathematical objects outside of combinatorics, such as quasisymmetric functions. More recently, an analogous definition of shuffle compatibility has been defined for cyclic permutations, which are permutations arranged in a circle so that the last element is considered adjacent to the first. In Chapter 2, we study a Lifting Lemma that can prove shuffle compatibility for some statistics on circular permutations based on known results for those statistics on linear permutations. One well-studied permutation statistic is the peak set, which is the set of all indices of a permutation where an element is adjacent to two smaller elements. Primarily spearheaded by Davis, Nelson, Petersen, and Tenner, there has been recent interest in studying an analogue of this statistic known as the pinnacle set, which are the values of the elements at the indices of the peak set. Davis et al. proposed a number of unanswered questions about this statistic, which later led to a series of papers on the topic. In Chapter 3 we will present multiple results that attempt to answer some of these questions, including some original formulas and also some alternate combinatorial proofs of known results. These will include a bΔ³ection for counting the number of sets that could be the pinnacle set of some permutation, formulas and recursions for counting the number of permutations with a given pinnacle set, along with a new proof for a weighted sum of those numbers, and a recursion for counting the number of distinct orderings in which the elements of a pinnacle set can appear within a permutation. Copyright by QUINN MINNICH 2023 Ad Majorem Dei Gloriam v ACKNOWLEDGEMENTS First and foremost, I would like to thank my advisor, Dr. Bruce Sagan, for all his invaluable help and patience in everything from research to proofreading. I will always be grateful for his example as a speaker who could present complex ideas while somehow keeping it accessible even for undergraduates. I would also like to thank my dissertation committee for their time and input. Additionally, I would like to thank my parents and family who supported me from afar (for whatever reason, it was while visiting home that I came up with a lot of my proof ideas). Finally, I would like to extend an enormous thank you to many of my fellow Ph. D. candidates for helping me survive my first year, giving me the insight I needed to learn far more in mathematics than I would have been able to on my own, and also for providing an encouraging community and several invaluable friendships that will likely stay with me for life. vi TABLE OF CONTENTS CHAPTER 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Definitions, notation, and motivation . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Chapter 2 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Chapter 3 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 CHAPTER 2 CYCLIC SHUFFLING . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 The lifting lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Remarks and an open question . . . . . . . . . . . . . . . . . . . . . . . . . . 19 CHAPTER 3 PINNACLE SETS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 Counting the number of admissible pinnacle sets . . . . . . . . . . . . . . . . 21 3.2 Permutations with a given pinnacle set . . . . . . . . . . . . . . . . . . . . . . 27 3.3 A formula for the weighted sum of 𝑝 𝑛 (𝑃) . . . . . . . . . . . . . . . . . . . . 42 3.4 Recursion for admissible orderings . . . . . . . . . . . . . . . . . . . . . . . . 54 3.5 Block representation of pinnacle sets . . . . . . . . . . . . . . . . . . . . . . . 62 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 vii CHAPTER 1 INTRODUCTION 1.1 Definitions, notation, and motivation Throughout, we will let N and P be the nonnegative and positive integers, respectively. Given π‘š, 𝑛 ∈ P we use the notation [π‘š, 𝑛] = {π‘š, π‘š + 1, . . . , 𝑛} for the interval they define, and abbreviate [1, 𝑛] to [𝑛]. Let 𝔖𝑛 be the symmetric group of all permutations πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› of [𝑛] written in one-line notation. If πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› then 𝑛 is called the length of πœ‹, written #πœ‹ = |πœ‹| = 𝑛. The hash symbol and absolute value sign will also be used for the cardinality of a set. In fact, we will often treat permutations as sets if no problem will result and write things such as π‘₯ ∈ πœ‹ in place of the more cumbersome πœ‹π‘– = π‘₯ for some 𝑖. Given a finite 𝐴 βŠ‚ P then a linear permutation of 𝐴 is a linear arrangement πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› of the elements of 𝐴. This is a generalization of permutations in 𝔖𝑛 which are just linear arrangements of 𝐴 = [𝑛]. We let 𝐿 ( 𝐴) = {πœ‹ | πœ‹ is a linear permutation of 𝐴}. We often drop β€œlinear" if it is understood from context. For example, 𝐿 ({1, 3, 6}) = {136, 163, 316, 361, 613, 631}. A (linear) permutation statistic is a function St whose domain is all linear permutations. Several common example are as follows. A permutation πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› has descent set Des πœ‹ = {𝑖 | πœ‹π‘– > πœ‹π‘–+1 }, descent number des πœ‹ = # Des πœ‹, peak set Pk πœ‹ = {𝑖 | πœ‹π‘–βˆ’1 < πœ‹π‘– > πœ‹π‘–+1 }, peak number pk πœ‹ = # Pk πœ‹, 1 major index βˆ‘οΈ maj πœ‹ = 𝑖, π‘–βˆˆDes πœ‹ inversion set Inv πœ‹ = {(𝑖, 𝑗) | 𝑖 < 𝑗 and πœ‹π‘– > πœ‹ 𝑗 }, and inversion number inv πœ‹ = # Inv πœ‹. To illustrate, if πœ‹ = 4218596 then Des πœ‹ = {1, 2, 4, 6}, des πœ‹ = 4, Pk πœ‹ = {4, 6}, pk πœ‹ = 2, maj πœ‹ = 1 + 2 + 4 + 6 = 13, Inv πœ‹ = {(1, 2), (1, 3), (2, 3), (4, 5), (4, 7), (6, 7)}, and inv πœ‹ = 6. We will be especially concerned with a particular type of statistic which is determined by the descent set in the following sense. Statistic St is a descent statistic if Des πœ‹ = Des 𝜎 and #πœ‹ = #𝜎 implies St πœ‹ = St 𝜎. Note that Des itself, des, Pk, pk, and maj are all descent statistics. A statistic which is not a descent statistic would be inv πœ‹ since 312 and 213 both have the same Des but different inv. We will often need to evaluate a statistic St on a set of permutations Ξ . So we define the distribution of St over Ξ  to be St Ξ  = {{St πœ‹ | πœ‹ ∈ Ξ }}. Note that this is a set with multiplicity or multiset since St may evaluate to the same thing on various members of Ξ . We will sometimes use exponents to denote multiplicities where, as usual, no exponent means multiplicity 1. For example des{123, 132, 312, 321} = {{0, 1, 1, 2}} = {{0, 12 , 2}}. Permutation statistics are interesting objects of study not only because of their relation to other areas of mathematics such as quasisymmetric functions, but also for their innate beauty and structure. For example, while maj and inv typically evaluate to different numbers on the same permutation, their distributions over 𝔖𝑛 are always the same. In general, statistics with the same distribution as maj and inv are known as Mahonian statistics, and all of them have the following beautiful generating function: βˆ‘οΈ π‘ž maj πœ‹ = [𝑛] π‘ž !, πœ‹βˆˆπ”–π‘› 2 where [𝑛] π‘ž ! = (1)(1 + π‘ž)(1 + π‘ž + π‘ž 2 ) Β· Β· Β· (1 + π‘ž + π‘ž 2 Β· Β· Β· π‘ž π‘›βˆ’1 ). This is known as the π‘ž-factorial, which derives its name from the property that if we substitute π‘ž = 1, then we get [𝑛] π‘ž ! = 𝑛!. Notice that in our generating function, letting π‘ž = 1 will result in a sum over all permutations in 𝔖𝑛 on the left-hand side, which is then equal to 𝑛! as expected. In addition to the factorial, π‘ž-analogues exist for many other numbers as well including binomial coefficients, where each factorial is replaced with the corresponding π‘ž-factorial. The study of these different π‘ž-analogies is a subject in its own right, and Mahonian statistics is only one of many places where they naturally appear. Another class of statistics with interesting generating functions is known as the Eularian statistics, which consist of all those statistics whose distribution over 𝔖𝑛 is the same as des. Their generating function is as follows: βˆ‘οΈ βˆ‘οΈ π‘ž des πœ‹ = (1 βˆ’ π‘ž) 𝑛+1 (π‘š + 1) 𝑛 π‘ž π‘š . πœ‹βˆˆπ”–π‘› π‘šβ‰₯0 This distribution is so important that it is denoted by 𝐴𝑛 (π‘ž) and called the π‘›π‘‘β„Ž Eularian polynomial. Additionally, these polynomials themselves have an exponential generating function given by βˆ‘οΈ π‘₯𝑛 π‘žβˆ’1 𝐴𝑛 (π‘ž) = . 𝑛β‰₯0 𝑛! π‘ž βˆ’ 𝑒 (π‘žβˆ’1)π‘₯ Even some of the non-Eularian descent statistics turn out to be closely related to 𝐴𝑛 (π‘ž). For example, if we define the generating function for pk as follows: βˆ‘οΈ 𝑃𝑛 (π‘ž) = π‘ž pk πœ‹ , πœ‹βˆˆπ”–π‘› then we get the relation,   (1 + π‘ž) π‘›βˆ’1 4π‘ž 𝐴𝑛 (π‘ž) = 𝑃𝑛 . 2π‘›βˆ’1 (1 + π‘ž) 2 Our goal will be to examine analogues of a few of these permutation statistics. 1.2 Chapter 2 introduction If πœ‹ ∈ 𝐿( 𝐴) and 𝜎 ∈ 𝐿(𝐡) where 𝐴 ∩ 𝐡 = βˆ… then these permutations have shuffle set πœ‹  𝜎 = {𝜏 ∈ 𝐿( 𝐴 ⊎ 𝐡) | πœ‹, 𝜎 are subwords of 𝜏} 3 where a subword of a permutation 𝜏 is a subsequence of (not necessarily consecutive) elements of 𝜏. For example, 25  73 = {2573, 2753, 2735, 7253, 7235, 7325}. (1.1) Whenever we write the shuffle of two permutations, we will tacitly assume that they are from disjoint sets. An important use of the shuffle set is in computing the product of two fundamental quasisym- metric functions, which form a basis for the algebra QSym of quasisymmetric functions. These fundamental functions are indexed by the descent sets of permutations, and when two are multiplied together the result is a sum of fundamental quasisymmetric functions over the descent sets of all shuffles of the original permutations. In order to show that multiplication is well defined (and hence that QSym really is an algebra), one needs shuffle compatibility as defined below. More information about QSym can be found in the texts of Luoto, Mykytiuk, and van Willigenburg [18], Sagan [23], or Stanley [25]. Roughly speaking, a statistic St is shuffle compatible if the distribution of St over πœ‹  𝜎 depends only on St πœ‹, St 𝜎, and the lengths #πœ‹ and #𝜎. To be precise, St is shuffle compatible if for all quadruples πœ‹, πœ‹β€², 𝜎, πœŽβ€² with St πœ‹ = St πœ‹β€², St 𝜎 = St πœŽβ€², #πœ‹ = #πœ‹β€², and #𝜎 = #πœŽβ€² we have St(πœ‹  𝜎) = St(πœ‹β€²  πœŽβ€²). For example, from equation (1.1) it is easy to see that des(25  73) = {{13, 23 }} The reader can check that this is also the distribution des(12  43) which is because des is shuffle compatible. Shuffle compatibility is implicit in Stanley’s theory of 𝑃-partitions [24] and he proved a result implying the shuffle compatibility of des. Gessel and Zhuang [12] were the first to define the concept explicitly and prove many shuffle compatibility results, including those for some of the other statistics defined previously. 4 Theorem 1.2.1 ([12]). The statistics Des, des, Pk, pk are all shuffle compatible. Other work on shuffle compatibility has been done by Baker-Jarvis and Sagan [2], by Oğuz [20], and by Grinberg [15]. Recently Adin, Gessel, Reiner, and Roichman [1] introduced a cyclic version of quasisymmetric functions with a corresponding cyclic shuffle operation. A linear permutation πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› has a corresponding cyclic permutation [πœ‹] which is the set of all its rotations, namely [πœ‹] = {πœ‹1 πœ‹2 . . . , πœ‹π‘› , πœ‹2 . . . , πœ‹π‘› πœ‹1 , . . . , πœ‹π‘› πœ‹1 . . . πœ‹π‘›βˆ’1 }. For example [3725] = {3725, 7253, 2537, 5372} so that [3725] = [7253] = [2537] = [5372]. The reader should bear in mind the difference between the notation [𝑛] for an interval of integers and [πœ‹] for a cyclic permutation. We let 𝐢 ( 𝐴) = {[πœ‹] | [πœ‹] is a cyclic permutation of 𝐴}. To illustrate 𝐢 ({2, 3, 5, 7}) = {[2357], [2375], [2537], [2735], [2573], [2753]}. We can lift the linear permutation statistics we have introduced to the cyclic realm as follows. Define the cyclic descent set and cyclic descent number for a linear permutation πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› to be cDes πœ‹ = {𝑖 ∈ [𝑛] | πœ‹π‘– > πœ‹π‘–+1 where 𝑖 is taken modulo 𝑛} 5 and cdes πœ‹ = # cDes πœ‹, respectively. Returning to πœ‹ = 4218596 we have cDes πœ‹ = {1, 2, 4, 6, 7} and cdes πœ‹ = 5. Now a cyclic permutation [πœ‹] will have cyclic descent set cDes[πœ‹] = {{cDes 𝜎 | 𝜎 ∈ [πœ‹]}} and cyclic descent number cdes[πœ‹] = cdes πœ‹. Note that cdes[πœ‹] is well defined since all elements of [πœ‹] have the same number of cyclic descents. To illustrate cDes[3725] = {{cDes 3725, cDes 7253, cDes 2537, cDes 5372}} = {{ {1, 3}2 , {2, 4}2 }} and cdes[3725] = 2. An important point later will be that if 𝑆 is one of the sets in cDes[πœ‹] then all of the other member sets can be obtained by adding 𝑖 to the elements of 𝑆 modulo 𝑛 = #πœ‹ as 𝑖 runs over [𝑛 βˆ’ 1]. We deal with peaks in a similar manner, defining the cyclic peak set and cyclic peak number in the linear case by cPk πœ‹ = {𝑖 ∈ [𝑛] | πœ‹π‘–βˆ’1 < πœ‹π‘– > πœ‹π‘–+1 where 𝑖 is taken modulo 𝑛} and cpk πœ‹ = # cPk πœ‹, respectively. For πœ‹ = 4218593 we have cPk πœ‹ = {1, 4, 6} and cpk πœ‹ = 3. The extension to cyclic permutations is as expected cPk[πœ‹] = {{cPk 𝜎 | 𝜎 ∈ [πœ‹]}} and cpk[πœ‹] = cpk πœ‹. 6 In general, a cyclic permutation statistic is any function cSt whose domain is cyclic permutations. And cSt is a cyclic descent statistic if cDes[πœ‹] = cDes[𝜎] and #πœ‹ = #𝜎 implies cSt[πœ‹] = cSt[𝜎]. All four of our cyclic statistics are cyclic descent statistics. The definitions for shuffles follow the same pattern already established. Given [πœ‹] ∈ 𝐢 ( 𝐴) and [𝜎] ∈ 𝐢 (𝐡) where 𝐴 ∩ 𝐡 = βˆ… we define their cyclic shuffle set to be [πœ‹]  [𝜎] = {[𝜏] ∈ 𝐢 ( 𝐴 ⊎ 𝐡) | [πœ‹], [𝜎] are circular subwords of [𝜏]}. Alternatively, there are rotations πœ‹β€² and πœŽβ€² of πœ‹ and 𝜎, respectively, which are both linear subwords of 𝜏. To illustrate, [13]  [24] = {[1324], [1342], [1234], [1432], [1243], [1423]}. (1.2) Call a cyclic permutation statistic cSt cyclic shuffle compatible if for all quadruples [πœ‹], [πœ‹β€²], [𝜎], [πœŽβ€²] with cSt[πœ‹] = cSt[πœ‹β€²], cSt[𝜎] = cSt[πœŽβ€²], #πœ‹ = #πœ‹β€², and #𝜎 = #πœŽβ€² we have cSt([πœ‹]  [𝜎]) = St([πœ‹β€²]  [πœŽβ€²]). The aim of the Chapter 2 will be to study this concept. In particular, we will prove the following theorem, which was my contribution to the paper I worked on with Domagalski, Liang, Sagan, Schmidt, and Sietsema [7]. Theorem 1.2.2. The statistics cDes, cdes, cPk, cpk are all cyclic shuffle compatible. Our primary tool for doing this will be a Lifting Lemma (2.1.3) which can prove shuffle compatibility for certain cyclic statistic from the shuffle compatibility of their linear counterparts. The theorem also requires a certain property pertaining to how the largest element of a circular permutation contributes to the given statistic, but thankfully the property holds for the above statistics. 7 One interesting nuance about many linear permutation statistics, including those mentioned above, is that they depend heavily on the indices of certain elements within a permutation. Because of this, it can sometimes be difficult to define the cyclic version of these statistics, and when we do, it is not always obvious which properties or formulas from the linear case carry through. One way of side-stepping this difficulty however is to consider statistics which depend on the values within a permutation as opposed to the indices. In the next chapter, we focus on a particular statistic with this property known as the pinnacle set. 1.3 Chapter 3 introduction Define the pinnacle set of a permutation πœ‹ ∈ 𝔖𝑛 to be Pin πœ‹ = {πœ‹π‘– | πœ‹π‘–βˆ’1 < πœ‹π‘– > πœ‹π‘–+1 } βŠ† [3, 𝑛]. Pinnacle sets have generated a lot of recent interest in part because of their close relation to the peak set, since the pinnacle set is just the values at the indices of the peak set. Peak sets have been widely studied with many interesting results. For instance, it is easy to see that 𝑆 βŠ† [2, 𝑛 βˆ’ 1] is the peak set of some πœ‹ ∈ 𝔖𝑛 if and only if no two elements of 𝑆 are consecutive, and so the number of possible peak sets is a Fibonacci number. One could also ask how many permutations have a given peak set. This question was answered by Billey, Burdzy and Sagan. Theorem 1.3.1 ([3]). If 𝑛 ∈ P and 𝑆 βŠ† [2, 𝑛] then #{πœ‹ ∈ 𝔖𝑛 | Pk πœ‹ = 𝑆} = 𝑝(𝑆; 𝑛)2π‘›βˆ’#π‘†βˆ’1 where 𝑝(𝑆; 𝑛) is a polynomial in 𝑛 depending on 𝑆. It is natural to study the values at the peak indices. Some of the initial work related pinnacle sets (although under a different name) was done by Strehl in [26] where he studied permutations in which pinnacles and non-pinnacles alternated. The concept was rediscovered independently by Davis et al. in [5] where they proved several initial results, including that the number of sets 𝑃 βŠ† [𝑛] that could be a pinnacle set for some permutation is counted by a central binomial coefficient. Not long afterwards Domagalski et al. gave a formula in [9] for the number of permutations in 𝔖𝑛 8 having a given pinnacle set 𝑃 using the principle of inclusion and exclusion. This was a paper that I coauthored, and those results in it that were originally mine have been included as the first two main results in Chapter 3. Around the same time, Diaz-Lopez et al. gave a different formula for the same number by keeping track of vale sets, which are those elements of a permutation πœ‹ smaller than those on either side. Both of these formulas however ran in time exponential in the number of elements of 𝑃. Shortly afterwards, Falque et al. published some results in [10] which included a recursive formula for the number of permutations having a fixed pinnacle set that ran in time 𝑂 (π‘›π‘˜ 2 ) where π‘˜ is the number of elements in 𝑃 and 𝑛 is the length of the permutations being counted. Finally, both Fang [11] and myself [19], Theroem 3.5.3 below, independently proved results which computed the number in 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 4 ) time. In addition to results that pertained to the number of permutations with a given pinnacle set, Rusu in [21] studied transforming a permutation with a given pinnacle set into another permutation with the same pinnacle set such that the pinnacle set was preserved in all intermediate steps of the transformation. Additional work was also done by Rusu and Tenner in [22] characterizing the orderings in which the elements of some pinnacle set 𝑃 could appear within a permutation with pinnacle set 𝑃. Later, both Fang [11] and Minnich [19], Theorem 3.4.5 below, independently found means of calculating the number of such orderings of some pinnacle set 𝑃 with π‘˜ elements that ran in 𝑂 (π‘˜ 2 ) time. Following Davis et al. we call a set 𝑃 an admissible pinnacle set if there is some permutation πœ‹ with Pin πœ‹ = 𝑃. Note that if 𝑃 = Pin πœ‹ for some πœ‹ ∈ 𝔖𝑛 then 𝑃 is also a pinnacle set of some πœ‹β€² ∈ 𝔖𝑛′ for all 𝑛′ β‰₯ 𝑛 since one can just add values larger than 𝑛 to the beginning of πœ‹ in decreasing order. Davis et al. found a criterion for 𝑃 to be admissible which will be useful in the sequel. This result was stated in recursive fashion, but it is clearly equivalent to the following non-recursive version. Theorem 1.3.2 ([5]). Let 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } βŠ‚ P. The set 𝑃 is an admissible pinnacle set 9 if and only if we have 𝑝𝑖 > 2𝑖 for all 𝑖 ∈ [𝑑]. In Chapter 3 we will present many more results on pinnacle sets, including a bΔ³ection for counting the number of admissible pinnacle sets (Theorem 3.1.4), multiple methods for counting the number of permutations with a given pinnacle set (Theorem 3.2.1 and Theorem 3.5.3), and a method for counting the number of orderings in which the elements of some pinnacle set 𝑃 could appear within a permutation with pinnacle set 𝑃 (Theorem 3.4.5). 10 CHAPTER 2 CYCLIC SHUFFLING This chapter will be structured as follows. Rather than proving each of the cases of Theorem 1.2.2 in an ad hoc manner, we will develop a method for lifting linear shuffle compatibility results to cyclic ones. This will be done in the next section. Then in Section 2.2 we will apply our Lifting Lemma to each of the four statistics in turn. Finally, we will end with a section of comments and a future direction for research. We will first set some notation. In the notations like 𝐢 ( 𝐴) and 𝐿( 𝐴) we will often drop the parentheses if they would cause double delimiters. For example 𝐿 [𝑛] is all the linear permutations of [𝑛]. If 𝐴 βŠ‚ P and 𝑛 ∈ N then let 𝐴 + 𝑛 = {π‘Ž + 𝑛 | π‘Ž ∈ 𝐴}. In particular, [π‘š] + 𝑛 = {𝑛 + 1, 𝑛 + 2, . . . , 𝑛 + π‘š}. We will also need to add integers to sets modulo some π‘š ∈ P. So if 𝐴 βŠ† [π‘š] then define 𝐴 + 𝑛 (mod π‘š) = {π‘Ž + 𝑛 (mod π‘š) | π‘Ž ∈ 𝐴} where the representatives are chosen to be in [π‘š]. For example if 𝐴 = {2, 4, 5} and π‘š = 6 then 𝐴 + 3 = {5, 7, 8} and 𝐴 + 3 (mod 6) = {1, 2, 5}. We will also need the notion of standardization. Suppose 𝐴, 𝐡 βŠ‚ P with #𝐴 = #𝐡 = 𝑛 and πœ‹ = πœ‹1 πœ‹2 . . . πœ‹π‘› ∈ 𝐿 ( 𝐴). The standardization of πœ‹ to 𝐡 is std𝐡 πœ‹ = 𝑓 (πœ‹1 ) 𝑓 (πœ‹2 ) . . . 𝑓 (πœ‹π‘› ) ∈ 𝐿 (𝐡) 11 where 𝑓 : 𝐴 β†’ 𝐡 is the unique order-preserving bΔ³ection between 𝐴 and 𝐡. To illustrate, if 𝐴 = {2, 4, 6, 7} and 𝐡 = {1, 3, 8, 9} then std𝐡 (4762) = 3981. If 𝐡 = [𝑛] then we write just std πœ‹ for std [𝑛] πœ‹ and call this the standardization of πœ‹. Standardization for cyclic permutations is defined in the analogous manner. Finally, if Ξ  and Ξ β€² are sets of permutations and St is a statistic, then a function 𝑓 : Ξ  β†’ Ξ β€² is St-preserving if St 𝑓 (πœ‹) = St πœ‹ for all πœ‹ ∈ Ξ . Functions preserving cyclic permutation statistics are defined in the obvious way. 2.1 The lifting lemma In this section we will provide a general method for proving cyclic shuffle compatibility results as corollaries of linear ones. We start with a result about cyclic descent statistics which is a cyclic analogue of one in the linear case [2]. Lemma 2.1.1. Let cSt be a cyclic descent statistic. For any four cyclic permutations [πœ‹], [πœ‹β€²], [𝜎], [πœŽβ€²] such that std[πœ‹] = std[πœ‹β€²] and std[𝜎] = std[πœŽβ€²] we have cSt([πœ‹]  [𝜎]) = cSt([πœ‹β€²]  [πœŽβ€²]). Proof. Since cSt is a cyclic descent statistic, its values only depends on the relative order of adjacent elements. So it suffices to prove the case when [πœ‹] ⊎ [𝜎] = [πœ‹β€²] ⊎ [πœŽβ€²] = [π‘š + 𝑛] where π‘š = #πœ‹ = #πœ‹β€² and 𝑛 = #𝜎 = #πœŽβ€². For simplicity, let 𝐴 = [π‘š] and 𝐡 = [𝑛] + π‘š. We claim that it suffices to find, for any πœ‹ and 𝜎 as in the previous paragraph, a cSt-preserving bΔ³ection [πœ‹]  [𝜎] β†’ std 𝐴 [πœ‹]  std𝐡 [𝜎]. 12 For from this map and the hypothesis of the lemma we have cSt( [πœ‹]  [𝜎]) = cSt(std 𝐴 [πœ‹]  std𝐡 [𝜎]) = cSt(std 𝐴 [πœ‹β€²]  std𝐡 [πœŽβ€²]) = cSt([πœ‹β€²]  [πœŽβ€²]). We will show the existence of this bΔ³ection by induction on the size of the set of what we will call out-of-order pairs 𝑂 = {(𝑖, 𝑗) ∈ πœ‹ Γ— 𝜎 | 𝑖 > 𝑗 }. If #𝑂 = 0 then [πœ‹] ∈ 𝐢 ( 𝐴) and [𝜎] ∈ 𝐢 (𝐡). It follows that [πœ‹] = std 𝐴 [πœ‹] and [𝜎] = std𝐡 [𝜎] so the identity map will do. For the induction step, let #𝑂 > 0. Then there must be a pair (𝑖, 𝑖 βˆ’ 1) ∈ 𝑂. Let πœ‹β€²β€² = (𝑖 βˆ’ 1, 𝑖)πœ‹ and πœŽβ€²β€² = (𝑖 βˆ’ 1, 𝑖)𝜎 where (𝑖 βˆ’ 1, 𝑖) is the transposition which exchanges 𝑖 βˆ’ 1 and 𝑖. We will be done if we can construct a cSt preserving bΔ³ection 𝑇𝑖 : [πœ‹]  [𝜎] β†’ [πœ‹β€²β€²]  [πœŽβ€²β€²]. This is because πœ‹β€²β€², πœŽβ€²β€² have fewer out-of-order pairs and so, by induction, there is a cSt-preserving bΔ³ection [πœ‹β€²β€²]  [πœŽβ€²β€²] β†’ std 𝐴 [πœ‹β€²β€²]  std𝐡 [πœŽβ€²β€²] which, when composed with 𝑇𝑖 , will finish the construction. Define 𝑇𝑖 by ο£±  ο£² [(𝑖 βˆ’ 1, 𝑖)𝜏] if 𝑖 βˆ’ 1, 𝑖 are not cyclically adjacent in [𝜏],    𝑇𝑖 [𝜏] =   [𝜏] else.   ο£³ We must first check that 𝑇𝑖 is well defined in that 𝑇𝑖 [𝜏] ∈ [πœ‹β€²β€²]  [πœŽβ€²β€²]. This is true if 𝑖 βˆ’ 1 and 𝑖 are not cyclically adjacent since 𝑖 βˆ’ 1 and 𝑖 have been swapped in all three cyclic permutations involved. If they are adjacent then the relative order of the elements of [𝜏] corresponding to [πœ‹] and [πœ‹β€²β€²] are the same, and similarly for [𝜎] and [πœŽβ€²β€²]. So leaving [𝜏] fixed again gives a shuffle in the range. Finally, we need to verify that 𝑇𝑖 is cSt preserving. Since cSt is a descent statistic, it suffices to show that 𝑇𝑖 is cDes preserving. Certainly this is true of [𝜏] is fixed. And if it is not, then 13 𝑖 βˆ’ 1, 𝑖 are not cyclically adjacent in [𝜏]. But switching 𝑖 βˆ’ 1 and 𝑖 could only change a cyclic descent into a cyclic ascent or vice-versa if these two elements were adjacent. So in this case cDes[(𝑖 βˆ’ 1, 𝑖)𝜏] = cDes[𝜏] and we are done. As an example of the map 𝑇𝑖 , consider the shuffle set in (1.2). Here we can take 𝑖 = 3 since 3 ∈ 13 and 2 ∈ 24. For [𝜏] = [1324] we have 2 and 3 cyclically adjacent so 𝑇3 [1324] = [1324] ∈ [12]  [34] as desired. On the other hand, in [1342] the 2 and 3 are not cyclically adjacent so 𝑇3 [1342] = [1243]. Note that [1243] ∈ [12]  [34] and cDes[1243] = {{ {1, 2}, {2, 3}, {3, 4}, {1, 4} }} = cDes[1342]. We can use the previous lemma to drastically cut down on the number of cases which need to be checked to obtain cyclic shuffle compatibility. In particular, the component permutations in the shuffles to be considered can be on consecutive intervals of integers. And one can keep one component of the shuffle constant while the other varies. Corollary 2.1.2. Suppose that cSt is cyclic descent statistic. The following are equivalent. (a) The statistic cSt is cyclic shuffle compatible. (b) If cSt([πœ‹]) = cSt([πœ‹β€²]) where [πœ‹], [πœ‹β€²] ∈ 𝐢 [π‘š] and [𝜎] ∈ 𝐢 ([𝑛] + π‘š) for some π‘š, 𝑛 ∈ N then cSt([πœ‹]  [𝜎]) = cSt([πœ‹β€²]  [𝜎]). (c) If cSt([𝜎]) = cSt([πœŽβ€²]) where [𝜎], [πœŽβ€²] ∈ 𝐢 ([𝑛] + π‘š) and [πœ‹] ∈ 𝐢 [π‘š] for some π‘š, 𝑛 ∈ N then cSt([πœ‹]  [𝜎]) = cSt([πœ‹]  [πœŽβ€²]). 14 Proof. We will prove the equivalence of (a) and (b) since the equivalence of (a) and (c) is similar. Clearly (a) implies (b). For the converse, let πœ‹, πœ‹β€², 𝜎, πœŽβ€² be any four permutations satisfying the hypothesis of the cyclic shuffle compatible definition and let π‘š = #πœ‹ = #πœ‹β€², 𝑛 = #𝜎 = #πœŽβ€². Also let 𝐴 = [π‘š], 𝐡 = [𝑛] + π‘š, 𝐴′ = [π‘š] + 𝑛, and 𝐡′ = [𝑛]. Then, using Lemma 2.1.1 and (b) alternately cSt([πœ‹]  [𝜎]) = cSt(std 𝐴 [πœ‹]  std𝐡 [𝜎]) = cSt(std 𝐴 [πœ‹β€²]  std𝐡 [𝜎]) = cSt(std 𝐴 [πœ‹β€²]  std𝐡 [𝜎]) β€² β€² = cSt(std 𝐴 [πœ‹β€²]  std𝐡 [πœŽβ€²]) β€² β€² = cSt([πœ‹β€²]  [πœŽβ€²]) which is what we wished to prove. In order to prove the Lifting Lemma, we will need to define two functions. For 𝑖 ∈ [𝑛] we construct the splitting map 𝑆𝑖 : 𝐢 [𝑛] β†’ 𝐿 [𝑛] as follows. If [πœ‹] ∈ 𝐢 [𝑛] then let 𝑆𝑖 [πœ‹] be the unique linear permutation in [πœ‹] which starts with 𝑖. For example, 𝑆3 [45132] = 32451. Also define the maximum removal map 𝑀 : 𝐢 [𝑛] β†’ 𝐿 [𝑛 βˆ’ 1] by first applying 𝑆𝑛 to [πœ‹] and then removing the initial 𝑛. To illustrate 𝑀 [45132] = 1324. Note that 𝑀 is a bΔ³ection. We similarly define 𝑀 : 𝐢 ([𝑛] + π‘š) β†’ 𝐿 ([𝑛 βˆ’ 1] + π‘š) using π‘š + 𝑛 in place of 𝑛, as in 𝑀 [67354] = 3546. Finally, we say that 𝑦 is between π‘₯ and 𝑧 in [πœ‹] if this is true of any linear permutation in [πœ‹] where π‘₯ occurs to the left of 𝑧. If [πœ‹] ∈ 𝐢 [π‘š], 𝑖 ∈ [π‘š], and [𝜎] ∈ 𝐢 ([𝑛] + π‘š) define [πœ‹] 𝑖 [𝜎] = {[𝜏] ∈ [πœ‹]  [𝜎] | only elements of 𝜎 are between π‘š + 𝑛 and 𝑖 in [𝜏]}. 15 For example, [12]  [34] = {[1234], [1243], [1324], [1423], [1342], [1432]} with [12] 1 [34] = {[1234], [1243], [1324]} and [12] 2 [34] = {[1423], [1342], [1432]}. Clearly [πœ‹]  [𝜎] is the disjoint union of the [πœ‹] 𝑖 [𝜎] for 𝑖 ∈ [π‘š]. Lemma 2.1.3 (Lifting Lemma). Let cSt be a cyclic descent statistic and St be a shuffle compatible linear descent statistic such that the following conditions hold. (a) For any [𝜏], [πœβ€²] of the same length St(𝑀 [𝜏]) = St(𝑀 [πœβ€²]) implies cSt[𝜏] = cSt[πœβ€²]. (b) Given any [πœ‹], [πœ‹β€²] ∈ 𝐢 [π‘š] such that cSt[πœ‹] = cSt[πœ‹β€²], there exists a bΔ³ection 𝑓 : [π‘š] β†’ [π‘š] such that for all 𝑖 and 𝑗 = 𝑓 (𝑖) St(𝑆𝑖 [πœ‹]) = St(𝑆 𝑗 [πœ‹β€²]). Then cSt is cyclic shuffle compatible. Proof. By Corollary 2.1.2, it suffices to show that if [πœ‹], [πœ‹β€²] are as given in (b) and 𝜎 ∈ 𝐢 ([𝑛] +π‘š) then cSt( [πœ‹]  [𝜎]) = cSt([πœ‹β€²]  [𝜎]). The remarks preceding the lemma show that this reduces to proving cSt([πœ‹] 𝑖 [𝜎]) = cSt([πœ‹β€²]  𝑗 [𝜎]) (2.1) for all 𝑖 ∈ [π‘š] and 𝑗 = 𝑓 (𝑖). It follows that St(𝑆𝑖 [πœ‹]) = St(𝑆 𝑗 [πœ‹β€²]) by (b). So, since St is shuffle compatible, we have St(𝑆𝑖 [πœ‹]  πœŽβ€²) = St(𝑆 𝑗 [πœ‹β€²]  πœŽβ€²) where πœŽβ€² = 𝑀 [𝜎]. Thus there is an St-preserving bΔ³ection πœƒ : 𝑆𝑖 [πœ‹]  πœŽβ€² β†’ 𝑆 𝑗 [πœ‹β€²]  πœŽβ€². 16 This gives rise to a map 𝑖 [𝜎] →𝑀 𝑆𝑖 [πœ‹]  πœŽβ€² β†’πœƒ 𝑆 𝑗 [πœ‹β€²]  πœŽβ€² 𝑀→ [πœ‹β€²]  𝑗 [𝜎] βˆ’1 πœƒ β€² : [πœ‹] Since this is a bΔ³ection, to show (2.1) it suffices to prove that πœƒ β€² is cSt-preserving. So take [𝜏] ∈ [πœ‹] 𝑖 [𝜎] and [πœβ€²] = πœƒβ€² [𝜏]. Then 𝑀 [πœβ€²] = πœƒ β—¦ 𝑀 [𝜏]. Since πœƒ is St preserving, we have St 𝑀 [πœβ€²] = St 𝑀 [𝜏]. But then hypothesis (a) implies that cSt[𝜏] = cSt[πœβ€²] which is what we wished to prove. 2.2 Applications The hypotheses in the Lifting Lemma may seem strange at first glance. But they can be quite easy to verify, making it a useful tool. We will see four instances of this by proving Theorem 1.2.2 using its aid. Theorem 2.2.1. The statistic cDes is cyclic shuffle compatible. Proof. We will verify the hypotheses of Lemma 2.1.3 using St = Des. For (a), suppose that #𝜏 = #πœβ€² = 𝑛 and Des(𝑀 [𝜏]) = Des(𝑀 [πœβ€²]). (2.2) Let us assume that 𝜏, πœβ€² were chosen from their cyclic equivalence class so that 𝜏1 = max 𝜏 and similarly for πœβ€². Then 𝑀 [𝜏] = 𝜏2 𝜏3 . . . πœπ‘› . And by the choice of 𝜏1 we see that Des 𝜏 = {1} ⊎ (Des 𝑀 [𝜏] + 1). (2.3) Since the same statement holds with πœβ€² in place of 𝜏 and (2.2) holds, we have Des 𝜏 = Des πœβ€². But Des 𝜏 is one set in the multiset cDes[𝜏], and the others are gotten by adding each 𝑖 ∈ [𝑛] to all elements of Des 𝜏 modulo 𝑛. The same being true of cDes[πœβ€²] shows that cDes[𝜏] = cDes[πœβ€²] as desired. For (b), we are given [πœ‹], [πœ‹β€²] ∈ 𝐢 [π‘š] with cDes[πœ‹] = cDes[πœ‹β€²] and must construct the necessary bΔ³ection. From this assumption, we can choose πœ‹ and πœ‹β€² such that cDes πœ‹ = cDes πœ‹β€² = 𝐴. (2.4) 17 for some set 𝐴. Define 𝑓 : [π‘š] β†’ [π‘š] by 𝑓 (πœ‹ π‘˜ ) = πœ‹β€²π‘˜ for all π‘˜ ∈ [π‘š]. Let 𝑖 = πœ‹ π‘˜ and 𝑗 = πœ‹β€²π‘˜ . To show that Des(𝑆𝑖 [πœ‹]) = Des(𝑆 𝑗 [πœ‹β€²]) there are two cases depending on whether π‘˜ βˆ’ 1 ∈ 𝐴 or not, where π‘˜ βˆ’ 1 is taken modulo π‘š. If π‘˜ βˆ’ 1 βˆ‰ 𝐴 then πœ‹ π‘˜ , πœ‹β€²π‘˜ are not the second elements in cyclic descents of their respective permutations. From this and equation (2.4) it follows that Des(𝑆𝑖 [πœ‹]) = 𝐴 βˆ’ π‘˜ + 1 (mod π‘š) = Des(𝑆 𝑗 [πœ‹β€²]). If π‘˜ βˆ’ 1 ∈ 𝐴 then the same equalities hold with 𝐴 replaced by 𝐴′ which is 𝐴 with π‘˜ βˆ’ 1 removed. The completes the proof of (b) and of the theorem. Theorem 2.2.2. The statistic cdes is cyclic shuffle compatible. Proof. We proceed as in the previous proof with St = des. For (a) we assume des(𝑀 [𝜏]) = des(𝑀 [πœβ€²]). But from equation (2.3) we see that des 𝜏 = des(𝑀 [𝜏]) βˆ’ 1 and the same is true for πœβ€². Combining this with our initial assumption gives des 𝜏 = des πœβ€². But 𝜏, πœβ€² begin with their largest element so that cDes[𝜏] = des 𝜏 = des πœβ€² = cDes[πœβ€²] which is what we wished to show. To prove (b), we are given cdes[πœ‹] = cdes[πœ‹β€²]. As in the preceding paragraph, choose πœ‹, πœ‹β€² to begin with their largest elements so that cdes[πœ‹] = des πœ‹ and similarly for πœ‹β€². Since des πœ‹ = des πœ‹β€² there is a bΔ³ection πœƒ : Des πœ‹ β†’ Des πœ‹β€². Extend this map to πœƒ : [π‘š] β†’ [π‘š] by using any bΔ³ection between the complements of Des πœ‹ and Des πœ‹β€². The proof that πœƒ has the desired property is now similar to that for Des and so is left to the reader. Theorem 2.2.3. The statistic cPk is cyclic shuffle compatible. Proof. This proof parallels the one for cDes, so we will only mention the highlights. For (a) one sees that Pk 𝜏 = Pk 𝑀 [𝜏] + 1 since 𝜏1 = max 𝜏 is not a peak in 𝜏 and is removed in 𝑀 [𝜏]. But this still implies that Pk 𝜏 = Pk πœβ€² and the rest of this part of the demonstration goes through. 18 For (b), the map πœƒ is constructed in exactly the same way using 𝐴 = cPk πœ‹ = cPk πœ‹β€². The only difference with the remaining part of the proof is that there are two subcases when π‘˜ βˆ’ 1 βˆ‰ 𝐴 depending on whether π‘˜ βˆ’ 2 ∈ 𝐴 or not. If π‘˜ βˆ’ 2 ∈ 𝐴 then one loses the peak which was at πœ‹ π‘˜βˆ’2 in 𝑆𝑖 [πœ‹]. On the other hand, the peak set stays the same modulo rotation if π‘˜ βˆ’ 2 βˆ‰ 𝐴. But since the analogous statements hold for πœ‹β€², the manipulations in these subcases are as before. The proof of the next result is based on the proof of Theorem 2.2.3 in much the same way that the demonstrations of Theorems 2.2.1 and 2.2.2 are related. So the details are left to the reader. Theorem 2.2.4. The statistic cpk is cyclic shuffle compatible. Lest it appear that cyclic shuffle compatibility follows exactly the same lines as the linear case, let us point out a place where they differ. A birun of πœ‹ is a maximal monotone factor (subsequence of consecutive elements). Let bru πœ‹ be the number of biruns of πœ‹. For example, bru 125346 = 3 because of the biruns 125, 53, and 346. It is easy to see [12] that the birun statistic is not linearly shuffle compatible. A cyclic birun of [πœ‹] is defined in the obvious manner and denoted cbru[πœ‹]. Returning to our example, cbru[125346] = 4 because of the biruns above and 61. Theorem 2.2.5. The statistic cbru is cyclic shuffle compatible. Proof. Clearly cyclic biruns always begin at a cyclic peak and end at a cyclic valley, or vice-versa. So cbru[πœ‹] = 2 cpk[πœ‹] and the result follows from Theorem 2.2.4. 2.3 Remarks and an open question 2.3.0.1 Cyclic pattern avoidance and statistics We say that [𝜎] ∈ 𝐢 [𝑛] contains the pattern [πœ‹] ∈ 𝐢 [π‘š] if there is some subsequence [πœŽβ€²] of [𝜎] such that std[πœŽβ€²] = [πœ‹]. Otherwise [𝜎] avoids [πœ‹]. For any set [Ξ ] of cyclic permutations we let Av𝑛 [Ξ ] = {[𝜎] ∈ 𝐢 [𝑛] | [𝜎] avoids [πœ‹] for all [πœ‹] ∈ [Ξ ]}. Callan in [4] calculated # Av𝑛 [Ξ ] when [Ξ ] consists of a single element of 𝐢 [4]. Gray, Lanning, and Wang then contributed work on cyclic packing of patterns [13] and patterns in colored cyclic 19 permutations [14]. Most recently, Domagalski, Liang, Minnich, Sagan, Schmidt, and Sietsema determined # Av𝑛 [Ξ ] for all [Ξ ] βŠ† 𝐢 [4] [8]. They also calculated the generating function βˆ‘οΈ 𝐷 𝑛 ([Ξ ]; π‘ž) = π‘ž cdes[𝜎] . [𝜎]∈Av𝑛 [Ξ ] for the same sets of patterns. 2.3.1 Cyclic maj Recall that the major index of πœ‹ is βˆ‘οΈ maj πœ‹ = 𝑖. π‘–βˆˆDes πœ‹ Stanley’s theory of 𝑃-partitions [24] shows that if #πœ‹ = π‘š and #𝜎 = 𝑛 then   maj πœ‹+maj 𝜎 π‘š + 𝑛 βˆ‘οΈ maj 𝜏 π‘ž =π‘ž πœβˆˆπœ‹ 𝜎 π‘š π‘ž where the last factor is a π‘ž binomial coefficient. Note that this is a π‘ž-analogue of the fact that  #(πœ‹ 𝜎) = π‘š+𝑛  π‘š . It is easy to see that    π‘š+π‘›βˆ’2 #([πœ‹] [𝜎]) = (π‘š + 𝑛 βˆ’ 1) . (2.5) π‘šβˆ’1 Indeed, write each [𝜏] in the shuffle so that it starts with πœ‹1 . Then there are π‘š + 𝑛 βˆ’ 1 more slots to be filled and π‘š βˆ’ 1 of them must be for the elements πœ‹2 πœ‹3 . . . πœ‹π‘š in that order. The remaining slots  can be filled with any of the 𝑛 rotations of 𝜎 for a total of 𝑛 π‘š+π‘›βˆ’1 π‘šβˆ’1 choices. This is equivalent to the formula above. In [1] the following question was raised. Question 2.3.1. Is there a cyclic analogue of maj which has nice properties such as giving a π‘ž-analogue of equation (2.5)? One possible analogue was given by Ji and Zhang in [16] where they defined cyclic maj of [πœ‹] to be maj(πœ‹β€²) where πœ‹β€² is the representative of [πœ‹] starting with the largest element in the cyclic permutation. However, Liang, Sagan, and Zhuang noted in [17] that this analogue was not shuffle compatible. They proposed a second possibility, which was a multiset containing the sums of cDes for each rotation of [πœ‹], but this also failed to be shuffle compatible and so the search for a cyclic maj remains an open pursuit in combinatorics. 20 CHAPTER 3 PINNACLE SETS This chapter will be structured as follows. First, we will state a result originally proven by Davis et al. for which we were able to find a simpler proof. Next, defining 𝑝 𝑛 (𝑃) to be the number of permutations in 𝔖𝑛 with pinnacle set 𝑃, we give a formula to directly count 𝑝 𝑛 (𝑃) using the principle of inclusion and exclusion which runs in exponential time in the size of 𝑛. Next, we will give a combinatorial proof for a weighted sum of the numbers 𝑝 𝑛 (𝑃) originally proven by Fang in [11] using more algebraic methods. Following this, we give a recursion for counting the number of admissible orderings, which are orderings of the elements of some set 𝑃 that can appear in a permutation with pinnacle set 𝑃. Finally, we finish by giving a recursive way of finding 𝑝 𝑛 (𝑃) that runs in time 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 4 ) where 𝑛 is the length of the permutations being counted and π‘˜ = #𝑃. 3.1 Counting the number of admissible pinnacle sets In their paper, Davis et al. used lattice paths to give a bΔ³ective proof for the following theorem where 𝑛 is fixed and βŒŠπ‘šβŒ‹ is the floor function. Theorem 3.1.1 ([5]). If A𝑛 = {𝑃 | 𝑃 = Pin πœ‹ for some πœ‹ ∈ 𝔖𝑛 } then   π‘›βˆ’1 #A𝑛 =  π‘›βˆ’1  . 2 We were able to come up with a second bΔ³ective proof of the result that is simpler in the sense that it does not use lattice paths. Our strategy will be as follows. First, we will introduce the set of interleaved permutations which are obviously counted by the desired binomial coefficient. Next, we will associate with each admissible pinnacle set 𝑃 a particular permutation πœ‹ such that Pin πœ‹ = 𝑃. This permutation will be called right canonical because its pinnacles will be as far right as possible. Finally, we will show that the set of interleaved permutations and the set of right canonical permutations are, in fact, the same. This will complete the proof of the theorem. 21 An interleaved permutation πœ‹ ∈ 𝔖𝑛 is one constructed in the following manner. Pick any   𝐴 βŠ† [2, 𝑛] with #𝐴 = π‘›βˆ’1 2 .  π‘›βˆ’1  I1 Fill the first 2 even positions of πœ‹ with the elements of 𝐴 in increasing order. I2 Fill the remaining positions of πœ‹ with the elements of 𝐴 = [𝑛] βˆ’ 𝐴 in increasing order. As an example, suppose 𝑛 = 9 and 𝐴 = {2, 3, 7, 9}. After step I1 we have πœ‹= 2 3 7 9 . Since 𝐴 = {1, 4, 5, 6, 8}, after I2 we have the full interleaved permutation πœ‹ = 1 2 4 3 5 7 6 9 8. (3.1) Let I𝑛 = {πœ‹ ∈ 𝔖𝑛 | πœ‹ is interleaved}. Clearly πœ‹ ∈ I𝑛 is completely determined by the choice of 𝐴. It follows immediately that   π‘›βˆ’1 #I𝑛 =  π‘›βˆ’1  . (3.2) 2 Now given an admissible pinnacle set 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } βŠ‚ [𝑛] we wish to construct a permutation πœ‹ ∈ 𝔖𝑛 with Pin πœ‹ = 𝑃. We use the following algorithm to construct the right canonical permutation πœ‹ from 𝑃. We first deal with the case where 𝑛 is odd. Let 𝑃 = [𝑛] βˆ’ 𝑃. C1 Place elements of 𝑃 in πœ‹ moving right to left, starting with the largest unused element of 𝑃 and then decreasing until an element less than the largest unused element of 𝑃 is placed. C2 Place the largest unused element of 𝑃 in the rightmost unused position. C3 Iterate C1 and C2 until all elements of 𝑃 and 𝑃 are placed. If 𝑛 is even, the only change to this procedure is that we fill both πœ‹π‘› and πœ‹π‘›βˆ’1 with elements of 𝑃 before considering whether to place an element of 𝑃. To illustrate, consider 𝑛 = 9 and 𝑃 = {4, 7, 9}. 22 So 𝑃 = {1, 2, 3, 5, 6, 8}. Here is the construction of πœ‹ where, at each stage, we note whether C1 or C2 is being used. step C1 C2 C1 C2 C1 C1 C2 C1 C1 πœ‹ 8 98 698 7698 57698 357698 4357698 24357698 124357698 So the right canonical permutation for 𝑃 = {4, 7, 9} is πœ‹ = 124357698. Note that Pin πœ‹ = 𝑃. Furthermore, this is the same permutation as obtained in (3.1). However, neither the sets 𝐴 nor 𝐴 equals 𝑃. Let C𝑛 = {πœ‹ ∈ 𝔖𝑛 | πœ‹ is right canonical}. We first need to show that C1–C3 is well defined in that every position of πœ‹ gets filled and that we always have Pin πœ‹ = 𝑃. Lemma 3.1.2. If 𝑃 βŠ‚ [𝑛] is an admissible set then C1–C3 produces a permutation πœ‹ with Pin πœ‹ = 𝑃. Thus #C𝑛 = #A𝑛 . Proof. Clearly the second sentence follows from the first. For the first sentence, we will present details for the case when 𝑛 is odd. If 𝑛 is even, then one can just place the largest element of 𝑃 in position 𝑛 and proceed as in the odd case. The following notation will be useful. Let 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 }, 𝑃 = { 𝑝¯1 < 𝑝¯2 < . . . < π‘Β―π‘›βˆ’π‘‘ }. We will also let 𝑃 𝑝 and 𝑃 𝑝 denote the elements of 𝑃 and of 𝑃, respectively, which have not been used during the placement of πœ‹π‘› , πœ‹π‘›βˆ’1 , . . . , πœ‹ 𝑝 . We will use reverse induction on the position 𝑝 being filled in πœ‹. When 𝑝 = 𝑛, we have 𝑃 β‰  βˆ… since 1, which is always a non-pinnacle, must be in 𝑃. So there is an element π‘Β―π‘›βˆ’π‘‘ to place in position 𝑛. Furthermore this element can not be a pinnacle since it is the last element of the permutation, which agrees with the fact that it is in 𝑃. 23 Suppose that πœ‹π‘› , πœ‹π‘›βˆ’1 , . . . , πœ‹ 𝑝+1 have been constructed. Suppose first that πœ‹ 𝑝+1 ∈ 𝑃. One subcase is if either 𝑃 𝑝 = βˆ…, or 𝑃 𝑝 β‰  βˆ… and πœ‹ 𝑝+1 > max 𝑃 𝑝 . We must show that 𝑃 𝑝 β‰  βˆ… so that we can let πœ‹ 𝑝 = max 𝑃 𝑝 . This is true when 𝑃 𝑝 = βˆ… since |𝑃 𝑝 ⊎ 𝑃 𝑝 | = 𝑝. If the second option holds then we have πœ‹ 𝑝+1 > max 𝑃 𝑝 . But there must be at least two elements of 𝑃 smaller than max 𝑃 𝑝 since 𝑃 is admissible and so there is some permutation making max 𝑃 𝑝 a pinnacle. Also, these elements must still be in 𝑃 𝑝 since elements of this set are placed in decreasing order right to left. Thus this set is nonempty as desired. Furthermore, πœ‹ 𝑝 is not a pinnacle since it is smaller than πœ‹ 𝑝+1 . Now consider the subcase when πœ‹ 𝑝+1 < max 𝑃 𝑝 . Then we let πœ‹ 𝑝 = max 𝑃 𝑝 which is well defined. But we must show that πœ‹ 𝑝 is a pinnacle. We know πœ‹ 𝑝 > πœ‹ 𝑝+1 . So there remains to check whether one can construct πœ‹ π‘βˆ’1 with πœ‹ π‘βˆ’1 < πœ‹ 𝑝 . For this, it suffices to show that 𝑃 π‘βˆ’1 β‰  βˆ… since then we will have πœ‹ π‘βˆ’1 = max 𝑃 π‘βˆ’1 < πœ‹ 𝑝+1 < πœ‹ 𝑝 . Note that this will also finish the induction step. We claim that if πœ‹ 𝑝 = 𝑝𝑖 and πœ‹ 𝑝+1 = 𝑝¯ 𝑗 then 𝑗 > 𝑖. It will then follow that 𝑝¯ π‘—βˆ’1 exists and can be used for πœ‹ π‘βˆ’1 . But by Theorem 1.3.2 we have 𝑝𝑖 > 𝑝¯𝑖+1 . Indeed, if 𝑝𝑖 < 𝑝¯𝑖+1 then at most the elements 𝑝 1 , . . . , π‘π‘–βˆ’1 , 𝑝¯1 , . . . , 𝑝¯𝑖 are less than 𝑝𝑖 so that 𝑝𝑖 ≀ 2𝑖, a contradiction. Also, elements of 𝑃 are placed in decreasing order with 𝑝𝑖 being placed as early as possible with a smaller element to its right. The desired bound on 𝑗 follows. We are now ready to give our proof of Theorem 3.1.1. Theorem 3.1.3. We have C𝑛 = I𝑛 . Thus   π‘›βˆ’1 #A𝑛 =  π‘›βˆ’1  . 2 Proof. The second statement follows directly from the first, Lemma 3.1.2, and equation (3.2). So we only need to prove that the two sets are the same. We will consider the case when 𝑛 is odd, as the even case is similar. We begin by showing that any right canonical permutation πœ‹ is interleaved. That is to say, the subword consisting of all even indices is an increasing sequence, and the subword consisting of all odd indices is an increasing sequence starting with 1. 24 In terms of the placement of 1, note that πœ‹1 is not a pinnacle. And since non-pinnacles are placed in decreasing order from right to left we must have πœ‹1 = 1. To finish this direction, it is enough to show that for any elements πœ‹π‘– and πœ‹π‘–+2 , we have that πœ‹π‘–+2 > πœ‹π‘– . Note that we are done immediately if πœ‹π‘– and πœ‹π‘–+2 are either both pinnacles or both non-pinnacles since the construction places them in decreasing order from right to left. If πœ‹π‘–+2 is a pinnacle and πœ‹π‘– is not, then by the pinnacle assumption πœ‹π‘–+2 > πœ‹π‘–+1 . And since non-pinnacles are placed in decreasing order right to left πœ‹π‘–+1 > πœ‹π‘– . Combining the two inequalities gives the desired result. Finally, suppose πœ‹π‘– is a pinnacle and πœ‹π‘–+2 is not. Then πœ‹π‘–+1 is not a pinnacle, being adjacent to πœ‹π‘– . And, by construction, πœ‹π‘–+1 must be the first available non-pinnacle right to left which is smaller than πœ‹π‘– . It follows that πœ‹π‘–+2 > πœ‹π‘– . For set containment the other way, let πœ‹ be an interleaved permutation. It suffices to show that if the elements of πœ‹ are placed right to left then they follow C1–C3. Consider πœ‹π‘– placed after πœ‹π‘–+1 with 1 < 𝑖 < 𝑛. The boundary cases when 𝑖 = 1 or 𝑛 are similar. If πœ‹π‘– < πœ‹π‘–+1 then πœ‹π‘– is a non-pinnacle and πœ‹π‘–+1 is either a non-pinnacle or a pinnacle. In the first case, the non-pinnacles are being placed in decreasing order as desired. In the second, the previously placed non-pinnacle is πœ‹π‘–+2 . So the same conclusion holds by the interleaving condition. Now consider the possibility πœ‹π‘– > πœ‹π‘–+1 . By the interleaving condition, πœ‹π‘–βˆ’1 < πœ‹π‘–+1 so πœ‹π‘– is a pinnacle. Either πœ‹π‘–+2 is a pinnacle or not, the latter possibility including the case that πœ‹π‘–+2 does not exist. If it is, then the interleaving condition shows that pinnacles are being placed in decreasing order. If πœ‹π‘–+2 is not a pinnacle, then this fact and the interleaving condition again imply πœ‹π‘– < πœ‹π‘–+2 < πœ‹π‘–+3 . It follows that πœ‹π‘– was placed after the first smaller non-pinnacle and, by the interleaving condition one last time, that any pinnacles to its right are larger. This completes the proof of the other containment. The above construct gives us a bΔ³ection. 𝐴 Theorem 3.1.4. Given a set 𝐴 and π‘˜ ∈ N we let π‘˜ be the set of all π‘˜-element subsets of 𝐴, we have the bΔ³ection   [2, 𝑛] πœ“ :  π‘›βˆ’1  β†’ A𝑛 2 25 2 1 6 7 8 9 0 1 2 3 4 5 6 7 8 2 5 -1 3 4 -2 Figure 3.1 The lattice path 𝐿 for 𝐴 = {2, 3, 7, 9} given by πœ“( 𝐴) = Pin πœ‹ where πœ‹ is the interleaving permutation corresponding to 𝐴. In [5], the authors proved Theorem 3.1.1 using a bΔ³ection   [2, 𝑛] πœ™ :  π‘›βˆ’1  β†’ A𝑛 2 defined as follows. An up-down lattice path 𝐿 starts at the origin and uses steps which are either up (π‘ˆ) or down (𝐷) parallel to the vectors [1, 1] and [1, βˆ’1], respectively. For more information about lattice paths, see the text of Sagan [23]. It will be convenient to index the steps of 𝐿 with [2,𝑛]  [2, 𝑛] and write 𝐿 = 𝑝 2 𝑝 3 . . . 𝑝 𝑛 . Associate with 𝐴 ∈ π‘›βˆ’1 the lattice path 𝐿 such that ⌊ 2 βŒ‹ ο£² 𝐷 if 𝑖 ∈ 𝐴, ο£±   𝑝𝑖 =  π‘ˆ if 𝑖 βˆ‰ 𝐴.  ο£³ To illustrate, if 𝑛 = 9 and 𝐴 = {2, 3, 7, 9} as in the example beginning this section then 𝐿 = π·π·π‘ˆπ‘ˆπ‘ˆπ·π‘ˆπ· as depicted in Figure 3.1 where each step is labeled by its index. We now define πœ™( 𝐴) = {𝑖 | in 𝐿 either 𝑝𝑖 = π‘ˆ strictly below the π‘₯-axis, or 𝑝𝑖 = 𝐷 weakly above the π‘₯-axis}. Continuing our example, πœ™({2, 3, 7, 9}) = {4, 7, 9} = πœ“({2, 3, 7, 9}). This is not an accident. 26 Proposition 3.1.5. We have πœ™ = πœ“. Proof. We will give the proof for 𝑛 odd as the even case is similar. Let 𝑙 = (𝑛 βˆ’ 1)/2. We need to show that πœ™( 𝐴) = πœ“( 𝐴) for all 𝐴 ∈ [2,𝑛]  𝑙 . Suppose 𝐴 = {π‘Ž 1 < π‘Ž 2 < . . . < π‘Ž 𝑙 } and 𝐴 = [𝑛] βˆ’ 𝐴 = {π‘Ž 1 < π‘Ž 2 < . . . < π‘Ž π‘›βˆ’π‘™ }. Let 𝐿 and πœ‹ be the lattice path and interleaved permutation, respectively, associated with 𝐴. So πœ“( 𝐴) = Pin πœ‹ and there will be two cases depending on whether a pinnacle of πœ‹ comes from 𝐴 or 𝐴 In the first case, suppose π‘Žπ‘– ∈ Pin πœ‹. Since πœ‹ is interleaved, this is equivalent to π‘Žπ‘– = πœ‹2𝑖 > πœ‹2𝑖+1 = π‘Žπ‘–+1 . Recall that π‘Žπ‘– indexes the 𝑖th 𝐷 step of 𝐿, and similarly for π‘Žπ‘–+1 and π‘ˆ steps. So the previous inequality is equivalent to step 𝑝 π‘Žπ‘– = 𝐷 being preceded by more up steps than down steps. And this is precisely the condition for π‘Žπ‘– to be the index of a down step weakly above the π‘₯-axis, which means it is in πœ™( 𝐴). Thus this case is complete. In a similar manner, one proves that π‘Žπ‘– ∈ Pin πœ‹ if and only if π‘Žπ‘– is the index of an up step strictly below the π‘₯-axis. This completes the second case and the proof. 3.2 Permutations with a given pinnacle set Given an admissible set 𝑃 of cardinally 𝑑, we may also want to count the number of permutations πœ‹ ∈ 𝔖𝑛 such that Pin πœ‹ = 𝑃; we denote this number by 𝑝 𝑛 (𝑃). There does not seem to be an expression for 𝑝 𝑛 (𝑃) analogous to the one in Theorem 1.3.1 for peak sets. In [5], Davis et al. found expressions for 𝑝 𝑛 (𝑃) when #𝑃 ≀ 2 as well as bounds for general 𝑃, and asked whether an exact formula could be given in the general case. Such an expression was given in [6] as a summation. In this section we will give another sum which is asymptotically more efficient. Since our sum will involve a significant amount of new notation, we will collect it here and then explain its relevance afterwards. Fix 𝑛 ∈ P. Suppose we have an admissible pinnacle set 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } for permutations in 𝔖𝑛 . We use the convention 𝑝 0 = 0 and 𝑝 𝑑+1 = 𝑛 + 1 and let 𝑛𝑖 = 𝑝𝑖+1 βˆ’ 𝑝𝑖 βˆ’ 1 27 for 0 ≀ 𝑖 ≀ 𝑑. Let 𝐷 = {1𝑙 , 1π‘Ÿ , 2𝑙 , 2π‘Ÿ , . . . , 𝑑𝑙 , π‘‘π‘Ÿ } and give the following total order to 𝐷’s elements 1𝑙 < 1π‘Ÿ < 2𝑙 < 2π‘Ÿ < . . . < 𝑑𝑙 < π‘‘π‘Ÿ . We call 𝑖 𝑙 and π‘–π‘Ÿ the elements of rank 𝑖 in 𝐷. If 𝐡 βŠ† 𝐷 then we will let 𝑏 = #𝐡 and π‘Ÿ 𝑗 = the rank of the 𝑗th smallest element of 𝐡 for 1 ≀ 𝑗 ≀ 𝑏. We also define 𝑏𝑖 = the number of elements in 𝐡 with rank at least 𝑖. Note that we always have 𝑏 1 = 𝑏 and 𝑏 𝑑+1 = 0 since 𝑑 is the largest rank. For example, if 𝑑 = 4, then 𝐷 = {1𝑙 , 1π‘Ÿ , 2𝑙 , 2π‘Ÿ , 3𝑙 , 3π‘Ÿ , 4𝑙 , 4π‘Ÿ } and one possible 𝐡 might be 𝐡 = {1𝑙 , 3𝑙 , 3π‘Ÿ , 4π‘Ÿ } which has π‘Ÿ 1 = 1, π‘Ÿ 2 = 3, π‘Ÿ 3 = 3, π‘Ÿ 4 = 4 and 𝑏 1 = 4, 𝑏 2 = 3, 𝑏 3 = 3, 𝑏 4 = 1, 𝑏 5 = 0. We can now state the first main result of this section. Theorem 3.2.1. Given 𝑛 ∈ P and admissible 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } we have π‘βˆ’1 ! 𝑑 ! βˆ‘οΈ Γ– Γ– 𝑝 𝑛 (𝑃) = 2π‘›βˆ’2π‘‘βˆ’1 (βˆ’1) 𝑏 (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 . π΅βŠ†π·: |𝐡|≀𝑑 𝑖=0 𝑖=0 To prove this, it will be convenient to convert the linear permutations we have been studying into cyclic ones in order to avoid considering boundary cases. Let [𝔖𝑛 ] = {[πœ‹] | πœ‹ ∈ 𝔖𝑛 }. We define the pinnacle set of [πœ‹] = [πœ‹1 πœ‹2 . . . πœ‹π‘› ] to be Pin[πœ‹] = {πœ‹π‘– | πœ‹π‘–βˆ’1 < πœ‹π‘– > πœ‹π‘–+1 where subscripts are taken modulo 𝑛}. 28 Continuing our example from the last paragraph Pin[1324] = {3, 4}. Note in particular that Pin[12] = {2} and, more generally, 𝑛 ∈ Pin[πœ‹] for any [πœ‹] ∈ [𝔖𝑛 ] where 𝑛 β‰₯ 2. Lemma 3.2.2. For 𝑛 ∈ P, there is a bΔ³ection between linear permutations in 𝔖𝑛 with pinnacle set 𝑃 and cyclic permutations in [𝔖𝑛+1 ] with pinnacle set 𝑃′ = 𝑃 βˆͺ {𝑛 + 1}. Proof. Given a linear πœ‹, append the element 𝑛 + 1 to the end of πœ‹ and take the corresponding equivalence class in 𝔖𝑛+1 to form an element of [𝔖𝑛+1 ]. The map is clearly invertible and does not destroy or create any pinnacles for elements in [𝑛]. Since 𝑛 + 1 β‰₯ 2, we know that 𝑛 + 1 will become a pinnacle. Therefore the map has the desired properties concerning the pinnacle set. Consider some admissible pinnacle set 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 }. Given the above lemma, we may count the number of permutations in 𝔖𝑛 with pinnacle set 𝑃 by counting the number of cyclic permutations [πœ‹] ∈ [𝔖𝑛+1 ] with pinnacle set 𝑃′ = 𝑃 βˆͺ {𝑛 + 1} where we let 𝑝 𝑑+1 = 𝑛 + 1. Therefore, much of what follows will be in regards to cyclic permutations with pinnacle set 𝑃′. A factor of a (cyclic) permutation is a subsequence of consecutive elements. We may attempt to construct a [πœ‹] with pinnacle set 𝑃′ by first putting the elements of 𝑃′ in some cyclic order, and then placing all elements in 𝑃′ = [𝑛 + 1] βˆ’ 𝑃′ into either decreasing factors starting with some 𝑝𝑖 , or into increasing factors ending with some 𝑝𝑖 . Such a [πœ‹] will then be completely determined by the increasing/decreasing factors that each element of 𝑃′ falls into, and we will call every such assignment a placement. Note that it is possible for multiple placements to result in the same permutation since each vale (an element of [πœ‹] smaller than the elements on either side) can be part of the factor on either side. For example, start with a desired pinnacle set {4, 5} and place non-pinnacles between these elements to form the cyclic permutation [πœ‹] = [14325]. Then [πœ‹] would be associated with a placement where the decreasing factor starting with 4 is 43 and the increasing factor ending with 5 is 25. But it would also be associated with a placement having these factors be 432 and 5, respectively. 29 It is also possible, depending on the placement, that [πœ‹] will not have pinnacle set 𝑃′ if no sufficiently small elements are placed between two pinnacles. In our example above, this could have happened if we had placed 1, 2 and 3 all in the increasing factor ending in 5, resulting in the cyclic permutation [41235] in which only 5 is a pinnacle. It is true, however, that any [πœ‹] so constructed will have a pinnacle set that is a subset of 𝑃′ since every non-pinnacle was placed so that its factor contains an 𝑝𝑖 which is the largest element. For our arguments, we will focus on counting placements and then convert them into permutations later. Fix a cyclic ordering of the pinnacle indices and write it as [𝜏] = [𝜏1 Β· Β· Β· πœπ‘‘+1 ] ∈ [𝔖𝑑+1 ]. An example is shown in Figure 3.2 where 𝜏 = [7612354]. Now given a placement consistent with this ordering, for every space between two adjacent elements in [𝜏] define the dale set of this placement to consist of all elements between the two corresponding pinnacles that are also smaller than both pinnacles. So in Figure 3.2 the dales are outlined by triangles with solid lines as sides. If 𝑝𝑖 is the smaller of the two pinnacles, then we say that the dale has rank 𝑖. Note that the rank is from the index of 𝑝𝑖 and not its actual value. We will further denote the rank as either 𝑖 𝑙 or π‘–π‘Ÿ depending on whether the dale is to the left, or right of the pinnacle 𝑝𝑖 . In Figure 3.2 the dale ranks are given along the π‘₯-axis. Define the dale rank set 𝐷 [𝜏] to be the set of the dale ranks of [𝜏]. And define the master dale rank set to be 𝐷 = {1𝑙 , 1π‘Ÿ , 2𝑙 , 2π‘Ÿ , . . . , 𝑑𝑙 , π‘‘π‘Ÿ } so that 𝐷 βŠ‡ 𝐷 [𝜏] for all [𝜏]. In Figure 3.2, we have that 𝐷 [𝜏] = {1𝑙 , 1π‘Ÿ , 2π‘Ÿ , 3π‘Ÿ , 41 , 4π‘Ÿ , 6𝑙 } while 𝐷 = {1𝑙 , 1π‘Ÿ , 2𝑙 , 2π‘Ÿ , . . . , 6𝑙 , 6π‘Ÿ }. Note that, by our definitions, there will be no dales in the case where 𝑑 = 0. Clearly 𝐷 [𝜏] will be a subset of 𝐷 consisting of exactly 𝑑 + 1 elements if 𝑑 > 0, and empty otherwise. We can derive further information about 𝐷 [𝜏] if we want, such as how it will always contain both 1𝑙 and 1π‘Ÿ if 𝑑 > 0, how it will never contain both 𝑑𝑙 and π‘‘π‘Ÿ if 𝑑 > 1, and how 𝐷 [𝜏] will never be able to have certain combinations of the higher ranked dales. These facts are not necessary for proving our formula, although further analysis of them might help to improve its efficiency. 30 𝑝7 𝑝7 𝑛6 elements 𝑝6 𝑛5 elements 𝑝5 𝑛4 elements 𝑝4 𝑛3 elements 𝑝3 𝑛2 elements 𝑝2 𝑛1 elements 𝑝1 𝑛0 elements 6𝑙 1𝑙 1π‘Ÿ 2π‘Ÿ 3π‘Ÿ 4𝑙 4π‘Ÿ Figure 3.2 Example of a pinnacle set ordering [𝜏] = [7612354] with corresponding dales Lemma 3.2.3. For 𝑛 ∈ P, a given placement will correspond to a permutation [πœ‹] ∈ [𝔖𝑛+1 ] with pinnacle set 𝑃′ if and only if every dale is non-empty. Proof. First, suppose 𝑑 = 0. In this case, the theorem is trivial since there are no dales. And every placement will automatically result in only one pinnacle, namely 𝑛 + 1, as long as 𝑛 > 0. Now suppose 𝑑 > 0. Clearly if any dale of rank 𝑖 (whether left or right) is empty, then the pinnacle 𝑝𝑖 will have no smaller elements between itself and the higher pinnacle next to it, which will force 𝑝𝑖 to not be a pinnacle. On the other hand, if all dales have at least one element, then the space between any two pinnacles will always contain an element smaller than both, and all elements of 𝑃′ will in fact be pinnacles. We can now enumerate all placements corresponding to a given cyclic ordering of the indices of the pinnacle set 𝑃′. Lemma 3.2.4. Given an admissible pinnacle set 𝑃′, fix an order [𝜏] of the pinnacle indices. The total number of placements with order [𝜏] that will result in a permutation with pinnacle set 𝑃′ is 31 given by βˆ‘οΈ Γ– 𝑑 𝑏 (βˆ’1) 2𝑛𝑖 (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 π΅βŠ‚π· [ 𝜏 ] 𝑖=0 where 𝑏, 𝑑, the 𝑏𝑖 , and the 𝑛𝑖 are defined above. Proof. We will use the Principle of Inclusion and Exclusion or PIE. We let our universal set be all possible placements with no restrictions. We then wish to exclude any placement where at least one dale is empty. Therefore, if 𝐡 is some subset of the dales, we must be able to count the number of placements where all dales in 𝐡 (and possibly others) are empty. First consider the case when 𝐡 = βˆ…. There are 2(𝑑 + 1) factors of which 2𝑖 only exist below 𝑝𝑖 . So each of the 𝑛𝑖 non-pinnacles between 𝑝𝑖 and 𝑝𝑖+1 may be placed in any of the 2(𝑑 + 1 βˆ’ 𝑖) factors that are long enough to extend above 𝑝𝑖 . As an example, in Figure 3.2.3 if we look between the horizontal boundary lines for the elements counted by 𝑛2 we see there are 10 = 2(6 + 1 βˆ’ 2) such factors represented by the diagonal lines (solid or dotted) which intersect the region. For non-empty 𝐡, each dale of rank at least 𝑖 + 1 that we require to be empty will result in a loss of two additional factors, and so there are only 2(𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) choices. Therefore, for a given 𝐡, the total number of placements guaranteeing the dales in 𝐡 are empty is Ö𝑑 2𝑛𝑖 (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 . 𝑖=0 To use the PIE, we must also attach the sign (βˆ’1) |𝐡| = (βˆ’1) 𝑏 to this term before summing. Therefore, given a fixed order [𝜏] of the pinnacle indices of 𝑃′, we have that the total number of placements that will result in a permutation with pinnacle set 𝑃′ is βˆ‘οΈ Γ– 𝑑 (βˆ’1) 𝑏 2𝑛𝑖 (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 . π΅βŠ†π· [ 𝜏 ] 𝑖=0 Finally, when 𝐡 = 𝐷 [𝜏] then 𝑏 1 = #𝐡 = 𝑑 + 1. So we can ignore this term because the product has a factor of 𝑑 + 1 βˆ’ 𝑏 1 = 0. The above formula must be summed over all possible [𝜏] to give a final count for the number of [πœ‹] with Pin[πœ‹] = 𝑃′. This results in computationally expensive double sum. Also, note that 32 in the above formula there may be multiple 𝐡 resulting in the same term. For example, {1𝑙 , 2π‘Ÿ , 5𝑙 } is not the same as {1π‘Ÿ , 2π‘Ÿ , 5𝑙 } even though both produce the same 𝑏𝑖 . We will take care of this redundancy when we optimize our formula below. To fix the double sum problem, note that each 𝐡 in Lemma 3.2.4 is a subset of the master dale rank set 𝐷. We will fix some subset 𝐡 βŠ† 𝐷 and count the number of orderings [𝜏] that will produce a 𝐷 [𝜏] which can have 𝐡 as a subset. This will allow us to just sum over all subsets 𝐡 βŠ† 𝐷 without having to keep track of [𝜏]. Furthermore, we only have to sum over the subsets 𝐡 of cardinality at most 𝑑 since requiring more than 𝑑 dales to be empty is impossible for an admissible pinnacle set. Lemma 3.2.5. Fix some 𝐡 βŠ† 𝐷 with |𝐡| ≀ 𝑑. The number of orderings [𝜏] that will produce a 𝐷 [𝜏] such that 𝐡 βŠ† 𝐷 [𝜏] is given by π‘βˆ’1 Γ– (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) 𝑖=0 where 𝑏, 𝑑, and the π‘Ÿπ‘– are defined as above. Proof. We will start by viewing all 𝑑 + 1 pinnacles as separate and then adjoin them in pairs in such a way so that the desired dales are formed. Here, β€œadjoining a pair of pinnacles" means requiring that they be adjacent in [𝜏]. We start with the dale of rank π‘Ÿ 𝑏 the largest rank in 𝐡. In that case, the only way to generate such a dale is to order π‘π‘Ÿ 𝑏 so that one of the 𝑑 + 1 βˆ’ π‘Ÿ 𝑏 higher pinnacles is directly to its left or right depending on whether the corresponding element of 𝐡 is a left or right rank, respectively. So select one such pinnacle and adjoin it to the appropriate side of π‘π‘Ÿ 𝑏 . Next we will examine the dale in 𝐡 with the next highest rank, π‘Ÿ π‘βˆ’1 . If π‘Ÿ π‘βˆ’1 is a smaller rank than π‘Ÿ 𝑏 , we may once again select a taller pinnacle to place next to π‘π‘Ÿ π‘βˆ’1 , on either the left or right as necessary, in order to produce the desired dale. This time however, although there are 𝑑 + 1 βˆ’ π‘Ÿ π‘βˆ’1 pinnacles higher than π‘π‘Ÿ π‘βˆ’1 , one of them is unavailable since we have already adjoined two of the higher-ranked pinnacles together. More specifically, because of adjoining a higher pinnacle with π‘π‘Ÿ 𝑏 , we know that one taller pinnacle cannot be joined to its left and another cannot be joined to its right. So no matter whether π‘Ÿ π‘βˆ’1 corresponded to a left or right dale, there is one less option. 33 Therefore, the number of ways to append a larger pinnacle is 𝑑 + 1 βˆ’ π‘Ÿ π‘βˆ’1 βˆ’ 1. On the other hand, if π‘Ÿ π‘βˆ’1 = π‘Ÿ 𝑏 then we need to adjoin a second pinnacle to π‘π‘Ÿ 𝑏 on the side opposite the one used when considering π‘Ÿ 𝑏 . Again, the pinnacle already adjoined to π‘π‘Ÿ 𝑏 removes one option so the number of choices is 𝑑 + 1 βˆ’ π‘Ÿ π‘βˆ’1 βˆ’ 1 as before. So in either case we have the same number of possibilities. Similar consideration show that, in general, each π‘Ÿ π‘βˆ’π‘– results in 𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– choices for adjoining pinnacles. Note that for this argument we are using the fact that 𝑏 ≀ 𝑑 since if 𝑏 = 𝑑 + 1 then the string of pinnacles would wrap into a circle before creating the final dale. Once all dales have been created by the above process, we only need to count the number of ways to join the resulting strings of pinnacles together. Since we have adjoined pinnacles together 𝑏 times, we have 𝑑 + 1 βˆ’ 𝑏 strings which we then must arrange in a circle. This can be done in (𝑑 + 1 βˆ’ 𝑏 βˆ’ 1)! = (𝑑 βˆ’ 𝑏)! ways. Therefore, Γ–π‘βˆ’1 (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) 𝑖=0 is the number of orderings [𝜏] that will allow for a given 𝐡 to be a subset of 𝐷 [𝜏] . We are now in a position to prove Theorem 3.2.1 which we restate here for ease of reference. Theorem 3.2.6. Given 𝑛 ∈ P and admissible 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } we have π‘βˆ’1 ! 𝑑 ! βˆ‘οΈ Γ– Γ– 𝑝 𝑛 (𝑃) = 2π‘›βˆ’2π‘‘βˆ’1 (βˆ’1) 𝑏 (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 . π΅βŠ†π·: |𝐡|≀𝑑 𝑖=0 𝑖=0 Proof. It is easy to verify the formula if 𝑑 = 0, so we assume 𝑑 > 0. From Lemma 3.2.3, the number of permutations πœ‹ ∈ 𝔖𝑛+1 with pinnacle set 𝑃 equals the number of cyclic permutations [πœ‹] ∈ [𝔖𝑛+1 ] with pinnacle set 𝑃′ = 𝑃 βˆͺ {𝑛 + 1}. So we will count the latter. From Lemma 3.2.4, the number of placements which correspond to a cyclic permutation with pinnacle set 𝑃′ is given by βˆ‘οΈ βˆ‘οΈ Ö𝑑 (βˆ’1) 𝑏 2𝑛𝑖 (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 [𝜏] π΅βŠ†π· [ 𝜏 ] 𝑖=0 where the outer sum is over all possible cyclic orderings [𝜏] of the index set of 𝑃′. We now wish to swap the summations so that the outer sum is over all 𝐡 βŠ† 𝐷 with |𝐡| ≀ 𝑑. We may restrict to 34 size at most 𝑑 since any larger 𝐡 will either consist of a combination of dales that cannot exist, or will require all 𝑑 + 1 dales to be empty which is impossible because of the assumption that 𝑑 > 0. In order to interchange the summations we must multiply the term corresponding to each 𝐡 by the number of distinct permutations [𝜏] that could have generated it. This was counted in Lemma 3.2.5, and so we get the formula π‘βˆ’1 ! 𝑑 ! βˆ‘οΈ Γ– Γ– 𝑏 𝑛𝑖 𝑛𝑖 (βˆ’1) (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) 2 (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) π΅βŠ‚π·: |𝐡|≀𝑑 𝑖=0 𝑖=0 for the number of placements. Now we seek to turn the placements into permutations. Since all dales are guaranteed to be non-empty, we have that every permutation corresponding to one of these placements will have 𝑑 + 1 non-pinnacle elements that are part of both a decreasing factor and an increasing factor. This means that every such corresponding [πœ‹] has been counted by 2𝑑+1 placements. Dividing by this, and also pulling some common factors of two out from the second product, we have 𝑑 π‘βˆ’1 ! 𝑑 ! Γ– βˆ‘οΈ Γ– Γ– 𝑝 𝑛 (𝑃) = 2βˆ’π‘‘βˆ’1 2𝑛 𝑖 (βˆ’1) 𝑏 (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 𝑖=0 π΅βŠ†π·: |𝐡|≀𝑑 𝑖=0 𝑖=0 π‘βˆ’1 ! 𝑑 ! βˆ‘οΈ Γ– Γ– = 2π‘›βˆ’2π‘‘βˆ’1 (βˆ’1) 𝑏 (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 π΅βŠ†π·: |𝐡|≀𝑑 𝑖=0 𝑖=0 where this is the formula we set out to prove. In [5], explicit formulas were given for 𝑝 𝑛 (𝑃) when |𝑃| ≀ 3. These expressions follow easily from the previous result. Corollary 3.2.7. We have the following values for 𝑝 𝑛 (𝑃). (1) If 𝑃 = βˆ… then 𝑝 𝑛 (𝑃) = 2π‘›βˆ’1 . (2) If 𝑃 = {𝑙} where 3 ≀ 𝑙 ≀ 𝑛 then 𝑝 𝑛 (𝑃) = 2π‘›βˆ’2 (2π‘™βˆ’2 βˆ’ 1). 35 (3) If 𝑆 = {𝑙, π‘š} where 𝑙 β‰₯ 3, π‘š β‰₯ 5, and 𝑙 < π‘š ≀ 𝑛, then 𝑝 𝑛 (𝑃) = 2𝑛+π‘šβˆ’π‘™βˆ’5 (3π‘™βˆ’1 βˆ’ 2𝑙 + 1) βˆ’ 2π‘›βˆ’3 (2π‘™βˆ’2 βˆ’ 1). Proof. In each of the results we apply Theorem 3.2.6. (1) When 𝑑 = 0, the first product in Theorem 3.2.6 is always empty and the second always equals one. Therefore, everything reduces immediately to 𝑝 𝑛 (𝑃) = 2π‘›βˆ’1 , as desired. (2) When 𝑑 = 1 we have 𝑛0 = 𝑙 βˆ’ 1, 𝑛1 = 𝑛 βˆ’ 𝑙. Therefore, we have the following possibilities for 𝐡, and the corresponding terms in the summation β€’ 𝐡 = βˆ… : 2π‘™βˆ’1 β€’ 𝐡 = {1𝑙 } or {1π‘Ÿ }: βˆ’1 which when substituted into the formula gives 𝑝 𝑛 (𝑃) = 2π‘›βˆ’3 (2π‘™βˆ’1 βˆ’ 2) = 2π‘›βˆ’2 (2π‘™βˆ’2 βˆ’ 1). (3) When 𝑑 = 2 we have 𝑛0 = 𝑙 βˆ’ 1, 𝑛1 = π‘š βˆ’ 𝑙 βˆ’ 1, and 𝑛2 = 𝑛 βˆ’ π‘š. Additionally, the first inner product will always zero out if 2π‘Ÿ , 2𝑙 are both in 𝐡. Therefore, we have the following possibilities for 𝐡, and the corresponding terms in the summation: β€’ 𝐡 = βˆ… : (2)3π‘™βˆ’1 2π‘šβˆ’π‘™βˆ’1 β€’ 𝐡 = {1𝑙 } or {1π‘Ÿ }: (βˆ’2)2π‘™βˆ’1 2π‘šβˆ’π‘™βˆ’1 β€’ 𝐡 = {2𝑙 } or {2π‘Ÿ }: (βˆ’1)2π‘™βˆ’1 β€’ 𝐡 = {1𝑙 , 1π‘Ÿ }: 2 β€’ 𝐡 = {1𝑙 , 2π‘Ÿ } or {1π‘Ÿ , 2π‘Ÿ } or {1𝑙 , 2𝑙 } or {1π‘Ÿ , 2𝑙 }: 1. When we substitute all these into the formula, we get 𝑝 𝑛 (𝑃) = 2π‘›βˆ’5 [(2)3π‘™βˆ’1 2π‘šβˆ’π‘™βˆ’1 βˆ’ (4)2π‘™βˆ’1 2π‘šβˆ’π‘™βˆ’1 βˆ’ (2)2π‘™βˆ’1 + (2)2π‘šβˆ’π‘™βˆ’1 + 4] = 2π‘›βˆ’5 [(2)3π‘™βˆ’1 2π‘šβˆ’π‘™βˆ’1 βˆ’ (4)2π‘™βˆ’1 2π‘šβˆ’π‘™βˆ’1 + (2)2π‘šβˆ’π‘™βˆ’1 ] βˆ’ 2π‘›βˆ’5 [(2)2π‘™βˆ’1 βˆ’ 4] = 2𝑛+π‘šβˆ’π‘™βˆ’5 (3π‘™βˆ’1 βˆ’ 2𝑙 + 1) βˆ’ 2π‘›βˆ’3 (2π‘™βˆ’2 βˆ’ 1) 36 as desired. We can make Theorem 3.2.6 more efficient by summing over certain weak compositions rather than subsets. A weak composition of 𝑛 ∈ N is a sequence 𝛼 = [𝛼1 , 𝛼2 , . . . , 𝛼 π‘˜ ] of nonnegative Í Í integers called parts such that 𝑖 𝛼𝑖 = 𝑛. In this case we write 𝛼 |= 𝑛 or |𝛼| = 𝑛 where |𝛼| = 𝑖 𝛼𝑖 . To 𝐡 βŠ† 𝐷 we associate the composition 𝛼 = [𝛼1 , 𝛼2 , . . . , 𝛼𝑑 ] where 𝛼𝑖 is the number of dales in 𝐡 of rank 𝑖. To illustrate, for the example in Figure 3.2 the corresponding composition is 𝛼 = [2, 1, 1, 2, 0, 1]. Note that all the necessary parameters for 𝐷 can be read off of 𝛼. In particular π‘Ÿ 𝑗 = min{𝑖 | 𝛼1 + 𝛼2 + Β· Β· Β· + 𝛼𝑖 β‰₯ 𝑗 }, and 𝑏𝑖 = 𝛼𝑖 + 𝛼𝑖+1 + Β· Β· Β· + 𝛼𝑑 . Note that 𝑏 = 𝑏 1 = |𝛼|. Thus we will be able to sum over the following set 𝐢 (𝑑) = {𝛼 = [𝛼1 , 𝛼2 , . . . , 𝛼𝑑 ] | 𝛼𝑖 ∈ [0, 2] for all 𝑖 and |𝛼| ≀ 𝑑}. We must find how many 𝐡 correspond to a given 𝛼. If 𝛼𝑖 = 0 then 𝐡 contains no dales of rank 𝑖. If 𝛼𝑖 = 2 then 𝐡 contains both dales of rank 𝑖. So the only choice comes if 𝛼𝑖 = 1 in which case 𝐡 could contain either 𝑖 𝑙 or π‘–π‘Ÿ . Letting π‘œ = the number of 𝛼𝑖 = 1 we see that the number of 𝐡 represented by 𝛼 is 2π‘œ . Thus we have proved the following result. Corollary 3.2.8. Given 𝑛 ∈ P and admissible 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } we have π‘βˆ’1 ! 𝑑 ! βˆ‘οΈ Γ– Γ– 𝑝 𝑛 (𝑃) = 2π‘›βˆ’2π‘‘βˆ’1 (βˆ’1) 𝑏 2π‘œ (𝑑 βˆ’ 𝑏)! (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘βˆ’π‘– ) (𝑑 + 1 βˆ’ 𝑖 βˆ’ 𝑏𝑖+1 ) 𝑛𝑖 . π›ΌβˆˆπΆ (𝑑) 𝑖=0 𝑖=0 37 𝑃 DLHHIN DLMSSS {3, 5, 7, 9, 11, 13, 15, 17, 19, 21} 9.2 Γ— 10βˆ’5 0.72 {3, 6, 9, 12, 15, 18, 21, 24, 27, 30} 0.11 0.73 {3, 7, 11, 15, 19, 23, 27, 31, 35, 39} 9.5 0.73 {3, 8, 13, 18, 23, 28, 33, 38, 43, 48} 210 0.78 Table 3.1 Run times in seconds compared when most 𝑛𝑖 are equal In order to compare this formula to the one in [6], we need to introduce some notation. The vale set of a permutation πœ‹ is Val πœ‹ = {πœ‹π‘– | πœ‹π‘–βˆ’1 > πœ‹π‘– < πœ‹π‘–+1 }. Call a pair (𝑃, 𝑇) 𝑛-admissible if there is a permutation πœ‹ ∈ 𝔖𝑛 with Pin πœ‹ = 𝑃 and Val πœ‹ = 𝑇. Define V𝑛 (𝑃) = {𝑇 | (𝑃, 𝑇) is 𝑛-admissible}. Theorem 3.2.9 ([6]). Given 𝑛 ∈ P and admissible 𝑃 with #𝑃 = 𝑑 we have βˆ‘οΈ Γ–  𝑁 𝑃𝑇 ( 𝑝)  Γ– π‘›βˆ’2π‘‘βˆ’1 𝑝 𝑛 (𝑃) = 2 𝑁 𝑃𝑇 (𝑑) 2 𝑇 ∈V𝑛 (𝑃) π‘βˆˆπ‘ƒ π‘‘βˆˆ[𝑛]βˆ’(π‘ƒβŠŽπ‘‡) where 𝑃𝑖 = {𝑝 ∈ 𝑃 | 𝑝 < 𝑖}, 𝑇𝑖 = {𝑑 ∈ 𝑇 | 𝑑 < 𝑖}, and 𝑁 𝑃𝑇 (𝑖) = #𝑇𝑖 βˆ’ #𝑃𝑖 . In order to estimate the number of terms in this sum, we need a formula for #V𝑛 (𝑃). Let 𝐾 (𝑑) = {𝛼 = [𝛼1 , 𝛼2 , . . . , 𝛼𝑑 ] |= 𝑑 | 𝛼1 + 𝛼2 + Β· Β· Β· + 𝛼 π‘˜ β‰₯ π‘˜ for all π‘˜ ∈ [𝑑]}. Theorem 3.2.10 ([6]). Given 𝑛 ∈ P and admissible 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 𝑑 } we have βˆ‘οΈ 𝑛0 βˆ’ 1 Γ– 𝑑   π‘›π‘–βˆ’1 #V𝑛 (𝑃) = . 𝛼1 𝛼𝑖 π›ΌβˆˆπΎ (𝑑) 𝑖=2 We can now compare the number of terms in the sums of Corollary 3.2.8 and Theorem 3.2.9. In the former we have 𝑐(𝑑) := #𝐢 (𝑑) ≀ 3𝑑 terms, where the inequality comes from the fact that every 𝛼𝑖 ∈ {0, 1, 2}. In the latter, we have 𝑣 𝑛 (𝑃) := #V𝑛 (𝑃) terms which depends on 𝑛 and 𝑃, and 38 not just 𝑑 as seen in Theorem 3.2.10. If 𝑛1 ≀ 4 and 𝑛𝑖 ≀ 3 for 𝑖 β‰₯ 2 then each of the binomial coefficients in the sum is a most 3 and so 𝑣 𝑛 (𝑃) could be significantly smaller than 𝑐(𝑑). But if even one of the 𝑛𝑖 is large, then the inequality will be reversed. For example, suppose 𝑛1 β‰₯ 2𝑑 + 1 and take 𝛼 = [𝑑, 0, 0, . . . , 0] ∈ 𝐾 (𝑑). Then, by Stirling’s approximation,   2𝑑 4𝑑 𝑣 𝑛 (𝑃) β‰₯ ∼√ 𝑑 πœ‹π‘‘ which will eventually be greater than 3𝑑 . So, for fixed 𝑑, there are only finitely many 𝑛 such that 𝑣 𝑛 (𝑃) ≀ 𝑐(𝑑). Thus, in most cases, Corollary 3.2.8 will be more efficient. We should mention that Diaz-Lopez, Insko, and Nilsen [6] have come up with a refinement of the ideas in [6] which permits the product of binomial coefficients in Theorem 3.2.10 to be replaced by 2𝑑 . The observations of the previous paragraph are borne out by actual computer computations. In Tables 3.1 and 3.2 we show the results of computing 𝑝 1000 (𝑃) for various sets 𝑃 (first column) with constant 𝑑 by the algorithm in [6] (second column) and our algorithm (third column). The run times are in seconds and are the average over 10 trials for each set using a 15-inch 2017 MacBook Pro with a 3.1 GHz Quad-Core Intel Core i7 processor. In Table 3.1 the 𝑛𝑖 for 0 < 𝑖 < 𝑑 are constant in each set, but allowed to increase as one goes down the table. As expected, the algorithm using vales starts out orders of magnitude faster than the one using dales but quickly becomes orders of magnitude slower, with the latter’s times being virtually constant. Similar behaviour is shown in the two parts of Table 3.2 which keep all of the 𝑛𝑖 for 0 ≀ 𝑖 < 𝑑 constant except for one which is allowed to grow. Note the difference in growth rate of the vale algorithm between increasing 𝑛4 (upper chart) and 𝑛0 (lower chart). Another advantage to this approach is that it can be modified to count #O (𝑃), the number of admissible orderings of an admissible pinnacle set 𝑃. First, if we fix 𝑛 > 0 we have that Lemma 3.2.2 will again allow us to reduce to the case of cyclic orderings of the pinnacle set 𝑃′ for permu- tations in 𝔖𝑛+1 . We now prove the following intermediate result. 39 Increase 𝑛4 with other 𝑛𝑖 constant 𝑃 DLHHIN DLMSSS {3, 5, 7, 9, 11} 2.9 Γ— 10βˆ’5 0.0014 {3, 5, 7, 9, 21} 7.1 Γ— 10βˆ’5 0.0014 {3, 5, 7, 9, 31} 0.00012 0.0015 {3, 5, 7, 9, 41} 0.00017 0.0015 Increase 𝑛0 with other 𝑛𝑖 constant 𝑃 DLHHIN DLMSSS {3, 5, 7, 9, 11} 2.9 Γ— 10βˆ’5 0.0014 {13, 15, 17, 19, 21} 0.012 0.0015 {23, 25, 27, 29, 31} 0.26 0.0015 {33, 35, 37, 39, 41} 1.8 0.0015 Table 3.2 Run times in seconds compared when most 𝑛𝑖 are constant Lemma 3.2.11. Consider a cyclic ordering [𝜏] with dale set 𝐷 [𝜏] and corresponding π‘Ÿ 𝑗 . The ordering is admissible if and only if 𝑗 ≀ 𝑛0 + 𝑛1 + Β· Β· Β· + π‘›π‘Ÿ 𝑗 βˆ’1 for all 𝑗 ∈ [𝑑 + 1]. Proof. Note that, by definition of the 𝑛𝑖 and π‘Ÿπ‘– , the right hand side of the inequality is simply the number of non-pinnacles small enough to be placed in any of the dales having rank at least π‘Ÿ 𝑗 . So if for any 𝑗 we have 𝑗 > 𝑛0 + 𝑛1 + Β· Β· Β· π‘›π‘Ÿ 𝑗 βˆ’1 , then there will be at least 𝑗 + 1 dales having rank at most π‘Ÿ 𝑗 . This means there would not be enough small non-pinnacle elements to fill them all. Therefore, any such ordering is not admissible. On the other hand, if we have that 𝑗 ≀ 𝑛0 + 𝑛1 + Β· Β· Β· π‘›π‘Ÿ 𝑗 βˆ’1 for all 𝑗, then we may always fill all the dales by placing the smallest non-pinnacle in the lowest ranked dale, and proceeding upwards. The inequalities guarantee that we will always have enough non-pinnacles to do this at every step, and so we are done. 40 Since the problem is trivial if 𝑑 = 0, so we may also assume that 𝑑 > 0. We also define for the master dale rank set 𝐷 𝐷 β€² = 𝐷 βˆ’ {1𝑙 , 1π‘Ÿ } and for any subset 𝐡 ο£±  ο£²1 if 𝑗 ≀ 𝑛0 + 𝑛1 + Β· Β· Β· + π‘›π‘Ÿ 𝑗 βˆ’1 for all 𝑗 ∈ [𝑏],    𝛿𝐡 =  0 otherwise.   ο£³ With this notation, we can count admissible orderings. Theorem 3.2.12. If 𝑑 ∈ P and 𝑃 is admissible then βˆ‘οΈ π‘‘βˆ’2 Γ– #O (𝑃) = 𝛿 𝐡βˆͺ{1𝑙 ,1π‘Ÿ } (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘‘βˆ’1βˆ’π‘– ) . π΅βŠ†π· β€² : |𝐡|=π‘‘βˆ’1 𝑖=0 Proof. We first wish to sum over all possible orderings, partitioned by their dales. Since every dale set for 𝑑 > 0 is guaranteed to have 𝑑 + 1 elements and contain {1𝑙 , 1π‘Ÿ }, we may index the dales by taking 𝐡 βŠ† 𝐷 β€² where |𝐡| = 𝑑 βˆ’ 1. We then consider the following summation βˆ‘οΈ Γ–π‘‘βˆ’2 (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘‘βˆ’1βˆ’π‘– ) . π΅βŠ†π· β€² : |𝐡|=π‘‘βˆ’1 𝑖=0 Clearly this sums over every possible dale set once, and the expression inside comes from Lemma 3.2.5, which counts the number of cyclic orderings of 𝑃′ which have dales containing those in 𝐡. However, due to the restrictions placed on the size of 𝐡 and the comments above, this expression will count those cyclic orderings of 𝑃′ which have dales equal to 𝐡 βˆͺ {1𝑙 , 1π‘Ÿ } instead of just a subset. Therefore, no ordering can be counted twice by two different 𝐡’s and so every ordering is accounted for exactly once in the above summation, making the total 𝑑!. Finally, using Lemma 3.2.11, we may exclude from this sum precisely those orderings which are not admissible by writing it as βˆ‘οΈ π‘‘βˆ’2 Γ– 𝛿 𝐡βˆͺ{1𝑙 ,1π‘Ÿ } (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘‘βˆ’1βˆ’π‘– ) . π΅βŠ†π· β€² : |𝐡|=π‘‘βˆ’1 𝑖=0 This completes the proof. 41 We may also rewrite our result in terms of compositions for a faster summation. Lemma 3.2.11 still holds as the π‘Ÿ 𝑗 are the same whether or not the dales sets are represented as compositions, but now we will need make some new definitions. Let 𝐢 β€² (𝑑) = {𝛼 = [𝛼1 , 𝛼2 , . . . , π›Όπ‘‘βˆ’1 ] |= [𝑑 βˆ’ 1] | 𝛼𝑖 ∈ [0, 2] for all 𝑖}, and if 𝛼 |= 𝑏 ο£±  ο£²1 if 𝑗 ≀ 𝑛0 + 𝑛1 + Β· Β· Β· + π‘›π‘Ÿ 𝑗 βˆ’1 for all 𝑗 ∈ [𝑏],    𝛿𝛼 =   0 otherwise.   ο£³ Also, if 𝛼 = [𝛼1 , 𝛼2 , . . . , π›Όπ‘‘βˆ’1 ] then define 2 βŠ• 𝛼 = [2, 𝛼1 , 𝛼2 , . . . , π›Όπ‘‘βˆ’1 ]. The following result follows from Theorem 3.2.12 in much the same way that Corollary 3.2.8 followed from Theorem 3.2.6. So the proof is omitted. Corollary 3.2.13. If 𝑑 ∈ P and 𝑃 is admissible then βˆ‘οΈ π‘‘βˆ’2 Γ– π‘œ #O (𝑃) = 𝛿2βŠ•π›Ό 2 (𝑑 + 1 βˆ’ 𝑖 βˆ’ π‘Ÿ π‘‘βˆ’1βˆ’π‘– ). π›ΌβˆˆπΆ β€² (𝑑) 𝑖=0 3.3 A formula for the weighted sum of 𝑝 𝑛 (𝑃) We do not know of a simpler closed formula for 𝑝 𝑛 (𝑃) than the one given above, but we can get a simplification if we look at a weighted sum. Define a Dyck path with π‘˜ steps to be a path starting at (0, 0), ending at (π‘˜, 0), that uses only down steps [1, βˆ’1] and up steps [1, 1], and that never drops below the π‘₯-axis. A Dyck walk of length π‘˜ is a generalised version of a Dyck path where we allow the path to end at any point (π‘˜, 𝑦) for 𝑦 β‰₯ 0. We then define a modified Dyck walk to be a Dyck walk where the last step may possibly drop below the π‘₯-axis. In other words, a modified Dyck walk is a walk starting at (0, 0) consisting of only up steps and down steps that may end at any height β„Ž β‰₯ βˆ’1, and that does not drop below the π‘₯-axis except possibly at the final step. Define 𝑅 π‘˜ be the set of 𝑦-coordinate sequences of modified Dyck walks of length π‘˜. A walk π‘Ÿ ∈ 𝑅 π‘˜ takes the form (π‘Ÿ 0 , π‘Ÿ 1 , . . . π‘Ÿ π‘˜ ) where π‘Ÿπ‘– is the height of the 42 1𝑙 2𝑙 1π‘Ÿ 2𝑙 1π‘Ÿ 2𝑙 1π‘Ÿ 1𝑙 1π‘Ÿ 9 8 7 6 5 4 3 2 1 Figure 3.3 An example of a walk in 𝑀9 (𝑃) for 𝑝 = {9, 7, 5, 3} end of the 𝑖-th step and π‘Ÿ 0 = 0. From this, we have that π‘Ÿπ‘– β‰₯ 0 for all 0 ≀ 𝑖 < π‘˜, π‘Ÿ π‘˜ β‰₯ βˆ’1, and π‘Ÿπ‘– = π‘Ÿπ‘–βˆ’1 Β± 1 for all 1 ≀ 𝑖 ≀ π‘˜. We will give a generalization of Theorem 1.2 found in [11] with a simpler, combinatorial proof. Theorem 3.3.1. For 𝑛 β‰₯ 1 and 𝑃 = {𝑝 1 > 𝑝 2 > Β· Β· Β· > 𝑝 π‘˜ } βŠ† [𝑛], we take the convention that 𝑝 0 = 𝑛 + 1 and 𝑝 π‘˜+1 = 1. Then if we take the convention that 00 = 1, we have the following. βˆ‘οΈ βˆ‘οΈ Γ– π‘˜ |𝑄|+1 2 | 𝑝 𝑛 (𝑄)| = 2 π‘›βˆ’π‘˜ (π‘Ÿπ‘– + 1) 𝑝𝑖 βˆ’π‘π‘–+1 . π‘„βŠ†π‘ƒ π‘Ÿβˆˆπ‘… π‘˜ 𝑖=0 This will be proven later, but first we need to set up some combinatorial objects. Define the set of decorated Motzkin walks, 𝑀𝑛 (𝑃), to be the set of all lattice walks with 𝑛 steps, starting at (0, 0), consisting of steps [1, βˆ’1], [1, 0], and [1, 1], such that every step starts weakly above the π‘₯-axis, and where the steps are numbered 1, 2, . . . , 𝑛 from right to left. Note that this will allow walks that can go below the π‘₯-axis only on their final step. Furthermore, we require that in each walk of 𝑀𝑛 (𝑃) the step numbered π‘˜ be either the up step [1, 1] or the down step [1, βˆ’1] if π‘˜ ∈ 𝑃, and the horizontal step [1, 0] if π‘˜ βˆ‰ 𝑃. Finally, we give every step of the walk two labels. The first is an integer in [β„Ž + 1] where β„Ž is the height of the starting point of the step. The second label is either a right or left designation subject to the condition that down steps are always labeled as left and up steps always labeled as right. An example of an element in 𝑀𝑛 (𝑃) is given in Figure 3.3 where the number of each step is at the bottom of the figure and the label of each step is directly above the step. Note that for simplicity, we have combined the two labels by giving 𝑙 and π‘Ÿ subscripts to the height labels. For instance, the label given to the third step in Figure 3.3 is 2𝑙 meaning it has a height label of 2 and a left designation. 43 The count for the number of walks in 𝑀𝑛 (𝑃) is given by the following result. Theorem 3.3.2. Suppose 𝑛 β‰₯ 1 and 𝑃 βŠ† [𝑛]. Then the formula βˆ‘οΈ Γ– π‘˜ |𝑀𝑛 (𝑃)| = 2π‘›βˆ’π‘˜ (π‘Ÿπ‘– + 1) 𝑝𝑖 βˆ’π‘π‘–+1 π‘Ÿβˆˆπ‘… π‘˜ 𝑖=0 gives the count for the number of distinct decorated Motzkin walks. Proof. If we consider any walk in 𝑀𝑛 (𝑃) we note that by removing all horizontal steps we reduce the walk to one in 𝑅 π‘˜ . We may also reverse this process by starting with a walk π‘Ÿ ∈ 𝑅 π‘˜ and adding horizontal steps as specified by 𝑃. Therefore, to find |𝑀𝑛 (𝑃)| we need only sum over all sequences π‘Ÿ ∈ 𝑅 π‘˜ and for each resulting walk, determine how many different labelings are possible. Consider all walks in 𝑀𝑛 (𝑃) corresponding to a fixed π‘Ÿ ∈ 𝑅 π‘˜ . Note that the height of the step corresponding to 𝑝𝑖+1 and the heights of the steps between 𝑝𝑖 and 𝑝𝑖+1 will have starting point at height π‘Ÿπ‘– since the height can only change on a step corresponding to an element in 𝑃. Therefore, there are π‘Ÿπ‘– + 1 choices for each of the labels of these 𝑝𝑖 βˆ’ 𝑝𝑖+1 steps. Additionally, since only horizontal steps have a choice for subscripts, we must multiply by a factor of 2 for each element not in 𝑃. Therefore, the total count is as stated. Given πœ‹ ∈ 𝔖𝑛 and arbitrary 𝑃 βŠ† [𝑛], let [πœ‹β€²] be the cyclic permutation obtained by adding the element 𝑛 + 1 to the end of πœ‹ and wrapping it around into a circle, and let 𝑃′ = 𝑃 βˆͺ {𝑛 + 1}. We then have that the cyclic permutations with cPin[πœ‹β€²] = 𝑃′ are in bΔ³ection to those in 𝑝 𝑛 (𝑃), since this operation is invertible, and preserves all pinnacles except 𝑛 + 1. Define an intermediate set to be the set of all elements between (but not including) two consecutive elements of 𝑃′ in [πœ‹β€²]. Intermediate sets may be empty. Given πœ‹ a cyclic vale is any vale of [πœ‹β€²]. Because 𝑛 + 1 will always be a pinnacle, all cyclic vales will be in [𝑛] and will alternate with the pinnacles, which means there will be exactly π‘˜ + 1 of them in [πœ‹β€²] where π‘˜ is the number of pinnacles of πœ‹. In order to prove Theorem 3.3.1, we will interpret the sum βˆ‘οΈ 2|𝑄|+1 | 𝑝 𝑛 (𝑄)| π‘„βŠ†π‘ƒ 44 as the number of cyclic permutations such that [πœ‹β€²] ∈ [𝔖𝑛+1 ], cPin[πœ‹β€²] = 𝑄 β€² = 𝑄 βˆͺ {𝑛 + 1} βŠ† 𝑃′, and where every element of 𝑄 is marked as either left or right subjected to certain restrictions. If we note that every element of a cyclic permutation is either a pinnacle, a vale, or in the middle of an increasing or decreasing sequence of three elements, we may impose the following labeling. 1. Any element that is a cyclic vale may be marked as either right or left. 2. Any element of 𝑃 that is not a cyclic vale is always marked as right. 3. Any element not in 𝑃 that is in the middle of a decreasing sequence of 3 elements is always marked as right. 4. Any element not in 𝑃 that is in the middle of an increasing sequence of 3 elements is always marked as left. Let us call the set of all such permutations 𝑉𝑛 (𝑃). Note that by this convention, all markings are forced except those at the cyclic vales, which are all free, and therefore the cardinality of 𝑉𝑛 (𝑃) is βˆ‘οΈ 2|𝑄|+1 | 𝑝 𝑛 (𝑄)| π‘„βŠ†π‘ƒ since the number of cyclic vales is |𝑄| + 1 and since the number of cyclic permutations with cPin[πœ‹β€²] = 𝑄 β€² is | 𝑝 𝑛 (𝑄)|. Next, we define a map 𝑓 from 𝑀𝑛 (𝑃) to 𝑉𝑛 (𝑃). To do this, we read the steps of some π‘š ∈ 𝑀𝑛 (𝑃) one at a time and use it to build up a cyclic permutation. The process is described as follows. 1. Start with the cyclic permutation consisting of only 𝑝 0 = 𝑛 + 1. In all future steps, an intermediate set will be said to be available if neither of the elements in 𝑃′ that bound it have a left label. To this end, 𝑝 0 is assumed to have a right label. 2. Take the current leftmost step of walk π‘š and insert its step number, 𝑖, into the cyclic permutation in the following manner. Let the label of the step be β„Žπ‘₯ . Counting clockwise from 𝑝 0 , insert 𝑖 into the β„Ž-th available intermediate set and give it the left/right label 45 corresponding to the subscript π‘₯. If the intermediate set was empty, there is only one way to insert 𝑖π‘₯ . If the intermediate set is non-empty, look at the current smallest element of that set, 𝑣, and place 𝑖 adjacent to 𝑣 on the side corresponding to 𝑣’s label. Note that if π‘˜ was in 𝑃′, the available intermediate sets for future steps will be renumbered. Finally, delete the step numbered 𝑖 from the walk. 3. Repeat until all elements have been placed and the walk is empty. As an example of this algorithm, suppose that 𝑃 = {9, 7, 5, 3} and consider the walk in Figure 3.3. To compute the output of the map in 𝑉9 (𝑃) we successively generate the following permutations as we read the steps of 𝑃 from left to right, inserting the next element as indicated by the number and label of the step in the walk. Elements in 𝑃 are in bold to make it easier to see the intermediate sets. Commentary is provided for the first few insertions to aid the reader. 46 [10r ] [10r , 9r ] : 9π‘Ÿ is inserted in the only intermediate set available, splitting it in two. [10r , 8𝑙 , 9r , 7l ] : 7𝑙 is inserted in the second intermediate set because its label is 2𝑙 ; from here to the end of the algorithm, no other elements will be inserted between 9 and 7, or between 7 and 10 because 7 ∈ 𝑃 and step 7 has a left label. [10r , 6π‘Ÿ , 8𝑙 , 9r , 7l ] : 6π‘Ÿ is inserted to the left of the smallest element, 8, of the first intermediate set because 8 has a left label. [10r , 6π‘Ÿ , 5r , 8𝑙 , 9r , 7l ] : Inserting 5π‘Ÿ splits the only available intermediate set into two (one from 10 to 5 and one from 5 to 9) since 5 ∈ 𝑃 and both are available since 5 has a right label. [10r , 6π‘Ÿ , 5r , 4𝑙 , 8𝑙 , 9r , 7l ] [10r , 6π‘Ÿ , 5r , 3l , 4𝑙 , 8𝑙 , 9r , 7l ] [10r , 6π‘Ÿ , 2𝑙 , 5r , 3l , 4𝑙 , 8𝑙 , 9r , 7l ] [10r , 6π‘Ÿ , 1π‘Ÿ , 2𝑙 , 5r , 3l , 4𝑙 , 8𝑙 , 9r , 7l ] The last line is the final output. We will now prove some properties about this map so that we may show it is well-defined. Lemma 3.3.3. In the final result, all elements in 𝑃′ that are not cyclic vales are guaranteed to have right labels. Proof. This follows because when an element of 𝑃′ with a left label is initially inserted, it will become a cyclic vale. Indeed, it is a cyclic vale upon insertion since it is the smallest element inserted so far. And in all future steps no elements are ever inserted next to it on account of the intermediate sets on either side being unavailable. So it will remain a cyclic vale until the end. Lemma 3.3.4. The output of 𝑓 will always have pinnacles a subset of 𝑃′ Proof. Consider some element 𝑖 βˆ‰ 𝑃′. Since all elements become vales when initially placed, it is enough to show that 𝑖 remains next to to one of its larger adjacent elements through the end of the 47 algorithm. But this is immediate because if 𝑖 is labeled as left, then no future element will ever be inserted directly to the right of 𝑖, and similarly for a right label. Since no element is ever removed, we have that 𝑖 will remain next to a larger element and therefore fail to be a pinnacle. Lemma 3.3.5. In the final result, all elements 𝑖 βˆ‰ 𝑃′ that are also not vales will be in the middle of a decreasing sequence of three elements if 𝑖 has a right label, and in the middle of an increasing sequence of three elements if 𝑖 has a left label. Proof. First, since 𝑖 cannot be a vale by assumption and since it cannot be a pinnacle by Lemma 3.3.4, the only remaining possibilities are that it is in the middle of a decreasing or increasing sequence. If such an element 𝑖 has a left label, then the algorithm forces all elements which are less than 𝑖 and placed adjacent to 𝑖 to be to its left. Therefore, no element smaller than 𝑖 will be placed to its right, which makes it impossible for 𝑖 to end up in the middle of a decreasing sequence. Therefore, it must be in the middle of an increasing one. A similar proof holds for when 𝑖 has a right label. Lemma 3.3.6. At any step of the algorithm, if 𝑝𝑖 was the last element of 𝑃′ to be placed, then there will be π‘Ÿπ‘– + 1 available intermediate sets for the next step. Proof. Suppose that element 𝑖 was just placed in [πœ‹β€²]. If 𝑖 ∈ 𝑃′ corresponds to an up step, then 𝑖 will have a right label and the net effect on the permutation will be to replace the intermediate set it landed in with two new ones on either side, resulting in an increase of one available intermediate set. If 𝑖 ∈ 𝑃′ corresponds to a down step however, it will have a left label and therefore make the intermediate set it lands in unavailable, for a net loss of one intermediate set. Finally, if 𝑖 βˆ‰ 𝑃′, then 𝑖 cannot change the number of intermediate sets since they are completely determined by the positions of the elements in 𝑃′. This, combined with the fact that at the start of the process there is always one available intermediate set and that π‘Ÿ 0 = 0, is enough to show the result by induction. Proposition 3.3.7. The algorithm defined by 𝑓 is well defined. In particular it always terminates, and outputs a permutation in 𝑉𝑛 (𝑃). 48 Proof. To prove that 𝑓 terminates, note that there will always be at least one available intermediate set in which to place elements because every π‘Ÿπ‘– β‰₯ 0, for 0 ≀ 𝑖 < π‘˜ and so by Lemma 3.3.6 there will always be at least one intermediate set at each step. Lemma 3.3.4 shows that the pinnacles will be a subset of 𝑃′, and Lemmas 3.3.3 and 3.3.5 together show that those elements which are not cyclic vales will be marked as specified by the set 𝑉𝑛 (𝑃). Finally, since the algorithm marks all cyclic vales, we have that 𝑓 is well-defined. We now construct the inverse 𝑔 = 𝑓 βˆ’1 by reversing each step of the algorithm for 𝑓 . 1. Start with a permutation [πœ‹β€²] ∈ 𝑉𝑛 (𝑃). We will build a walk π‘š ∈ 𝑀𝑛 (𝑃) from right to left with steps numbered 1, 2, . . . , 𝑛. To build step number 𝑖, we remove the element 𝑖 from [πœ‹β€²] in the following way. 2. Locate the smallest element, 𝑖, of [πœ‹β€²], and remove it to form [𝜎]. Now in [𝜎] take note of the intermediate set, 𝑆, from which 𝑖 was removed. Count how many available intermediate sets 𝑆 is clockwise from 𝑝 0 and call this number β„Ž. Then add a step to the walk π‘š with label β„Žπ‘₯ where π‘₯ corresponds to whether the element was labeled left or right. The step is placed so that it begins at height β„Ž βˆ’ 1 where β„Ž is the number of available intermediate sets in [πœ‹β€²] after 𝑖 is removed. The slope of the new step is determined as follows. a) If 𝑖 βˆ‰ 𝑃, the step will be a horizontal step. b) If 𝑖 ∈ 𝑃 and 𝑖 has a left label, the step will be a down step. c) If 𝑖 ∈ 𝑃 and 𝑖 has a right label, the step will be an up step. 3. Label [𝜎] as [πœ‹β€²] and continue with the above process until [πœ‹β€²] consists of only 𝑝 0 . The resulting walk is the final output of the map. We must prove that this map is well-defined. 49 Lemma 3.3.8. At every step of the process, the pinnacles of [πœ‹β€²] will always be in 𝑃′, regardless of how many elements have been removed. Proof. To see this, note that [πœ‹β€²] starts with all pinnacles in 𝑃′ by assumption, and no non-pinnacle can ever become a pinnacle since we always remove the smallest element. Lemma 3.3.9. At every step where 𝑖 is removed from [πœ‹β€²] to form [𝜎], the intermediate set in [𝜎] from which 𝑖 was removed will be available. Proof. Suppose the intermediate set in [𝜎] from which 𝑖 was removed was unavailable in [𝜎], which would force one of the two bounding elements in 𝑃′ to have a left label. Now any element 𝑝 ∈ 𝑃′ with a left label is a cyclic vale at the start of the algorithm, and since there are no other elements in 𝑃′ between 𝑝 and 𝑖 to be pinnacles, it must be that 𝑖 > 𝑝. But this contradicts the assumption that the smallest element is being removed. Therefore, 𝑖 must have been removed from an available intermediate set. Lemma 3.3.10. The algorithm 𝑔 will produce a connected walk. Proof. Consider any step π‘šπ‘– formed by removing element 𝑖 from [πœ‹β€²] and let π‘šπ‘–βˆ’1 be the step placed just before that (when 𝑖 βˆ’ 1 was removed from [πœ‹β€²]). Then by the definition of 𝑔, if π‘Ÿπ‘– and π‘Ÿπ‘–βˆ’1 are the starting heights of steps π‘šπ‘– and π‘šπ‘–βˆ’1 respectively, we have that π‘Ÿπ‘– + 1 must be the number of available intermediate sets in [πœ‹β€²] right after 𝑖 was removed while π‘Ÿπ‘–βˆ’1 + 1 was the number of available intermediate sets in [πœ‹β€²] right before 𝑖 was removed. We now have three cases. 1. Case 1: Suppose that 𝑖 was not in 𝑃′. Then the number of available intermediate sets will be unchanged once 𝑖 is removed, and since 𝑔 will cause π‘šπ‘– to be horizontal in this case, we have that π‘šπ‘– will end at height π‘Ÿπ‘–βˆ’1 , thereby connecting it to the previous step. 2. Case 2: Suppose that 𝑖 ∈ 𝑃′ and 𝑖 had a left label. Then the intermediate set it occupied will become available by Lemma 3.3.9 and there will be a net increase of one available intermediate set. Since in this case 𝑔 causes π‘šπ‘– to have downward slope, we have that π‘šπ‘– will end at height π‘Ÿπ‘–βˆ’1 , thereby connecting it to the previous step. 50 3. Case 3: Suppose that 𝑖 ∈ 𝑃′ and 𝑖 had a right label. Then the intermediate sets on each side of 𝑖 must be available or else Lemma 3.3.9 will be contradicted when 𝑖 is removed. Removing 𝑖 will then join these available intermediate sets into one available set, and there will be a loss of one available intermediate set. Since in this case 𝑔 causes π‘šπ‘– to have upward slope, we have that π‘šπ‘– will end at height π‘Ÿπ‘–βˆ’1 , thereby connecting it to the previous step. Therefore, since in every case we have that the newly placed step connects to the previous, we will have that the final walk will be connected. Proposition 3.3.11. The walk produced by the algorithm is in 𝑀𝑛 (𝑃). Proof. By definition, 𝑔 causes every step 𝑖 to have its label in [π‘Ÿπ‘– + 1] because the numeric label for 𝑖 is chosen from the available intermediate sets after it is removed, which is π‘Ÿπ‘– + 1. Also, 𝑔 forces all slanted steps to have the required left/right label by definition. Additionally, the walk will be connected by Lemma 3.3.10 and also begin on the π‘₯-axis because there will be only one available intermediate set when the process is finished (because at the end, all that is left of the permutation is [ 𝑝 0 ]). Finally, every step of the walk must start weakly above the π‘₯-axis because the only time there can be no available intermediate sets in [πœ‹β€²] is at the start of the algorithm, since removing an element always leaves behind an available intermediate set by Lemma 3.3.9. This means that π‘Ÿπ‘– must be at least zero for all 𝑖 except possibly the last one, which forces all steps to begin weakly above the π‘₯-axis. Therefore, the result π‘š ∈ 𝑀𝑛 (𝑃) and we have that the map is well-defined. Proposition 3.3.12. The maps 𝑓 and 𝑔 defined above are inverses of each other. Proof. First, given a walk π‘š ∈ 𝑀𝑛 (𝑃), we let π‘šπ‘– be the step numbered 𝑖, that is, the 𝑖-th step from the right in the original π‘š (note that if segments are deleted from π‘š, we do not re-index or renumber the remaining segments). Let 𝑓𝑖 be the step in 𝑓 that deletes walk segment π‘šπ‘– and adds element 𝑖 to [πœ‹β€²], and let 𝑔𝑖 be the step in 𝑔 that adds walk segment π‘šπ‘– and removes element 𝑖 from [πœ‹]. Then we have that 𝑓 = 𝑓1 β—¦ 𝑓2 β—¦ Β· Β· Β· β—¦ 𝑓𝑛 and 𝑔 = 𝑔𝑛 β—¦ π‘”π‘›βˆ’1 β—¦ Β· Β· Β· β—¦ 𝑔1 by definition. 51 For a given walk π‘š ∈ 𝑀𝑛 (𝑃) we define 𝑆𝑖 to be the state of the walk and the permutation [πœ‹β€²] after applying 𝑓𝑖+1 Β· Β· Β· β—¦ π‘“π‘›βˆ’1 β—¦ 𝑓𝑛 . Under this notation, we have that 𝑆𝑛 is the initial state consisting of the original walk π‘š and [πœ‹β€²] = [𝑛 + 1] and that 𝑆0 is the final state consisting of the empty walk and the final permutation. We can then say that when applying 𝑓 to a walk, each 𝑓𝑖 will convert state 𝑆𝑖 into state π‘†π‘–βˆ’1 . Therefore, if we can show that 𝑔𝑖 applied to state π‘†π‘–βˆ’1 gives state 𝑆𝑖 , we will have that 𝑔 β—¦ 𝑓 is the identity because the 𝑔𝑖 will move back through all the states step by step. Consider the walk and permutation at some state 𝑆𝑖 . If we apply 𝑓𝑖 to this state, we will delete step π‘šπ‘– with label 𝑗π‘₯ and add element 𝑖 to [πœ‹β€²]. Then 𝑗 will be the number of the intermediate set into which 𝑖 is inserted and the left/right label of 𝑖 in πœ‹ will be π‘₯. This will give us state π‘†π‘–βˆ’1 . If we then apply 𝑔𝑖 , we will remove 𝑖 and add step π‘šπ‘– to walk π‘š with label 𝑗π‘₯ . Now we must show that the height and slope of π‘šπ‘– are as they were in 𝑆𝑖 . As was proven already in Lemma 3.3.6, the height of the start of step π‘šπ‘– in 𝑆𝑖 was β„Ž βˆ’ 1 where β„Ž is the number of available intermediate sets in [πœ‹β€²] in state 𝑆𝑖 . But by definition of 𝑔 acting on state π‘†π‘–βˆ’1 , the height of the start of the step that 𝑔 places must be β„Ž βˆ’ 1 again since the number of intermediate sets after 𝑖 is removed from [πœ‹β€²] is the same as it was in 𝑆𝑖 . Therefore, π‘šπ‘– will be placed at the same height. To show that slope is preserved, we consider each of the three cases. If π‘šπ‘– started as horizontal in 𝑆𝑖 , then 𝑖 βˆ‰ 𝑃 because of the restrictions imposed on 𝑀𝑛 (𝑃) and when we apply 𝑔𝑖 to state π‘†π‘–βˆ’1 we will get a horizontal step back. If π‘šπ‘– was an up step, we have by the restrictions imposed on 𝑀𝑛 (𝑃) that π‘šπ‘– ∈ 𝑃 and that π‘šπ‘– has a right label. Since the left/right label for 𝑛 in [πœ‹β€²] is the same as that for π‘šπ‘– , we have that 𝑔𝑖 will make π‘šπ‘– an up step again. A similar proof shows that if π‘šπ‘– was a down step before it was removed, it will be a down step again after it is returned. Therefore, 𝑔𝑖 undoes 𝑓𝑖 . Now for a given permutation [πœ‹β€²] ∈ 𝑉𝑛 (𝑃) we define 𝑆𝑖′ to be the state of the walk and permutation [πœ‹β€²] after applying 𝑔𝑖 Β· Β· Β· β—¦ 𝑔2 β—¦ 𝑔1 . Under this notation, we have that 𝑆′𝑛 is the final state consisting of the final walk and permutation [πœ‹β€²] = [𝑛 + 1], and that 𝑆′0 is the initial state consisting of the empty walk and the initial permutation. We can then say that when applying 𝑔 to a permutation, each 𝑔𝑖 will convert state π‘†π‘–βˆ’1 β€² into state 𝑆′. Therefore, if we can show that 𝑓 applied 𝑖 𝑖 to state 𝑆𝑖′ gives state π‘†π‘–βˆ’1 β€² , we will have that 𝑓 β—¦ 𝑔 is the identity because the 𝑓 will move back 𝑖 52 through all the states step by step. Consider the walk and permutation at some state π‘†π‘–βˆ’1 and suppose we apply 𝑔𝑖 where we remove element 𝑖 with label π‘₯ from [πœ‹β€²] and add step π‘šπ‘– to the walk. Then we will be in state 𝑆𝑖′ where the numeric label of π‘šπ‘– will indicate the intermediate set, 𝐼, from which 𝑖 was removed and the left/right label will be π‘₯. If we then apply 𝑓𝑖 , we will add 𝑖 back to the intermediate set corresponding to the label of π‘šπ‘– with left/right label π‘₯, and so we have that 𝑖 will get back to [πœ‹β€²] in 𝐼 and have the same β€² . label as in state π‘†π‘–βˆ’1 We must now show that the position of 𝑖 in [πœ‹β€²] is as it was in π‘†π‘–βˆ’1 β€² . If 𝑖 was the only element β€² , it will arrive back in the same position in [πœ‹β€²] and we are done. If 𝑖 was not in 𝐼 in state π‘†π‘–βˆ’1 the only element, we note that since it was a vale and since all non-pinnacles in 𝐼 must form a decreasing sequence to the left of 𝑖 and an increasing sequence to the right of 𝑖 (or become pinnacles themselves), we have that 𝑖 was initially positioned next to the second smallest element in 𝐼. By the labeling conventions imposed on [πœ‹β€²], any element in 𝐼 to the left of 𝑖 will have a right label and any elements in 𝑆 to its right will have a left label. Therefore, no matter which of these two elements becomes the new vale after 𝑖 is removed, we are guaranteed that 𝑓𝑖 will put 𝑖 adjacent to this element again, and that it will be on the left if the element is labeled left and the right if it is labeled right. Therefore, 𝑓𝑖 undoes 𝑔𝑖 . Since 𝑓 and 𝑔 undo each other step by step, we have that they are inverses of each other. Since the maps are inverses, we have that the sets are in bΔ³ection which finishes the proof of Theorem 3.3.1. We finish with a few remarks. Corollary 3.3.13. If we define π‘Š π‘˜ to be the set of 𝑦 coordinate sequences of all walks using steps [1, 1] and [1, βˆ’1] and ending at any height, then βˆ‘οΈ βˆ‘οΈ Γ– π‘˜ |𝑄|+1 2 | 𝑝 𝑛 (𝑄)| = 2 π‘›βˆ’π‘˜ (𝑀 π‘š + 1) 𝑝 π‘š βˆ’π‘ π‘š+1 π‘„βŠ†π‘ƒ π‘€βˆˆπ‘Š π‘˜ π‘š=0 where we sum over π‘Š π‘˜ instead of 𝑅 π‘˜ . Proof. To see this, we note that if any walk 𝑀 ∈ π‘Š π‘˜ has a step that starts below the π‘₯-axis, then for some 𝑖 there will exist a 𝑦-coordinate of the walk, 𝑀 𝑖 = βˆ’1, for which 𝑖 β‰  π‘˜. This will cause 53 𝑀 𝑖 + 1 = 0 and 𝑝𝑖 > 𝑝𝑖+1 so that the weight of walk 𝑀 zeros out. Therefore, the sum reduces to summing over 𝑅 π‘˜ . As a final comment, we note that if we require 𝑃 to not contain the element 1 then Theorem 3.3.1 reduces to Theorem 1.2 in [11]. This is because the rightmost step of every walk in 𝑀𝑛 (𝑃) will then be horizontal, which prevents all walks from dipping below the π‘₯-axis, and so we can safety restrict our definition of 𝑅 π‘˜ in Theorem 3.3.1 to require that all π‘Ÿ π‘˜ are non-negative, which is the same set that Fang used. Dividing both sides of Theorem 3.3.1 by two then gives Fang’s formula. 3.4 Recursion for admissible orderings Let πœ” be any ordering of the elements in some set 𝑆 βŠ† [𝑛]. Then for any permutation πœ‹ of a set of positive integers containing 𝑆, we say that ord(πœ‹) = πœ” if the elements in 𝑆 appear in the same relative order in πœ‹ as they do in πœ”. Now consider some 𝑃 = {𝑝 1 < 𝑝 2 < Β· Β· Β· < 𝑝 π‘˜ } βŠ† [𝑛] which need not be a pinnacle set (note the different indexing from the previous section). For the following theorems, we define an admissible ordering of 𝑃 to be any ordering πœ” of the elements of 𝑃 such that there exists a πœ‹ ∈ 𝔖𝑛 with Pin(πœ‹) = 𝑃 and ord(πœ‹) = πœ”. If such a πœ‹ exists, we call it a witness to the ordering. Under this definition, it makes sense to talk about the admissible orderings even when 𝑃 is not an admissible pinnacle set, since there will just be zero orderings. We will also define 𝑁 = {𝑛1 < 𝑛2 < . . . < 𝑛 π‘˜+1 } to be the set of the first π‘˜ + 1 positive integers that are not in 𝑃. Theorem 3.4.1. Suppose 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 π‘˜ } βŠ† [𝑛] is an arbitrary subset of [𝑛]. Let 𝑁 = {𝑛1 < 𝑛2 < . . . < 𝑛 π‘˜+1 } be the set of the first π‘˜ + 1 positive integers that are not in 𝑃. Then given a fixed ordering πœ” of 𝑃, there exists a πœ‹ ∈ 𝔖𝑛 with Pin(πœ‹) = 𝑃 and ord(πœ‹) = πœ” if and only if there exists a permutation 𝜏 of the elements 𝑃 βˆͺ 𝑁 with Pin(𝜏) = 𝑃 and ord(𝜏) = πœ”. Proof. Let πœ‹ ∈ 𝔖𝑛 be a witness to some admissible ordering of 𝑃. We will build up a permutation 𝜏 on the elements of 𝑃 βˆͺ 𝑁 which has Pin(𝜏) = 𝑃. An example of this process follows the proof. 54 To start, let 𝜏 = πœ‹ and identify each of the π‘˜ + 1 blocks of consecutive non-pinnacles in 𝜏. For each block, delete all but the smallest non-pinnacle. Finally, take the set of all π‘˜ + 1 remaining non-pinnacles in the result and standardize them to the set 𝑁 to get permutation 𝜏. Then 𝜏 will be a permutation of the elements of 𝑃 βˆͺ 𝑁 by definition with elements of 𝑃 in order πœ”. We must also have that Pin(𝜏) = 𝑃 since every 𝑝 ∈ 𝑃 started as a pinnacle in πœ‹, and the elements on either side of 𝑝 could only decrease throughout the steps of this process. Since all other elements end up adjacent to a pinnacle, there can be no added pinnacles, and so we have 𝜏 as specified. To see the reverse direction, simply take any 𝜏 with a given ordering of the elements of 𝑃 as the pinnacle set and add the elements [𝑛] \ (𝑃 βˆͺ 𝑁) in increasing order to the end of 𝜏. The result will be in 𝔖𝑛 and have pinnacle set 𝑃 in the same order as in 𝜏. As an example, suppose that 𝑛 = 8, 𝑃 = {3, 7} and πœ‹ = 57642318. Then 𝑁 = {1, 2, 4}, πœ” = 73, and we build up 𝜏 in the following steps: 𝜏 = 57642318 𝜏 = 57231 𝜏 = 47231 We may now state a corollary which will always allow us to reduce to the case where we only need to look for witnesses in 𝔖2π‘˜+1 Corollary 3.4.2. Given 𝑃 = {𝑝 1 < 𝑝 2 < Β· Β· Β· < 𝑝 π‘˜ } and 𝑁 as above, standardize the set 𝑃 βˆͺ 𝑁 and let 𝑃′ and 𝑁 β€² be the sets that 𝑃 and 𝑁 standardize to, respectively. Then the number of admissible orderings of set 𝑃 for πœ‹ ∈ 𝔖𝑛 is the same as the number of admissible orderings of set 𝑃′ for πœ‹ ∈ 𝔖2π‘˜+1 . Proof. Simply standardize the permutation 𝜏 given in the proof of the previous theorem. For example, if we standardize the 𝜏 = 47231 we had at the end of the previous example, we would get 𝜏 = 45231 ∈ 𝔖5 where now 𝑃′ = {5, 3}. 55 In all that follows we will assume that 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 π‘˜ } and 𝑛 = 2π‘˜ + 1 (3.3) since counting admissible orders when 𝑛 is larger can be reduced to this case. Note that because of this, specifying 𝑃 is enough to determine 𝑁 since 𝑁 = [2π‘˜ + 1] \ 𝑃. Let 𝑂 (𝑃) be the set of admissible orderings of set 𝑃, and π‘œ(𝑃) = |𝑂 (𝑃)|. More generally, if we let 𝑁𝑖 = {𝑛1 < 𝑛2 < . . . < 𝑛𝑖 } be the 𝑖 smallest elements of 𝑁, we define 𝑂 𝑖 (𝑃) = {πœ” ∈ 𝑆 𝑃βˆͺ𝑁𝑖 | there is πœ‹ ∈ 𝔖2π‘˜+1 with ord(πœ‹) = πœ” and Pin(πœ‹) = 𝑃} where 𝑆 𝐴 is the set of all permutations of the set 𝐴. We further define π‘œπ‘– (𝑃) = |𝑂 𝑖 (𝑃)| and note that 𝑂 0 (𝑃) = 𝑂 (𝑃). Essentially, 𝑂 𝑖 (𝑃) β€œkeeps track” of the positions of not only the elements of 𝑃, but of the positions of the 𝑖 smallest elements of 𝑁, too. As an example, consider the set 𝑃 = {3, 5}. Then π‘œ(𝑃) = 2 since all orderings are admissible. However, π‘œ1 (𝑃) = 4 since 𝑂 1 (𝑃) = {135, 315, 513, 531} with corresponding witnesses {13254, 23154, 45132, 45231}. Note that the orderings 351 and 153 are not included however because there is no way to insert the elements 2 and 4 to get a permutation in 𝔖5 having pinnacle set 𝑃. In the following results, we will need to talk about witnesses to specific orderings in 𝑂 𝑖 (𝑃). The following lemma will allow us to make certain assumptions about the witness we wish to pick. Lemma 3.4.3. Consider any πœ” ∈ 𝑂 𝑖 (𝑃) where the conditions in (3.3) hold and where 𝑖 < 𝑝 1 . Then if πœ”β€² is obtained by permuting the elements in [𝑖] in πœ” among their indices, then πœ”β€² ∈ 𝑂 𝑖 (𝑃) also. Proof. Since πœ” is an admissible ordering, there must exist at least one witness to it which we will call πœ‹. Because 𝑛 = 2π‘˜ + 1 we know that in πœ‹ the pinnacles and non-pinnacles, which are 56 the elements in 𝑃 and not in 𝑃 respectively, alternate beginning and ending with a non-pinnacle. Therefore each element of [𝑖] will be adjacent to two pinnacles larger than itself, and since all values in [𝑖] are smaller than all pinnacles, this will still be the case after permuting the elements in [𝑖]. Therefore, no elements in [𝑖] can become pinnacles. Additionally, no pinnacles can be lost because the only elements to move are those in [𝑖] and if an element of [𝑖] adjacent to a pinnacle gets swapped, it will just be replaced by a different value in [𝑖] that is still smaller than the pinnacle. Finally, we have that any element 𝑗 that is not in 𝑃 or [𝑖] cannot become a pinnacle because neither 𝑗 nor the two elements of 𝑃 initially adjacent to it will move during the swap. Therefore, no pinnacles are gained or lost, and so the resulting permutation will be a witness to the corresponding ordering πœ”β€², which shows it must be in 𝑂 𝑖 (𝑃). Given 𝑃 β‰  βˆ… and corresponding 𝑁, consider the set [2π‘˜ + 1] \ {𝑝 1 , 𝑛1 } and standardize so that the elements are in [2π‘˜ βˆ’ 1]. Let 𝑃′ be the set that the elements in 𝑃 \ {𝑝 1 } get mapped to which will always be {𝑝 2 βˆ’ 2, 𝑝 3 βˆ’ 2, . . . 𝑝 π‘˜ βˆ’ 2} if 𝑖 < 𝑝 1 . Then define the reduction operator π‘Ÿ (𝑃) = 𝑃′. We now wish to form a bΔ³ection between a subset of the elements in 𝑂 𝑖 (𝑃) and those in some 𝑂 𝑖 β€² (𝑃′). To this end, for 𝑗 ∈ {0, 1, 2} we define 𝑗 𝑂 𝑖 (𝑃) = {πœ” ∈ 𝑂 𝑖 (𝑃) | 𝑝 1 is adjacent to 𝑗 elements in [𝑖]} 𝑗 𝑗 and let π‘œπ‘– (𝑃) = |𝑂 𝑖 (𝑃)|. We then have the following result. Lemma 3.4.4. Suppose 𝑖 β‰₯ 0, that the conditions in (3.3) hold, and that 𝑃 is non-empty. Then if for some 𝑗 ∈ {0, 1, 2} we have that 𝑖 < 𝑝 1 and 𝑂 𝑖 (𝑃) β‰  βˆ… and we let 𝑃′ = π‘Ÿ (𝑃), then we have the 𝑗 following ο£± 𝑖(𝑖 βˆ’ 1)π‘œπ‘–βˆ’1 (𝑃′)  if 𝑗 = 2,       𝑗 ο£²  π‘œπ‘– (𝑃) = 2π‘–π‘œπ‘– (𝑃′) if 𝑗 = 1,      π‘œπ‘–+1 (𝑃′)    if 𝑗 = 0. ο£³ 57 𝑗 Proof. Note that since we have that 𝑂 𝑖 (𝑃) β‰  βˆ…, there must exist at least 𝑗 elements in [𝑖] and 2 βˆ’ 𝑗 elements not in [𝑖] but less than 𝑝 1 to surround 𝑝 1 . Therefore, we have the inequalities 𝑖 β‰₯ 𝑗 and 𝑖 + 2 βˆ’ 𝑗 < 𝑝1. We will consider the case where 𝑗 = 2 in detail and note the changes that must occur for when 𝑗 = 0, 1. Note first that by Lemma 3.4.3 we have that the existence of an ordering πœ” ∈ 𝑂 𝑖2 (𝑃) in which πœ” contains the factor π‘₯ 𝑝 1 𝑦 implies the existence of one containing the factor 1𝑝 1 2 and visa versa. If we let 𝐴 = {πœ” ∈ 𝑂 𝑖2 (𝑃) | 1𝑝 1 2 is a factor of πœ”} then we will have that π‘œπ‘–2 (𝑃) = 𝑖(𝑖 βˆ’ 1) Β· | 𝐴|. where we have the factor of 𝑖(𝑖 βˆ’ 1) because there are 𝑖 ways to choose an element in [𝑖] to the left of 𝑝 1 and 𝑖 βˆ’ 1 ways to choose a a different element in [𝑖] to the right. We may now define a map between set 𝐴 and 𝑂 π‘–βˆ’1 (𝑃′) in which we remove the factor 1𝑝 1 from πœ” and standardize to the set 𝑃′ βˆͺ [𝑖 βˆ’ 1]. To show this ordering has a witness, first consider any witness, πœ‹, to πœ” and note that πœ‹ must also contain the factor 1𝑝 1 2 since elements in 𝑃 must alternate with those that do not, and so no new elements can be inserted between 1, 𝑝 1 , and 2. If we then remove 1𝑝 1 from πœ‹ and standardize to get πœ‹β€², we are left with a witness to the ordering πœ”β€². Note that the element to the left of 1 in πœ‹, if it exists, must have originally been a pinnacle, and since in πœ‹β€² it will end up being adjacent to 1 again, it must remain a pinnacle. Furthermore, since 2 cannot become a pinnacle, and since the relative order of all other elements was preserved, we have that the pinnacle set of πœ‹β€² is 𝑃′ which shows that πœ”β€² is admissible. To reverse this map, consider some πœ”β€² ∈ 𝑂 π‘–βˆ’1 (𝑃′) and standardize to the set (𝑃 βˆͺ [𝑖]) \ {𝑝 1 , 1}. Note that since 𝑖 β‰₯ 𝑗 = 2, we have that πœ”β€² will contain the element 1, which will standardize to 2. Replace 2 with 1𝑝 1 2 to get the ordering πœ” which will be in 𝐴 if we can show it has a witness. To show this, consider any witness πœ‹β€² to πœ”β€², standardize to [2π‘˜ + 1] \ {𝑝 1 , 1}, and replace 2 with 1𝑝 1 2 to get πœ‹, which will be a witness to πœ”. An argument similar to the one above shows that the pinnacle set will be 𝑃, and so we have that πœ” is admissible, completing the proof in this case. 58 Since these maps are clearly inverses, we have that | 𝐴| = π‘œπ‘–βˆ’1 (𝑃′) which completes the case when 𝑗 = 2. For the case where 𝑗 = 1, we can use a similar proof where we use Lemma 3.4.3 to show that π‘œπ‘–2 (𝑃) = 2𝑖 Β· |{πœ” ∈ 𝑂 𝑖2 (𝑃) | 1𝑝 1 is a factor of πœ”}|. and then define a bΔ³ection to simply delete 𝑝 1 from πœ” and standardize to 𝑃′ βˆͺ [𝑖] to get πœ”β€². Care must be taken to prove this results in an ordering in 𝑂 𝑖 (𝑃′). To prove it has has a witness, one can use the fact that 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 to argue for the existence of a witness πœ‹ ∈ 𝔖2π‘˜+1 to πœ” which contains the factor 1𝑝 1 ( 𝑝 1 βˆ’ 1) where 𝑝 1 βˆ’ 1 βˆ‰ [𝑖]. Replacing this factor with 1 and standardizing will result in a witness for πœ”β€² with pinnacle set 𝑃′. The fact that 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 , together with the fact that 𝑖 β‰₯ 𝑗, must be used again when showing that the reverse of this map is well-defined. For the case where 𝑗 = 0, we may define our bΔ³ection between 𝑂 𝑖 (𝑃) and 𝑂 𝑖+1 (𝑃′) by taking 𝑗 some πœ” ∈ 𝑂 𝑖 (𝑃), replacing 𝑝 1 with 0, and standardizing to 𝑃′ βˆͺ [𝑖 + 1] to get πœ”β€². To prove that 𝑗 πœ” has a witness, one can use the fact that 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 to argue for the existence of a witness πœ‹ ∈ 𝔖2π‘˜+1 to πœ” which contains the factor ( 𝑝 1 βˆ’ 2) 𝑝 1 ( 𝑝 1 βˆ’ 1) where 𝑝 1 βˆ’ 1, 𝑝 1 βˆ’ 2 βˆ‰ [𝑖]. Replacing this factor with 0 and standardizing will then result in a witness for πœ”β€², which can be shown to be in 𝑂 𝑖+1 (𝑃′). The fact that 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 must be used again when showing that the reverse of this map is well-defined. Given some set 𝑃, we make the following definition: ο£±  ο£²1 if 𝑝 1 > 𝑗,    𝛿𝑗 =  0 otherwise.   ο£³ Then we can state our main result. Theorem 3.4.5. Let |𝑃| β‰₯ 1, 𝑃′ = π‘Ÿ (𝑃), 0 ≀ 𝑖 < 𝑝 1 , and suppose the conditions in (3.3) hold. Then we have the following recursion π‘œπ‘– (𝑃) = 𝑖(𝑖 βˆ’ 1)π‘œπ‘–βˆ’1 (𝑃′) + (2𝑖)𝛿𝑖+1 π‘œπ‘– (𝑃′) + 𝛿𝑖+2 π‘œπ‘–+1 (𝑃′). 59 Proof. Note that 𝑂 𝑖 (𝑃) can be partitioned into three (possibly empty) subsets depending on whether 𝑝 1 is directly adjacent to either two, one, or no elements of 𝑁𝑖 . It follows that π‘œπ‘– (𝑃) = π‘œπ‘–2 (𝑃) + π‘œπ‘–1 (𝑃) + π‘œπ‘–0 (𝑃). Therefore, we will have our result if we can show that ο£± 𝑖(𝑖 βˆ’ 1)π‘œπ‘–βˆ’1 (𝑃′)  if 𝑗 = 2,       𝑗 ο£²  π‘œπ‘– (𝑃) = 2𝑖𝛿𝑖+1 π‘œπ‘– (𝑃′) if 𝑗 = 1,      𝛿𝑖+2 π‘œπ‘–+1 (𝑃′)    if 𝑗 = 0. ο£³ 𝑗 If 𝑂 𝑖 (𝑃) is non-empty, then we have our result by Lemma 3.4.4 since we will have that 𝑖 +2βˆ’ 𝑗 < 𝑝 1 and the corresponding delta is 1. Therefore, we only need to concern ourselves with the case where 𝑗 𝑗 π‘œπ‘– (𝑃) = 0, in which we must prove that the corresponding expression for π‘œπ‘– (𝑃) is also zero. 𝑗 First, we claim that π‘œπ‘– (𝑃) = 0 if and only if either 𝑃 is not admissible, 𝑖 + 2 βˆ’ 𝑗 β‰₯ 𝑝 1 , or 𝑗 > 𝑖. 𝑗 That each of these three conditions independently forces π‘œπ‘– (𝑃) = 0 is not hard to see since we will either have that π‘œπ‘– (𝑃) = 0 or that there are not enough of the necessary elements to surround 𝑝 1 and have it still be a pinnacle. For the reverse direction, we prove the contrapositive. Suppose that 𝑃 is admissible, that 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 , and that 𝑗 ≀ 𝑖. In this case, chose any witness to any ordering of 𝑃 and call it πœ‹. Now by our two inequalities, we know there must exist two elements, π‘₯ and 𝑦, in πœ‹ such that 𝑗 of them are in [𝑖] and 2 βˆ’ 𝑗 of them are between 𝑖 and 𝑝 1 . If we then swap π‘₯ and 𝑦 with the pair of elements to either side of 𝑝 1 in πœ‹, we will have a witness to an ordering in 𝑗 𝑂 𝑖 (𝑃). The fact that the pinnacle set of this witness is indeed 𝑃 can be proven similarly to Lemma 3.4.3 since πœ‹ alternated pinnacles and non-pinnacles, and since all elements swapped were smaller 𝑗 than all pinnacles. Therefore, we have an ordering in 𝑂 𝑖 (𝑃), which proves it is non-empty. This finishes the proof of the claim. 𝑗 Therefore, in the case where π‘œπ‘– (𝑃) = 0 we may suppose that at least one of these three conditions 𝑗 is true. If 𝑗 > 𝑖, we immediately have that all three expressions for π‘œπ‘– (𝑃) are zero and so we still have equality even in the case when 𝑗 > 𝑖. If we assume that 𝑖 + 2 βˆ’ 𝑗 β‰₯ 𝑝 1 for some 𝑗 ∈ {0, 1, 2}, 60 we must have that 𝑗 < 2 since otherwise we contradict our assumption that 𝑖 < 𝑝 1 . But if 𝑗 = 0, 1, we immediately have that 𝛿𝑖+2βˆ’ 𝑗 is zero and so again we have equality. To finish the proof, all we have left to show is that all three expressions are zero if 𝑗 ≀ 𝑖, 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 , but 𝑃 is not admissible. Clearly if 𝑃′ fails to be admissible too, all three terms will immediately be zero, so suppose that 𝑃′ is admissible. This is equivalent to saying that for every element 𝑝 ∈ 𝑃′, the number of elements in 𝑃′ less than 𝑝 is exceeded by the number of elements not in 𝑃′ less than 𝑝. This will still be the case for all corresponding pinnacles in 𝑃 since both elements added are smaller than all other pinnacles, and so if 𝑃 fails to be admissible, it must be because the added element of 𝑃, 𝑝 1 , is less than 3. But supposing 𝑗 ≀ 𝑖 and 𝑖 + 2 βˆ’ 𝑗 < 𝑝 1 together force 𝑝 1 > 2, and so we have a contradiction. 𝑗 Therefore, since in all cases where π‘œπ‘– (𝑃) = 0 we have that the corresponding expression is also zero, we have our result. Corollary 3.4.6. This recursion can be used to compute π‘œ(𝑃) = π‘œ0 (𝑃). Furthermore, the number of terms that need to be computed will be asymptotically equal to π‘˜ 2 /4. Proof. First, note that every step reduces the size of 𝑃 by one, and so if we induct on π‘˜, we have the base case 𝑃 = βˆ…, and |𝑁 | = 1 which always has only one ordering. In order to show that we may repeatedly use this recursion however, we must show that we never need to compute some π‘œπ‘– (𝑃) where 𝑖 β‰₯ 𝑝 1 . First, note that on the first step when 𝑖 = 0, we must have that 𝑖 < 𝑝 1 since 𝑃 β‰  βˆ…. Now consider any application of the recursion on π‘œπ‘– (𝑃) where 𝑖 < 𝑝 1 . Since 𝑝′1 = 𝑝 2 βˆ’ 2 forces 𝑝′1 β‰₯ 𝑝 1 βˆ’ 1 by definition of π‘Ÿ (𝑃), we know that 𝑝′1 > 𝑖 βˆ’ 1 and so the recursion may be applied on π‘œπ‘–βˆ’1 (𝑃′). Now we consider π‘œπ‘– (𝑃′). If 𝑖 < 𝑝′1 we may apply the recursion; if not, then we will have that 𝑖 β‰₯ 𝑝 1 βˆ’ 1 which means 𝑝 1 ≀ 𝑖 + 1. But then we will have that 𝛿𝑖+1 = 0, and so we will not have to calculate π‘œπ‘– (𝑃′). Finally, we consider π‘œπ‘–+1 (𝑃′). If 𝑖 + 1 < 𝑝′1 we may apply the recursion; if not, then we will have that 𝑖 + 1 β‰₯ 𝑝 1 βˆ’ 1 and so 𝑝 1 ≀ 𝑖 + 2. But then we will have that 𝛿𝑖+2 = 0, and so we will not have to calculate π‘œπ‘–+1 (𝑃′). Therefore, the recursion never generates a term that cannot then be further broken down. 61 As to the number of terms that need to be calculated, let 𝑃 𝑗 = π‘Ÿ 𝑗 (𝑃) applying the π‘Ÿ operator 𝑗 times where 0 ≀ 𝑗 ≀ π‘˜. Note that since 𝑖 starts out as 0 and 𝑖 can only increase by at most 1 each step, we must have that 𝑖 ≀ 𝑗 for any term π‘œπ‘– (𝑃 𝑗 ). Additionally, since all permutations have elements in [2(π‘˜ βˆ’ 𝑗) + 1], we know that 𝑖 ≀ π‘˜ βˆ’ 𝑗 + 1 since the remaining π‘˜ βˆ’ 𝑗 elements are in 𝑃 𝑗 . Therefore when calculating terms of the form π‘œπ‘– (𝑃 𝑗 ), if 𝑗 ≀ π‘˜/2 we know that 0 ≀ 𝑖 ≀ 𝑗 while if π‘˜/2 ≀ 𝑗 ≀ π‘˜ we know that 0 ≀ 𝑖 ≀ π‘˜ βˆ’ 𝑗 + 1. Therefore, if we sum up all the different values that 𝑖 can take over all values of 𝑗, we have that the total number of terms is at most βŒŠπ‘˜/2βŒ‹ π‘˜ βŒŠπ‘˜/2βŒ‹ βŒŠπ‘˜/2βŒ‹     βˆ‘οΈ βˆ‘οΈ βˆ‘οΈ βˆ‘οΈ βŒŠπ‘˜/2βŒ‹ + 2 βŒŠπ‘˜/2βŒ‹ + 2 ( 𝑗 +1) + (π‘˜ βˆ’ 𝑗 +2) = ( 𝑗 +1) + ( 𝑗 +2) = + + βŒŠπ‘˜/2βŒ‹ +1 𝑗=0 𝑗=0 𝑗=0 2 2 𝑗=⌈(π‘˜+1)/2βŒ‰ which is asymptotically π‘˜ 2 /4. 3.5 Block representation of pinnacle sets Given a (not necessarily admissible) set 𝑃 = {𝑝 1 < 𝑝 2 < Β· Β· Β· < 𝑝 π‘˜ } βŠ† [𝑛], we may choose to represent 𝑃 as an array of some length 𝑛 β‰₯ 𝑝 π‘˜ consisting of 0s and 1s such that a given index 𝑖 contains a 1 if and only if 𝑖 ∈ 𝑃. For example, if we had 𝑃 = {3, 6, 7} then the corresponding array for 𝑛 = 7 would be [0, 0, 1, 0, 0, 1, 1]. For some fixed 𝑛, we can clearly we can go back and forth between these representations without loss of information, and the array will correspond to an admissible pinnacle set if and only if it is a ballot sequence, that is, at every index the number of 0s exceeds the number of 1s occurring before that index (we will not use this fact, but it is interesting). Now for the purposes of our proofs, it will be useful to think of 𝑃 using the array notation because it allows use to visually divide 𝑃 up into β€œblocks,” which is to say, we may break the array up into sub-arrays. For instance, in our previous example if we let 𝐡1 = [0, 0, 1], 𝐡2 = [0, 0, 1, 1] 62 then we may say that 𝑃 can be written as 𝐡1 𝐡2 where we concatenate the arrays to recover 𝑃. We may then apply algorithms recursively to each block, and combine the results to say something about 𝑃. For our purposes, it won’t matter how we break up 𝑃 provided that all blocks are non-empty, and so we will not (at this point) structure our notation to indicate how much of 𝑃 is contained in 𝐡1 . As an aside, but something that will not be used in the proof, we may choose our blocks carefully so that they correspond to trees. This is done by simply looking at the binary tree representation of 𝑃 (which is given in greater detail below), and letting 𝐡1 consist of those indices appearing in the first tree, 𝐡2 of those indices appearing in the second tree, and so on. Our approach is a little more general however as it allows us use blocks that contain β€œpart” of a tree, which will be useful in our applications. Using this particular division into blocks however will allow us to say some things about the tree representation of 𝑃 later. We now must introduce some new ideas and notation. Given a block 𝐡, which is to say, an array of some length π‘š containing only 0s and 1s, we may define a set, 𝑃 𝐡 , to contain all those indices in 𝐡 that are 1s. We then define 𝑃(𝐡) to be the set of permutations in π”–π‘š with pinnacle set 𝑃 𝐡 , and further define 𝑝(𝐡) = |𝑃(𝐡)|. For instance, suppose that in our running example we took 𝐡1 = [0, 0, 1]. Then 𝑃 𝐡1 = {3} and 𝑝(𝐡1 ) = 2 since there are two permutations in 𝔖3 that have pinnacle set {3}. On the other hand, if we took 𝐡2 = [0, 0, 1, 1] we would have 𝑃 𝐡2 = {3, 4} and 𝑝(𝐡2 ) = 0 since 𝑃 𝐡2 is not an admissible pinnacle set. We now take this a step further. Given a block 𝐡 of length 𝑛 with corresponding pinnacle set 𝑃 𝐡 , it will be desirable to modify 𝑃 𝐡 by adding additional elements larger than 𝑛 (that is to say, we wish to force additional pinnacles). Furthermore, we will want to require that these added elements are indistinguishable from one another, which is a deviation from normal pinnacle sets where all pinnacles are different. Pinnacle sets are still defined however even when considering permutations with repeated numbers, and so the notion still makes sense. More formally, define 𝑃(𝐡) 𝑖 to be all permutations of the multiset {1, 2, . . . , π‘š} βˆͺ {(𝑛 + 1) 𝑖 } that have pinnacle multiset 𝑃 𝐡 βˆͺ {(𝑛 + 1) 𝑖 }, and define 𝑝(𝐡) 𝑖 = |𝑃(𝐡) 𝑖 |. For instance, if 𝐡 = 63 [0, 0, 1, 0, 0, 0], then 𝑃 𝐡 = {3} and π‘š = 6. To compute 𝑃(𝐡) 2 , we must ask which permutations of the set {1, 2, 3, 4, 5, 6, 7, 7} have pinnacle set {3, 7, 7}, of which there are 36 (there are 3 ways to decide the order of 3, 7, 7 within the permutation, 2 ways to decide the order of 1 and 2 on either side of 3, and 6 ways to arrange the elements 4,5,6 to fill the remaining gaps between the pinnacles). On the other hand, 𝑝(𝐡) 5 = 0 because there would be too many pinnacles forced. There is a similar idea for forcing cyclic vales. Suppose once again that we have a block 𝐡 of length 𝑛 with corresponding pinnacle set 𝑃 𝐡 . It will be useful to talk about the set of permutations having not only pinnacle set 𝑃 𝐡 , but also a cyclic vale set that contains a certain set of desired elements. In fact, similar to how above we added new, large elements and forced them to be pinnacles, we will want to add new, small elements and force them to be cyclic vales. More formally, define 𝑃(𝐡) 𝑗 to be all permutations of the multiset {1, 2, . . . , 𝑛} βˆͺ {0 𝑗 } that have pinnacle set 𝑃 𝐡 and cyclic vale set containing the multiset {0 𝑗 }, and define 𝑝(𝐡) 𝑗 = |𝑃(𝐡) 𝑗 | . For instance, if 𝐡 = [0, 1, 1], then 𝑃 𝐡 = {2, 3} and π‘š = 3. To compute 𝑃(𝐡)2 , we must ask how many permutations of the set {0, 0, 1, 2, 3} have pinnacle set {2, 3} and also cyclic vale set containing {02 }, of which there are 6: there are 6 ways to order the elements 1, 2, 3 and then we may always insert the two 0s in a unique way in the remaining positions around 2 and 3 to force them to be pinnacles. On the other hand, 𝑃(𝐡)4 = 0 because the only way to force all four zeros to be cyclic vales is if they alternate with the numbers 1, 2, 3, but then this will force 1 to become a pinnacle. While the above ideas may seem strange, hopefully they will feel more natural in a minute. The gist is that in addition to requiring that a particular set becomes a pinnacle set, we may now throw in additional large elements and require them to be pinnacles, or additional small elements and require them to be cyclic vales. In fact, we will often do both at once, and to this end, define the notation 𝑃(𝐡) 𝑖𝑗 to be all permutations of the multiset {1, 2, . . . , 𝑛} βˆͺ {0 𝑗 , (𝑛 + 1) 𝑖 } that have pinnacle multiset 𝑃 𝐡 βˆͺ {(𝑛 + 1) 𝑖 } and vales set containing {0 𝑗 }. In the event that no such permutations exist, we simply say that 𝑃(𝐡) 𝑖𝑗 = βˆ…. Note that if any such permutations do exist, it will always be the case that no two elements of {(𝑛 + 1) 𝑖 } are adjacent, and that no two elements of {0 𝑗 } are adjacent, as that would not allow them to all be pinnacles or cyclic vales respectively. This fact will be helpful 64 in our first proof. Finally, we need to remind the reader of cyclic permutations. In general, any linear permutation in {1, 2, . . . 𝑛}βˆͺ{0 𝑗 , (𝑛+1) 𝑖 } included in 𝑃(𝐡) 𝑖𝑗 , that is, having pinnacle multiset 𝑃 𝐡 βˆͺ{(𝑛+1) 𝑖 } and cyclic vale set containing {0 𝑗 }, corresponds to a cyclic permutation in {1, 2, . . . 𝑛, ∞}βˆͺ{0 𝑗 , (𝑛+1) 𝑖 } having cyclic pinnacle multiset 𝑃 𝐡 βˆͺ {(𝑛 + 1) 𝑖 , ∞} and cyclic vale set containing {0 𝑗 }. This correspondence is achieved simply by appending ∞ onto the beginning of the linear permutation, and wrapping it around into a cyclic permutation. The reverse operation is also well defined. Therefore, we define 𝑐𝑃(𝐡) 𝑖𝑗 to be the set of cyclic permutations corresponding to the linear ones in 𝑃(𝐡) 𝑖𝑗 . Theorem 3.5.1. Suppose that some block 𝐡 (as described above) of length 𝑛 is decomposed into two, non-empty parts 𝐡1 and 𝐡2 such that the concatenation 𝐡1 𝐡2 gives back 𝐡. Suppose further that the number of ones in 𝐡2 is 𝑏. Then 𝑏+𝑖+1 βˆ‘οΈ 𝑝(𝐡) 𝑖𝑗 = 𝑝(𝐡1 ) π‘Žβˆ’1 𝑗 𝑝(𝐡2 ) π‘Ž 𝑖 π‘Ž=1 Proof. First, let 𝐿 be the set of all elements corresponding to those in block 𝐡1 together with the set {0 𝑗 }. Similarly let 𝐻 be the set of all remaining elements in [𝑛] not in 𝐿 together with the set {(𝑛 + 1) 𝑖 , ∞}. Then 𝐿 will be the β€œlow” set and 𝐻 the β€œhigh” set in the sense that all elements in 𝐿 will be smaller than all elements in 𝐻, and given any [πœ‹] ∈ 𝑐𝑃(𝐡) 𝑖𝑗 , we have that all elements in [πœ‹] will be in either 𝐿 or 𝐻. Since 𝑝(𝐡) 𝑖𝑗 = |𝑐𝑃(𝐡) 𝑖𝑗 | it suffices to consider only cyclic permutations to prove the result. Therefore given some [πœ‹] ∈ 𝑐𝑃(𝐡) 𝑖𝑗 we may decompose it into maximal consecutive sequences of elements either entirely in 𝐻 or entirely in 𝐿. Since such sequences from 𝐻 must alternate with those in 𝐿, we have that there are the same number of each and we call this number the alternations of [πœ‹] and denote it by π‘Ž. Note that π‘Ž must be at least 1 since we assumed both 𝐡1 and 𝐡2 were non-empty, and furthermore we know that π‘Ž cannot exceed the number of cyclic pinnacles in 𝐻 since every consecutive string of elements in 𝐻 is adjacent to two values in 𝐿 and so must contain 65 at least one cyclic pinnacle of [πœ‹]. Since every cyclic pinnacle element from 𝐻 must either be one of the 𝑏 pinnacles from 𝐡2 , 𝑛 + 1, or ∞, we have an upper bound of 𝑏 + 𝑖 + 1 for π‘Ž. Therefore, if we fix some 1 ≀ π‘Ž ≀ 𝑏 + 𝑖 + 1, we may reduce to proving that the number of permutations in 𝑐𝑃(𝐡) 𝑖𝑗 with π‘Ž alternations is |𝑃(𝐡1 ) π‘Žβˆ’1 𝑗 ||𝑃(𝐡2 ) π‘Ž | since the values of π‘Ž clearly 𝑖 partition all permutations in 𝑐𝑃(𝐡) 𝑖𝑗 . We prove this by constructing a bΔ³ection. An example follows this proof. Let 𝑙 = |𝐡1 |, β„Ž = |𝐡2 |, and suppose for the forward direction that [πœ‹] ∈ 𝑐𝑃(𝐡) 𝑖𝑗 has π‘Ž alternations. Then in [πœ‹] we may replace the block of consecutive elements in 𝐻 containing ∞ with the element ∞ and each of the other π‘Ž βˆ’ 1 blocks of consecutive elements in 𝐻 with the element 𝑙 + 1 to get [πœ‹ 𝐿 ]. Additionally, we may take the original [πœ‹] and replace each of the π‘Ž blocks of consecutive elements in 𝐿 with the element 0 and subtract 𝑙 from all remaining elements to get the cyclic permutation [πœ‹ 𝐻 ]. We must now show that [πœ‹ 𝐿 ] ∈ 𝑐𝑃(𝐡1 ) π‘Žβˆ’1 𝑗 and [πœ‹ 𝐻 ] ∈ 𝑐𝑃(𝐡2 )π‘Žπ‘– . From the construction given, it is easy to see that [πœ‹ 𝐿 ] is a permutation of the elements {1, . . . , 𝑙} βˆͺ {(𝑙 + 1) π‘Žβˆ’1 , ∞, 0 𝑗 } and that [πœ‹ 𝐻 ] is a permutation of the elements {1, . . . , β„Ž} βˆͺ {(β„Ž + 1) 𝑖 , ∞, 0π‘Ž }. Therefore, we need only show that all the necessary cyclic pinnacles and vales are formed in both cases. Consider [πœ‹ 𝐿 ]. Clearly we must have that every element in {(𝑙 + 1) π‘Žβˆ’1 } is a cyclic pinnacle since they are larger than all elements in {0, 1, . . . , 𝑙}, and since none of them are adjacent to each other or to ∞ because everything in {(𝑙 + 1) π‘Žβˆ’1 , ∞} originated from separate blocks of elements in [πœ‹]. Furthermore, given any element π‘₯ ∈ 𝐿 the relative order between π‘₯ and the elements on either side is the same in [πœ‹ 𝐿 ] as it was in [πœ‹], since the only change was that an element larger than π‘₯ may have been replaced by another element larger than π‘₯. Therefore, since all elements in 𝑃 𝐡1 and {0 𝑗 } were cyclic pinnacles and vales respectively in [πœ‹], they will continue to be so in [πœ‹ 𝐿 ], and so we are done. The proof for showing [πœ‹ 𝐻 ] ∈ 𝑐𝑃(𝐡2 )π‘Žπ‘– is almost identical, and therefore omitted. Therefore, our map is well-defined. To invert it, suppose that [πœ‹ 𝐿 ] ∈ 𝑐𝑃(𝐡1 ) π‘Žβˆ’1 𝑗 and [πœ‹ 𝐻 ] ∈ 𝑐𝑃(𝐡2 )π‘Žπ‘– . To combine them, first add 𝑙 to all elements of [πœ‹ 𝐻 ] to get [πœ‹β€²π» ]. Then write [πœ‹ 𝐿 ] in the form [∞𝐿 1 (𝑙 + 1)𝐿 2 (𝑙 + 1) Β· Β· Β· (𝑙 + 1)𝐿 π‘Ž ] where each 𝐿 𝑖 is a maximal consecutive sequence of 66 elements less than 𝑙 + 1. Similarly, we may write πœ‹β€²π» in the form [𝐻1 𝑙𝐻2 𝑙 Β· Β· Β· π‘™π»π‘Ž 𝑙] where each 𝐻𝑖 is a maximal consecutive sequence of elements greater than than 𝑙, and where 𝐻1 contains ∞. We then construct the cyclic permutation [πœ‹] = [𝐻1 𝐿 1 𝐻2 𝐿 2 Β· Β· Β· π»π‘Ž 𝐿 π‘Ž ]. It is easy to verify that [πœ‹] contains 𝑗 copies of the element 0, 𝑖 copies of the element 𝑛 + 1, and that all other elements are either ∞ or in 𝐡. Furthermore we note that given any element π‘₯ in [πœ‹], the relative sizes of π‘₯ and its two adjacent elements will be the same as they were for π‘₯ back in either [πœ‹ 𝐿 ] or [πœ‹ 𝐻 ]. Therefore, all cyclic pinnacles and vales in [πœ‹] are directly derived from those in [πœ‹ 𝐿 ] or [πœ‹ 𝐻 ]. This means that all 0’s will be vales, all elements of size 𝑛 + 1 will be cyclic pinnacles, and all other cyclic pinnacles will correspond to a cyclic pinnacle in either 𝐡 𝐿 or 𝐡 𝐻 . Therefore, [πœ‹] ∈ 𝑃(𝐡) 𝑖𝑗 . Since these maps are clearly inverses step by step, we have our bΔ³ection, and therefore our result. As an example of this process, consider 𝐡 = [00101001] where 𝐡1 = [001] and 𝐡2 = [01001]. Then we have that 𝑃 𝐡 = {3, 5, 8} while 𝑃 𝐡1 = {3} and 𝑃 𝐡2 = {2, 5} which correspond to the elements 5, 8 in 𝑃 𝐡 if you add |𝐡1 | = 3. We may then consider the permutation [πœ‹] = [∞0523081964097] ∈ 𝑐𝑃(𝐡)32 . If we write in boldface those elements of [πœ‹] that are in set 𝐿 defined in the proof, we have [πœ‹] = [∞0523081964097] and now it is easier to see that there are 4 alternations were we switch from an element of 𝐿 to one in 𝐻 and then back. Then we have [πœ‹ 𝐿 ] = [∞042304140] and [πœ‹ 𝐻 ] = [∞02050631064] which we get by standardizing [∞05080964097] 67 This recursion is very useful, as it allows us to give an efficient method for calculating 𝑝 𝑛 (𝑃) = |{πœ‹ ∈ 𝔖𝑛 | Pin πœ‹ = 𝑃}| using 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 4 ) arithmetic operations where π‘˜ = |𝑃|. It also allows us to derive results on the tree representation of pinnacles sets, which we do later. For a pinnacle set represented by block 𝐡, we will call 𝐡 a segregated block if it takes the form 𝐡 = [0π‘₯ , 1𝑦 ] in which we allow π‘₯ and 𝑦 to potentially be zero. That is to say, 𝐡 must consist of some number of 0’s followed by some number of 1’s with no other alternations. Our method to calculate 𝑝 𝑛 (𝑃) has two parts. First, we will present an efficient formula for calculating 𝑝(𝐡) 𝑖𝑗 where 𝐡 is a segregated block. We will then show that by using the recursion above, we may always write 𝑃( 𝐴) for any block 𝐴 in terms of these numbers, thereby giving a formula for the generic case. Lemma 3.5.2. Let 𝐡 = [0π‘₯ , 1𝑦 ] be a segregated block where π‘₯ + 𝑦 = 𝑛. Then if 𝑆(𝑛, π‘š) is the Stirling number of the second kind, we have 𝑗   𝑐!(𝑐 βˆ’ 1)! βˆ‘οΈ 1 𝑐 βˆ’ π‘š 𝑝(𝐡) 𝑖𝑗 =2 π‘₯+ π‘—βˆ’π‘ 𝑆(π‘₯, 𝑐 βˆ’ π‘š) 𝑖! π‘š=0 π‘š! 𝑗 βˆ’ π‘š where 𝑐 = 𝑖 + 𝑦 + 1 is the number of cyclic pinnacles. Proof. Given πœ‹ ∈ 𝑃(𝐡) 𝑖𝑗 , we may break πœ‹ down into a sequence of pinnacles in the set 𝑃 = 𝑃 𝐡 βˆͺ {(𝑛 + 1) 𝑖 } and a sequence of intermediate permutations, where each intermediate permutation is defined to be a maximal set of consecutive elements in πœ‹ consisting of no pinnacles. Furthermore, we know that the pinnacles must alternate with the intermediate permutations so that πœ‹ takes the form 𝐼1 𝑝′1 𝐼2 𝑝′2 Β· Β· Β· 𝐼 𝑦+𝑖 𝑝′𝑦+𝑖 𝐼𝑐 where πΌπ‘š are the intermediate permutations, 𝑃 = {𝑝′1 , . . . , 𝑝′𝑦+𝑖 }, and 𝑐 = 𝑖 + 𝑦 + 1 can be viewed as the number of cyclic pinnacles if we count ∞. Therefore, since every pinnacle is larger than every non-pinnacle, it will be the case that given any ordering of the pinnacles 𝑃 and any set of 𝑐 nonempty intermediate permutations, every ordering of those intermediate permutations, when interleaved with the pinnacle elements, will form a permutation in 𝑃(𝐡) 𝑖𝑗 . There are (𝑐 βˆ’ 1)!/𝑖! ways to order the pinnacle elements since 𝑖 of them are indistinguishable, and so to get our result it is enough to show that the number of ways of generating and ordering 𝑐 non-empty intermediate permutations is 68 𝑗   π‘₯+ π‘—βˆ’π‘ βˆ‘οΈ 1 π‘βˆ’π‘š 2 𝑐! 𝑆(π‘₯, 𝑐 βˆ’ π‘š) π‘š=0 π‘š! 𝑗 βˆ’ π‘š Note that since intermediate permutations cannot contain pinnacles, they must contain exactly one cyclic vale, which will always be the smallest element. Additionally, we must have that each intermediate set can contain at most one 0, since containing more would force one of the 0’s to not be a vale, which breaks the requirement of 𝑃(𝐡) 𝑖𝑗 . Therefore, we may partition all possible sets of intermediate permutations by the number of permutations π‘š that contain only the element 0. It then follows that each of the 𝑐 βˆ’ π‘š other intermediate permutations must contain at least one element of [π‘₯], and will therefore be distinguishable. So for a given π‘š the number of distinct orderings of a given set of intermediate permutations is 𝑐!/π‘š!, as specified in the formula. Now given an intermediate permutation, let its intermediate set be the corresponding set of elements in the permutation, which will have no repeats since we have already shown that the element 0 cannot appear twice. If an intermediate permutation has 𝑙 elements, then we may assign 𝑙 βˆ’ 1 of them a left or right label, corresponding to which side of the smallest element they appear. Alternatively, if we start from an intermediate set and give all elements except the smallest a left/right label, then there will be exactly one way to construct an intermediate permutation from it. Namely, all left labeled elements will form a decreasing string to the left of the smallest element, and all the right labeled elements an increasing string to the right. Therefore, counting intermediate permutations can be reduced to counting intermediate sets and multiplying by a power of 2. Since every collection of intermediate sets will have π‘₯ + 𝑗 elements total, and since all of them except the 𝑐 cyclic vales will be given a label, this power of 2 will be as stated in the above relation. Therefore, we have reduced to the case of counting the number of ways of partitioning the π‘₯ + 𝑖 non-pinnacles into 𝑐 non-empty intermediate sets such that no set contains more than one 0. This will force exactly 𝑗 of the intermediate sets to contain a 0, and so all that remains is to place the final π‘₯ elements in the set [π‘₯]. If we again fix π‘š to be the number of intermediate sets containing  only 0, there will be π‘βˆ’π‘š π‘—βˆ’π‘š 𝑆(π‘₯, 𝑐 βˆ’ π‘š) ways to create the remaining 𝑐 βˆ’ π‘š intermediate sets, namely, the number of ways of first partitioning the elements of [π‘₯] into 𝑐 βˆ’ π‘š non-empty sets, and then 69 choosing 𝑗 βˆ’ π‘š of those sets to contain the remaining 0’s. Since π‘š can be at most 𝑗, and since π‘š partitions all possible sets of intermediate sets, we may sum over π‘š to get the final part of our formula, which completes the proof. We can now prove our result. Theorem 3.5.3. The recursion in Theorem 3.5.1 together with the result in Lemma 3.5.2 is enough to compute 𝑝( 𝐴) for a general block 𝐴 of length 𝑛 corresponding to a (not necessarily admissible) set 𝑃. Furthermore, if |𝑃| = π‘˜ then this can be done using no more than 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 4 ) arithmetic operations. Proof. First we will show that the recursion and above lemma are enough to compute 𝑝( 𝐴) 𝑖𝑗 , which will then imply the result for 𝑝( 𝐴) = 𝑝( 𝐴)00 . Afterwards we will consider the run time. Suppose that 0π‘₯ is the maximal sequence of 0’s at the start of 𝐴, and that 1𝑦 is the maximal sequence of 1’s directly following it. Then we may write 𝐴 as the block concatenation 𝐡𝐴′ where 𝐡 = [0π‘₯ , 1𝑦 ] is a segregated block and 𝐴′ is the rest of block 𝐴. Note that 𝐴′ must either be empty, or have fewer 1’s in it than 𝐴 since 𝐡 will always take at least the first 1 that appears in 𝐴. If 𝐴′ is empty, then we have that 𝐴 started segregated and we are done by Lemma 3.5.2. If β€² not, then we may apply Theorem 3.5.1 to write 𝑝( 𝐴) 𝑖𝑗 in terms of 𝑝(𝐡) 𝑖𝑗 and 𝑝( 𝐴′) 𝑖𝑗 β€² , the former of which can be computed directly from Lemma 3.5.2 and the later of which can be further broken down using Theorem 3.5.1 again. Since we know that 𝐴′ must either be empty or have fewer 1’s than 𝐴, we will only have to repeat this recursion a finite number of times before 𝑝( 𝐴) 𝑖𝑗 is written entirely in terms of numbers that Lemma 3.5.2 can calculate, giving us our final answer. To prove the bound for the run time, suppose that at each step the block break down was 𝐴 = 𝐴0 = 𝐡1 𝐴1 , 𝐴1 = 𝐡2 𝐴2 , and so on until we have π΄π‘‘βˆ’1 = 𝐡 𝑑 𝐴𝑑 where 𝐴𝑑 is the first 𝐴𝑙 to be empty. Since each 𝐡𝑙 contains at least one 1, we have that 𝑑 is bounded by π‘˜, the number of pinnacles. It will be useful to find an upper bound on the different values for 𝑖 and 𝑗 that might appear in our calculations. Note that every time we apply the recursion to 𝑝( 𝐴𝑙 ) 𝑖𝑗 , we have that 𝑖 must be 70 zero. This is because 𝑖 = 0 initially when computing 𝑝( 𝐴)00 , and we only ever apply the recursion again on the second factor, which has the same 𝑖 as at the start. However, the first factor will take β€² the form 𝑝(𝐡𝑙+1 ) 𝑖𝑗 where 𝑖′ ranges over the values 0 to 𝑏 where 𝑏 is the number of 1’s in 𝐴𝑙+1 . Therefore in the worst case, 𝑖′ may reach a maximum of π‘˜ βˆ’ 1 when using Lemma 3.5.2 to compute β€² 𝑝(𝐡1 ) 𝑖𝑗 and so in all cases will be bounded by π‘˜. Now suppose that we apply our recursion to 𝑝( 𝐴𝑙 ) 𝑖𝑗 and let 𝑗 β€² be the maximum value of 𝑗 that can arise on any factor of the form 𝐴𝑙+1 in the sum. We have that 𝑗 β€² is at most max{ 𝑗, 𝑏 + 1} where 𝑏 + 1 is maximized on the first step when 𝑏 is the number of 1’s in 𝐴𝑙+1 , which is at most π‘˜ βˆ’ 1. Since 𝑗 starts out at zero, and the value of 𝑏 falls each step, we have that the maximum value that 𝑗 can be is π‘˜. We now wish to find the total run time of using Lemma 3.5.2 to calculate all the 𝑝(𝐡𝑙 ) 𝑖𝑗 . First, let 𝑛𝑙 be the number of 0’s in block 𝐡𝑙 and note that each 𝑛𝑙 is clearly bounded by 𝑛, which is the original length of 𝐴. Then note that the quantity 𝑐 βˆ’ π‘š = 𝑦 + 𝑖 + 1 βˆ’ π‘š in Lemma 3.5.2 can be at most π‘˜ + 1 since 𝑦 is the number of 1’s in the block 𝐡𝑙 while 𝑖 can be at most the number of ones in the block 𝐴𝑙 , which totals to no more than π‘˜. Therefore, we only have to calculate Stirling numbers of the form 𝑆(𝑛𝑙 , π‘˜ β€²) where 𝑙 is bounded by π‘˜ and π‘˜ β€² is bounded by π‘˜ + 1. Using the formula π‘˜β€²  β€² β€² 1 βˆ‘οΈ π‘˜ β€² βˆ’π‘‘ π‘˜ 𝑆(𝑛𝑙 , π‘˜ ) = β€² (βˆ’1) 𝑑 𝑛𝑙 π‘˜ ! 𝑑=0 𝑑 we may first calculate all powers 𝑑 𝑛𝑙 where 𝑑 ∈ [π‘˜ + 1] and 𝑙 ∈ [π‘˜] using fast exponentiation in at most 𝑂 (π‘˜ 2 log 𝑛) arithmetic operations. We may then calculate all binomial expressions of β€² the form π‘˜π‘‘ with π‘˜ β€² ≀ π‘˜ + 1 and 𝑑 ≀ π‘˜ β€² in 𝑂 (π‘˜ 3 ) operations and store those too. From this information, we may calculate all Stirling numbers that will be needed in 𝑂 (π‘˜ 3 ) additional time since the number of distinct 𝑛𝑙 , π‘˜ β€² values are bounded by π‘˜ + 1. Furthermore, all other factorial and binomial expressions used in Lemma 3.5.2, along with the power of 2, can be calculated and stored at this point in no more than 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 3 ) time. Therefore, if we do this preparation first, we may calculate each 𝑝(𝐡𝑙 ) 𝑖𝑗 in 𝑂 (π‘˜) time from the stored data. Since 𝑖, 𝑗, and 𝑙 are each bounded by π‘˜, there will be at most 𝑂 (π‘˜ 3 ) distinct such terms, we have that a look up table for all the 𝑝(𝐡𝑙 ) 𝑖𝑗 can be generated in no more than 𝑂 (π‘˜ 4 ) time. 71 Given this look up table, we may then compute and store the 𝑝( 𝐴𝑙 ) 0𝑗 in 𝑂 (π‘˜) algebraic operations each by starting with π΄π‘šβˆ’1 and then accessing all the 𝑝(𝐡𝑙 ) 𝑖𝑗 and previously computed 𝑝( 𝐴𝑙 ) 𝑖𝑗 to compute the next π΄π‘™βˆ’1 . Since 𝑙 and 𝑗 are bounded by π‘˜, we have that this part of the algorithm takes at most 𝑂 (π‘˜ 3 ) operations to get to 𝑝( 𝐴0 )00 , which is our final answer. Therefore, the total run time is 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 3 ) to prepare for Lemma 3.5.2, plus 𝑂 (π‘˜ 4 ) to create a look up table of the values in 𝑝(𝐡 π‘˜ ) 𝑖𝑗 , plus a final 𝑂 (π‘˜ 3 ) to use the recursion. Altogether, this results in a final run time of 𝑂 (π‘˜ 2 log 𝑛 + π‘˜ 4 ) as advertised. Before concluding, we present one more application of our recursion where we prove a version of a formula conjectured by Falque, Novelli, and Thibon in [10]. In their paper, the authors note that there is a map between admissible pinnacle sets in [𝑛] and forests of complete binary trees on 𝑛 vertices arranged as a sequence of trees from left to right, and such that the trees are labeled from left to right with nodes labeled in left suffix order. The map is given by the following algorithm. 1. Given some admissible pinnacle set 𝑃 = {𝑝 1 < 𝑝 2 < . . . < 𝑝 π‘˜ } βŠ‚ [𝑛], start with the forest consisting of a single unlabeled node. Let 𝑖 = 𝑛. 2. Label the rightmost unlabeled node 𝑖. If 𝑖 ∈ 𝑃, give this node two unlabeled children. Otherwise, create a new tree with one unlabeled node to the left of all existing trees. Let 𝑖 = 𝑖 βˆ’ 1. 3. Repeat the previous step until a node has been given the label 1, and then stop. To reverse this map, we start with any complete binary forest with trees arranged in a sequence from left to right and with nodes labeled as specified above. We then simply let 𝑃 be the set of labels of internal nodes. An example can be seen in Figure 3.4. It is not hard to show that these maps are well defined and that they are inverses of each other. In what follows, we will use the letter 𝐹 for forests, and 𝑇 for single trees. We may then write an admissible pinnacle set as a tree sequence (𝑇1 , 𝑇2 , . . . π‘‡π‘Ÿ ). If a tree has only one vertex, denote it as 72 1 6 7 4 5 2 3 Figure 3.4 The complete binary forest corresponding to pinnacle set 𝑃 = {4, 6} for 𝑛 = 7 𝑂. We can also group consecutive trees together as an ordered forest; for instance, we may wish to say (𝑇1 , 𝑇2 , 𝑇3 , 𝑇4 ) = (𝐹1 , 𝐹2 ) where 𝐹1 = (𝑇1 ) and 𝐹2 = (𝑇2 , 𝑇3 , 𝑇4 ). Using this notion of trees, we may use the notation 𝑝(𝐹) to denote the number of permutations in 𝔖𝑛 having pinnacle set represented by (𝐹). It was conjectured in [10] that for pinnacle set 𝐹 = (𝑂, 𝑇2 , 𝑇3 , . . . , π‘‡π‘Ÿ ) we have the relation 𝑝(𝐹) = 𝑝(𝑂, 𝑇2 )𝑃(𝑂, 𝑂, 𝑇3 , . . . , π‘‡π‘Ÿ ). Unfortunately, this is not true as can be seen by the counterexample when 𝑛 = 4 and the pinnacles set is {4}. However, a very similar result can be proved. Theorem 3.5.4. For a sequence of trees 𝐹 = (𝑂, 𝑇2 , 𝑇3 , . . . , π‘‡π‘Ÿ ) encoding a pinnacle set, we have 1 𝑝(𝐹) = 𝑝(𝑂, 𝑇2 ) 𝑝(𝑂, 𝑂, 𝑇3 , . . . , π‘‡π‘Ÿ ). 2 Proof. Since the trees 𝐹 are labeled from left to right, we have that all nodes in (𝑂, 𝑇2 ) will be smaller than all nodes in the rest of 𝐹. Therefore, we may consider a block composition 𝐡1 𝐡2 corresponding to this pinnacle set where 𝐡1 corresponds only to the labels of the nodes in (𝑂, 𝑇2 ) while 𝐡2 has the rest. Then by our notation, we will have that 𝑝(𝐡1 ) = 𝑝(𝑂, 𝑇2 ) and 𝑝(𝐡2 ) = 𝑝(𝑇3 , . . . , π‘‡π‘Ÿ ). We then have by Theorem 3.5.1 that βˆ‘οΈπ‘ 𝑝(𝐹) = 𝑝(𝐡1 𝐡2 ) = 𝑝(𝐡1 ) π‘š 𝑝(𝐡2 )π‘š+1 . π‘š=0 Now note that if π‘š > 1 we will have that 𝑝(𝐡1 ) π‘š = 0 since there will be too many pinnacles for the non-pinnacles to separate, and so this sum simplifies to 𝑝(𝐹) = 𝑝(𝐡1 ) 𝑝(𝐡2 )1 + 𝑝(𝐡1 ) 1 𝑝(𝐡2 )2 73 First, note that 𝑝(𝐡1 ) = 𝑝(𝐡1 ) 1 since there is a simple bΔ³ection between the permutations they count. Namely, for any πœ‹ counted by 𝑝(𝐡1 ) there will always exist exactly one index where two non-pinnacles are adjacent and where we may insert a new largest element to get a permutation counted by 𝑝(𝐡1 ) 1 . Similarly, we my reverse this bΔ³ection by deleting the largest element from some πœ‹β€² counted by 𝑝(𝐡1 ) 1 . This will not create any new pinnacles because all non-pinnacles will still be adjacent to either the end of the permutation or to one of the other pinnacles. We now consider a block 𝐡3 corresponding to (𝑂, 𝑂, 𝑇3 , . . . , π‘‡π‘Ÿ ), which will be 𝐡2 with two zeros appended to the beginning. We claim that 𝑝(𝐡3 ) = 2𝑠 where 𝑠 = 𝑝(𝐡2 )1 + 𝑝(𝐡2 )2 . To see this, note that every permutation counted by 𝑝(𝐡3 ) will either have the 1 and 2 adjacent, or separate. If they are adjacent, replace both by a single 0 and subtract 2 from all other elements. This will not destroy any pinnacles since neither 1 nor 2 were originally pinnacles, and so the result will be a permutation counted by 𝑝(𝐡2 )1 . Since this map is clearly reversible up to the ordering of 1 and 2, we also see that this is a two-to-one mapping. On the other hand, suppose that 1 and 2 are not adjacent. Then it is easy to see, by reasons similar to above, that if we replace both 1 and 2 by separate 0β€² 𝑠 and then subtract 2 from all other elements we will end up with a permutation counted by 𝑝(𝐡2 )2 . This will again be a two-to-one mapping and so we have that 𝑝(𝐡3 ) = 2𝑠. Therefore, we have 1 𝑝(𝐹) = 𝑝(𝐡1 𝐡2 ) = 𝑝(𝐡1 ) 𝑝(𝐡2 )1 + 𝑝(𝐡1 ) 1 𝑝(𝐡2 )2 = 𝑝(𝐡1 ) ( 𝑝(𝐡2 )1 + 𝑝(𝐡2 )2 ) = 𝑝(𝐡1 ) 𝑝(𝐡3 ) 2 the last of which is equal to 21 𝑝(𝑂, 𝑇2 ) 𝑝(𝑂, 𝑂, 𝑇3 , . . . , π‘‡π‘Ÿ ) as desired. 74 BIBLIOGRAPHY [1] Ron M. Adin, Ira M. Gessel, Victor Reiner, and Yuval Roichman. Cyclic quasi-symmetric functions. SΓ©m. Lothar. Combin., 82B:Art. 67, 12, 2020. [2] Duff Baker-Jarvis and Bruce E. Sagan. BΔ³ective proofs of shuffle compatibility results. Adv. in Appl. Math., 113:101973, 29, 2020. [3] Sara Billey, Krzysztof Burdzy, and Bruce E. Sagan. Permutations with given peak set. J. Integer Seq., 16(6):Article 13.6.1, 18, 2013. [4] David Callan. Pattern avoidance in circular permutations, 2002. Preprint arXiv:0210014v1. [5] Robert Davis, Sarah A. Nelson, T. Kyle Petersen, and Bridget E. Tenner. The pinnacle set of a permutation. Discrete Math., 341(11):3249–3270, 2018. [6] Alexander Diaz-Lopez, Pamela E. Harris, Isabella Huang, Erik Insko, and Lars Nilsen. A formula for enumerating permutations with a fixed pinnacle set. Discrete Math., 344(6):Paper No. 112375, 15, 2021. [7] Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce E. Sagan, Jamie Schmidt, and Alexander Sietsema. Cyclic shuffle compatibility. SΓ©m. Lothar. Combin., 85:Art. B85d, 11, [2020–2021]. [8] Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce E. Sagan, Jamie Schmidt, and Alexander Sietsema. Cyclic pattern containment and avoidance. Adv. in Appl. Math., 135:Pa- per No. 102320, 28 pp., 2022. [9] Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce E. Sagan, Jamie Schmidt, and Alexander Sietsema. Pinnacle set properties. Discrete Math., 345(7):Paper No. 112882, 16 pp., 2022. [10] Justine Falque, Jean-Christophe Novelli, and Jean-Yves Thibon. Pinnacle sets revisited, 2021. Preprint arXiv:2106.05248. [11] Wenjie Fang. Efficient recurrence for the enumeration of permutations with fixed pinnacle set. Discrete Math. Theor. Comput. Sci., 24(1):Paper No. 8, 18 pp., 2022. [12] Ira M. Gessel and Yan Zhuang. Shuffle-compatible permutation statistics. Adv. Math., 332:85–141, 2018. [13] Daniel Gray, Charles Lanning, and Hua Wang. Pattern containment in circular permutations. Integers, 18B:Paper No. A4, 13, 2018. [14] Daniel Gray, Charles Lanning, and Hua Wang. Patterns in colored circular permutations. 75 Involve, 12(1):157–169, 2019. [15] DarΔ³ Grinberg. Shuffle-compatible permutation statistics II: the exterior peak set. Electron. J. Combin., 25(4):Paper No. 4.17, 61, 2018. [16] Kathy Ji and Dax T. X. Zhang. A cyclic analogue of stanley’s shuffling theorem. Electron. J. Combin., 29(4):Paper No. 4.20–, 2022. [17] Jinting Liang, Bruce E. Sagan, and Yan Zhuang. Cyclic shuffle-compatibility via cyclic shuffle algebras, 2022. Preprint arXiv:2212.14522. [18] Kurt Luoto, Stefan Mykytiuk, and Stephanie van Willigenburg. An introduction to quasisym- metric Schur functions. SpringerBriefs in Mathematics. Springer, New York, 2013. Hopf algebras, quasisymmetric functions, and Young composition tableaux. [19] Quinn Minnich. Further results on pinnacle sets, 2021. Preprint arXiv:2111.08075. [20] Ezgi KantarcΔ± Oğuz. A counter example to the shuffle compatibility conjecture. Preprint arXiv:1807.01398, 2018. [21] Irena Rusu. Sorting permutations with fixed pinnacle set. Electron. J. Combin., 27(3):Paper No. 3.23, 22, 2020. [22] Irena Rusu and Bridget Eileen Tenner. Admissible pinnacle orderings. Graphs Combin., 37(4):1205–1214, 2021. [23] Bruce E. Sagan. Combinatorics: The art of counting, volume 210 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, [2020] Β©2020. [24] Richard P. Stanley. Ordered structures and partitions. American Mathematical Society, Providence, R.I., 1972. Memoirs of the American Mathematical Society, No. 119. [25] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. [26] Volker Strehl. Enumeration of alternating permutations according to peak sets. J. Combina- torial Theory Ser. A, 24(2):238–240, 1978. 76