Counting alternating permutations with restricted prefix and suffix
Ran Pan, Jeffrey Remmel · 2025
Read Counting alternating permutations with restricted prefix and suffix by Ran Pan, Jeffrey Remmel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10727.txt.
Introduction
Ran Pan and Jeffrey Remmel counted a special class of number orders in 2025. An alternating order rises and falls in turn, like a wave, across its whole run. The authors fix rules on how such an order may start and end. Starts and ends of length three and four are held to set shapes, or to gaps of a set size between the first values.
They work with tree-like charts and with formulas that pack a whole count family into one expression. Each rule set gets its own count. They also count orders where both the start and the end are held at once. The paper adds exact counts to a classic corner of combinatorics, the study of how patterns can be arranged.
Catalog record
| CREATOR | Ran Pan, Jeffrey Remmel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10727
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counting alternating permutations with restricted prefix and suffix Ran Pan, Jeffrey Remmel Abstract In this paper, we use Hasse diagrams and generating functions to count alternating permutations with restricted prefix and suffix of lengths 3 and 4. In other words, for an alternating permutation σ = σ 1 σ 2 σ 3 ⋯ σ n ∈ S n \sigma=\sigma_{1}\sigma_{2}\sigma_{3}\cdots\sigma_{n}\in S_{n} , we restrict length-3 prefixes σ 1 σ 2 σ 3 \sigma_{1}\sigma_{2}\sigma_{3} to follow certain patterns, such as 231 231 and 132 132 , or follow certain restrictions such as σ 2 ≥ max { σ 1 , σ 3 } + 2 \sigma_{2}\geq\max\{\sigma_{1},\sigma_{3}\}+2 , similarly for prefixes of length 4. We also study the enumeration of alternating permutations with restrictions on both prefix and suffix. 1 Introduction A permutation of length n is a rearrangement of \{1,2,3,\cdots,n\} . The set of all the permutations of length n is denoted by S_{n} and clearly, S_{n}=n! . It’s well-known in combinatorics that a permutation \sigma=\sigma_{1}\sigma_{2}\sigma_{3}\cdots\sigma_{n}\in S_{n} is called alternating if \sigma_{1}<\sigma_{2}>\sigma_{3}<\sigma_{4}>\sigma_{5}<\cdots . They are also called up-down permutations. We denote the set of all the alternating permutations in S_{n} by A_{n} . Désiré André showed that Euler numbers count the number of such permutations ( [ 1 ] ), i.e., |A_{n}|=E_{n} , where E_{n} is the n -th Euler number. E_{n} has exponential generating function f as follows f(x)=\sum_{n\geq 0}\frac{E_{n}}{n!}x^{n}=1+\frac{1}{1!}x+\frac{1}{2!}x^{2}+\frac{2}{3!}x^{3}+\frac{5}{4!}x^{4}+\frac{16}{5!}x^{5}+\cdots=\sec(x)+\tan(x). To better understand alternating permutations, we can use Hasse diagram to illustrate them, which is shown in Figure 1 . Figure 1: A_{5} and A_{6} Entringer studied the enumeration of alternating permutation starting with a given value [ 3 ] . In this paper, we focus on enumeration of alternating permutations with prefix or suffix that is restricted to some certain pattern. We say a prefix or suffix has pattern P if the prefix or the suffix is order-isomorphic to P . For example, there is a pattern P=1324\in A_{4} and a permutation \sigma=24361857 . The first four elements of \sigma are 2436 which is order-isomorphic to 1324 . So we say \sigma has P as the prefix. For \sigma\in S_{n} , the complement of \sigma is defined as \sigma^{c}=(n+1-\sigma_{n},n+1-\sigma_{n-1},\cdots,n+1-\sigma_{2},n+1-\sigma_{1}) . For example, if \sigma=251634 , then \sigma^{c}=341625 . It it easy to see that for any pattern P\in A_{2k} , the number of permutations in A_{2n} having P as prefix is equal to the number of permutations having P^{c} as suffix. So we will not discuss prefix and suffix separately. This paper is mainly motivated by Remmel’s [ 4 ] and Bóna’s [ 2 ] . Remmel studied pattern matching in alternating permutations and the theory in [ 4 ] could be extended to any minimal overlapping patterns in A_{2n} and in [ 2 ] Bóna gave results of number of minimal overlapping permutations. Part of this paper is preliminary results for a forthcoming paper about number of minimal overlapping permutations in some special families. In Section 2, we give formulas and generating functions of the number of alternating permutations with some given restricted prefix of length 3. In Section 3, we study prefixes of length 4. In Section 4, we study alternating permutations satisfying given prefix and suffix at the same time. The method is based on inclusion-exclusion using Hasse diagrams and generating functions. We only consider prefix and suffix of length 3 and 4 and one could easily expand the discussion for longer prefix or suffix. 2 Prefix of length 3 In this section, the discussion is focused on enumeration of alternating permutations with prefix of length 3 , that is, for any \sigma=\sigma_{1}\sigma_{2}\sigma_{3}\sigma_{4}\cdots\sigma_{n+3}\in A_{n+3} , we only take \sigma_{1}\sigma_{2}\sigma_{3} into consideration. Prefixes that are discussed in this section include \{\sigma_{1}>\sigma_{3}\} , \{\sigma_{1}>\sigma_{3}+1\} , \{\sigma_{3}>\sigma_{1}\} , \{\sigma_{3}>\sigma_{1}+1\} , \{\sigma_{2}>\max\{\sigma_{1},\sigma_{3}\}+1\} . 2.1 Pattern 231 as prefix Suppose \sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{n+3} is a permutation in A_{n+3} having pattern 231 as prefix, then \sigma_{3}<\sigma_{1}<\sigma_{2} . Then we have the corresponding Hasse diagram as Figure 2 (even-length case). We denote the set of all such alternating permutations of length n+3 by A^{231}(n+3) and clearly |A^{{231}}(n+3)| is the number of linear extensions of corresponding Hasse diagram. Figure 2: alternating permutations with pattern 231 as prefix (even-length case) We take A^{231}(8) as an example and use Hasse diagrams (Figure 7 ) to show how inclusion-exclusion principle works here. Note that we need to be careful about choosing an appropriate edge and then apply inclusion-exclusion to it. Figure 3: formula for A^{231}(8) By Figure 3 , since up-down permutations are essentially the same as down-up permutations, we have following formula \left|A^{231}(8)\right|=\binom{8}{1}E_{7}-E_{8}, where E_{n} is the n -th Euler number. For an arbitrary n , we have general formula \left|A^{231}(n+3)\right|=\binom{n+3}{1}E_{n+2}-E_{n+3}. Since E_{n} has exponential generating function f(x)=\sec x+\tan x , the exponential generating function f^{231} of A^{{231}}(n) for n\geq 3 is f^{231}(x)=xf(x)-f(x)=(x-1)(\sec x+\tan x). A few initial terms of |A^{231}(n)| for n\geq 3 are 1 , 3 , 9 , 35 , 155 , 791 , 4529 , 28839 , 201939 , \cdots . In fact, observing Figure 2 , we find f^{231}(x) is also the exponential generating function of up-up-down-up-down-up-down \cdots permutations, which gives Sequence A034428 on OEIS [ 5 ] a new interpretation. Since pattern 231 means \sigma_{1}>\sigma_{3} , a natural question could be how many alternating permutations satisfying \sigma_{1}-\sigma_{3}\geq 2 . It is not hard to see that number of alternating permutations of length n satisfying \sigma_{1}-\sigma_{2}=1 is E_{n-1} . Therefore, for n\geq 3 \left|A^{\sigma_{1}-\sigma_{3}\geq 2}(n)\right|=|A^{231}(n)|-E_{n-1} and the corresponding exponential generating function is \displaystyle f^{\sigma_{1}-\sigma_{3}\geq 2}(x) \displaystyle= \displaystyle f^{231}(x)-\int_{0}^{x}f(t)dt \displaystyle= \displaystyle(x-1)(\sec x+\tan x)+\log(1-\sin x) A few initial terms of \left|A^{\sigma_{1}-\sigma_{3}\geq 2}(n)\right| for n\geq 3 are 0 , 1 , 4 , 19 , 94 , 519 , 3144 , 20903 , 151418 , 1188947 , \cdots . 2.2 Pattern 132 as prefix Suppose \sigma=\sigma_{1}\sigma_{2}\cdots\sigma_{n+3} is a permutation in A_{n+3} having pattern 132 as prefix, then \sigma_{1}<\sigma_{3}<\sigma_{2} . Then we have the corresponding Hasse diagram as Figure 4 (even-length case). We denote the set of all such alternating permutations of length n+3 by A^{132}(n+3) and clearly |A^{{132}}(n+3)| is the number of linear extensions of corresponding Hasse diagram. Figure 4: alternating permutations with pattern 132 as prefix (even-length case) We take A^{132}(8) as an example and use Hasse diagrams (Figure 5 ) to show how inclusion-exclusion principle works here. Note that we need to be careful about choosing an appropriate edge and then apply inclusion-exclusion to it. Figure 5: formula for A^{132}(8) We have two ways to put the square node in the left tail and then the new diagram we obtain is the diagram corresponding to A^{231}(8) . Hence, we have \left|A^{132}(8)\right|=\binom{8}{1}E_{7}-2\left|A^{231}(8)\right|, For an arbitrary n , we have general formula \left|A^{132}(n+3)\right|=\binom{n+3}{1}E_{n+2}-2\left|A^{231}(n+3)\right|. Then the exponential generating function f^{132} of A^{{132}}(n) for n\geq 3 is \displaystyle f^{132}(x) \displaystyle= \displaystyle xf(x)-2f^{231}(x) \displaystyle= \displaystyle(x-2(x-1))(\sec x+\tan x) \displaystyle= \displaystyle(2-x)(\sec x+\tan x). A few initial terms of |A^{132}(n)| for n\geq 3 are 1 , 2 , 7 , 26 , 117 , 594 , 3407 , 21682 , \cdots . Actually, since |A_{n}|=|A^{132}(n)|+|A^{231}(n)| for n\geq 3 , there is an easier approach to get f^{132}(x) \displaystyle f^{132}(x) \displaystyle= \displaystyle f(x)-f^{231}(x) \displaystyle= \displaystyle\left(\sec x+\tan x\right)-(x-1)\left(\sec x+\tan x\right) \displaystyle= \displaystyle(2-x)(\sec x+\tan x). Similar to Section 2.2, we also consider number