A Combinatorial Interpretation of the Eigensequence for Composition

David Callan Department of Statistics University of Wisconsin-Madison 1300 University Ave. Madison, WI 53706-1532 USA

                     callan@stat.wisc.edu

Abstract

The monic sequence that shifts left under convolution with itself is the Catalan numbers with 130+ combinatorial interpretations. Here we establish a combinatorial interpretation for the monic sequence that shifts left under composition: it counts permutations that contain a 3241 pattern only as part of a 35241 pattern. We give two recurrences, the first allowing relatively fast computation, the second similar to one for the Catalan numbers. Among the 4 × 4! = 96 similarly restricted patterns involving 4 letters (such as 4\underline{2}31: a 431 pattern occurs only as part of a 4231), four different counting sequences arise: 64 give the Catalan numbers, 16 give the Bell numbers, 12 give sequence A051295 in OEIS, and 4 give a new sequence with an explicit formula.

1 Introduction

The composition of two sequences (a_{n})_{n≥1} and (b_{n})_{n≥1} is (c_{n})_{n≥1} defined by C(x) = A(B(x)) where A, B, C are the respective generating functions, A(x) = ∑_{n≥1} a_{n}x^{n} and so on. A sequence is monic if its first term is 1. There is a unique monic sequence (b_{n})_{n≥1} whose composition with itself is equal to its left shift, (b_{2}, b_{3}, …). This sequence (b_{n})_{n≥1} begins 1, 1, 2, 6, 23, 104, 531, … and is called the (monic) eigensequence for composition [1] .

Consider a permutation on a set of positive integers as a list (or word of distinct letters). A subpermutation is a subword (letters in same order but not not necessarily contiguous). Thus 253 is a subpermutation of 21534. A factor is a subpermutation in which the letters are contiguous. A standard permutation is one on an initial segment of the positive integers. The reduced form of a permutation π on an arbitrary set of positive integers, denoted reduce(π), is the standard permutation obtained by replacing its smallest entry by 1, next smallest by 2, and so on. Thus reduce(352) = 231. The length |π| of a permutation π is simply the number of letters in it. Given a permutation π and a standard permutation ρ of weakly smaller length—a “pattern”—a subpermutation of π whose reduced form is ρ is said to be an instance of the pattern ρ in π. Thus 352 forms a 231 pattern in 35124. A 321-avoiding permutation, for example, is one containing no instance of a 321 pattern. The number of 321-avoiding permutations is the Catalan number C_{n} [2].

Let A_{n} denote the set of permutations on [n] in which the pattern 3241 occurs only as part of a 35241 pattern (3\underline{5}241OK permutations for short). This curious pattern restriction arises in connection with 2-stack-sortable permutations, which can be characterized as permutations that are both 3\underline{5}241OK and 2341-avoiding [3]. With a_{n} = |A_{n}|, the first several terms of (a_{n})_{n≥0} coincide with those of (b_{n})_{n≥1} above. This suggests that a_{n} = b_{n+1} and the main objective of this paper is to prove bijectively that this is so (§3 and §4). In §2, we consider the structure of a 3\underline{5}241OK permutation and deduce two recurrences for a_{n}. A bonus section (§5) classifies all similarly restricted patterns involving 3 or 4 letters by their counting sequences.

2 Structure and Recurrences for 3\underline{5}241OK Permutations

Every permutation π on [n] has the form π = m_{1}L_{1}m_{2}L_{2} … m_{r}L_{r} where m_{1} < m_{2} < … < m_{r} = n are the left-to-right maxima (LRmax for short) of π. With this notation, the following characterization of 3\underline{5}241OK permutations is easy to verify.

Theorem 1. A permutation π on [n] is 3\underline{5}241OK if and only if ( i ) L_{1} < L_{2} < … < L_{r} in the sense that u ∈ L_{i}, v ∈ L_{j} with i < j implies u < v, and (ii ) each L_{i} is 3\underline{5}241OK.

Recall A_{n} is the set of all 3\underline{5}241OK permutations on [n]. Let A_{n,k} denote the set of permutations in A_{n} whose first entry is k, and let C_{n} the denote the set of permutations in A_{n} whose first two entries are in increasing order (n ≥ 2, C_{1} := A_{1} = {(1)}). Set a_{n} = |A_{n}|, a_{n,k} = |A_{n,k}|, c_{n} = |C_{n}|.

Theorem 2. a_{n} is given by the recurrence relations a_{0} = c_{1} = 1 and

(i )  a_{n} = ∑_{i=0}^{n−1} a_{i}c_{n−i}  n ≥ 1
(ii )  c_{n} = ∑_{i=0}^{n−1} ia_{n−1,i}  n ≥ 2

(iii ) a_{n,k} = \begin{cases}∑_{i=0}^{k−1} a_{i} ∑_{j=k−i}^{n−1−i} a_{n−1−i,j} & 1 ≤ k ≤ n − 1 \\ a_{n−1} & k = n \end{cases}

Proof (i) counts A_{n} by i = |L_{1}| since m_{1}L_{1}K ⟶ (reduce(L_{1}), reduce(m_{1}K)) is a bijection to A_{i} × C_{n−i}. (ii) counts C_{n} by second entry, say i + 1, because L_{1} = ∅ and, with m_{2} = i + 1, m_{1}m_{2}L_{2} … m_{r}L_{r} ⟶ (m_{1}, reduce(m_{2}L_{2} … m_{r}L_{r})) is a bijection to [i] × A_{n−1,i}.

(iii) counts A_{n,k} (1 ≤ k ≤ n − 1) by i = |L_{1}| and j = first entry of reduce(m_{2}L_{2} …) since j ≥ k − i, m_{1} = k and m_{1}L_{1}m_{2}L_{2} … ⟶ (L_{1}, reduce(m_{2}L_{2} …)) is a bijection to A_{i} × A_{n−1−i,j}.

There is a more elegant (but less computationally efficient) recurrence involving a sum over compositions. Recall that a composition c of n is a list c = (c_{1}, c_{2}, …, c_{r}) of positive integers whose sum is n and if c = (c_{i})_{i=1}^{r} and d = (d_{i})_{i=1}^{r} are same-length compositions of n, then d dominates c (d ⪰ c) if d_{1} + … + d_{i} ≥ c_{1} + … + c_{i} for i = 1, 2, …, r − 1 (of course, equality holds for i = r). Let C_{n} denote the set of all compositions of n (there are 2^{n−1} of them). A permutation π = m_{1}L_{1}m_{2}L_{2} … m_{r}L_{r} (recall the m_{i} are the LRmax entries) determines two same-length compositions of [n]: c = (c_{i})_{i=1}^{r} with c_{i} = |m_{i}L_{i}| = 1 + |L_{i}| and d = (d_{i})_{i=1}^{r} with d_{i} = m_{i} − m_{i−1} (m_{0} := 0) and necessarily d ⪰ c (or else a left-to-right max would occur among the L_{i}). Summing over c, Theorem 1 yields

Theorem 3.

a_{n} = ∑_{c∈C_{n}} |{d ∈ C_{n} : d ⪰ c}| a_{c_{1}−1}a_{c_{2}−1} ⋯ a_{c_{r}−1} n ≥ 1

Omitting the first factor in the summand, the recurrence

a_{0} = 1, a_{n} = ∑_{c∈C_{n}} a_{c_{1}−1}a_{c_{2}−1} ⋯ a_{c_{r}−1} n ≥ 1

is well known to generate the Catalan numbers. For example, it counts Dyck paths by the locations of their returns to ground level. Since the permutations for which c = d are precisely those which avoid the pattern 231, another byproduct is that the Catalan numbers count 231-avoiding permutations.

3 Preparing for the Main Bijection

The generating function B(x) = ∑_{n≥1} b_{n}x^{n} for the “shifts left under composition” sequence of §1 is characterized by B(B(x)) = \frac{B(x)}{x} − 1. If (b_{n}) is the counting sequence for some species, say B-structures, then [x^{n}]B(B(x)) is the number of pairs (X, Y) where X is a Bstructure of unspecified size k, 1 ≤ k ≤ n and Y is a k-list of B-structures of total size n (a k-list is simply a list with k entries). On the other hand, [x^{n}](\frac{B(x)}{x} − 1) = b_{n+1}. Hence, to show that b_{n+1} = a_{n}, our main objective, we need a bijection from the set A_{n} of 3\underline{5}241OK permutations on [n] to pairs (ρ, v) where ρ ∈ A_{k−1} for some 1 ≤ k ≤ n and v is a k-list of 3\underline{5}241OK permutations (possibly empty) of total length n − k.

Indeed, given π ∈ A_{n}, the position of n in π determines k and the right factor of π starting at n determines ρ as follows (it is the extraction of v that will really make us work). It is convenient to define the LIT (longest increasing terminal) entries of a permutation π on [n] to be k, k + 1, …, n where k is the smallest integer such that k, k + 1, …, n appear in that order in π. Note that the LIT entries form a terminal segment of the LRmax entries. For example, the LIT entries are double underlined and the remaining LRmax entries are single underlined in \underline{2} 1 \underline{4} \underline{\underline{7}} 6 5 \underline{\underline{8}} \underline{\underline{9}} 3. The LIT entries of a permutation on an arbitrary set of positive integers are defined analogously. Now decompose π as σnτ.

Theorem 4. A permutation σnτ on [n] is 3\underline{5}241OK if and only if σ, τ are both 3\underline{5}241OK and each entry of σ that exceeds the smallest entry of τ is an LIT entry of σ.

Proof (⇒) Suppose b ∈ σ exceeds c ∈ τ yet b is not an LIT entry of σ. Then either (i) there exists a ∈ σ preceding b with a > b, and abnc is an offending 3241 pattern, or (ii) there exist u, v following b in σ with u > v > b and this time uvnc is an offending 3241.

(⇐) routine. Set k = |nτ|, the length of the right factor of π starting at n, and set ρ = reduce(τ) ∈

A_{k−1}, capturing the underlying permutation of τ. The support of τ can be captured by placing, for each c ∈ support(τ), an asterisk (or star) right before the smallest entry of σ that exceeds c (necessarily an LIT entry in view of Theorem 4) or after max(σ) if there is no such entry. No information is lost if σ is then reduced (keeping the stars in place) to produce σ^{∗} say, because only the LIT entries of σ will be affected and the stars determine both the original LIT entries of σ and the support of τ. For example, π = (2, 8, 3, 1, 11, 4, 6, 5, 13, 7, 15, 9, 10, 14, 12) ∈ A_{15} gives k = 5, τ = (9, 10, 14, 12) and yields the pair ρ = (1, 2, 4, 3), σ^{∗} = (2, 8, 3, 1, ∗, ∗, 9, 4, 6, 5, ∗, 10, ∗, 7), and π can be recovered from ρ and σ^{∗}. The length of σ^{∗} (disregarding the stars) coincides with the total length n − k of the desired list of 3\underline{5}241OK permutations. This reduces the problem to giving a bijection from 3\underline{5}241OK permutations on [n] with k − 1 stars distributed arbitrarily, just before LIT entries or just after the maximum entry n, to k-lists of (possibly empty) 3\underline{5}241OK permutations of total length n.

Let X_{n,k} denote the subset of the preceding “starred” permutations on [n] with (i) no stars immediately following or preceding the max n, and (ii) at most one star preceding each non-max LIT entry. In other words, X_{n,k} is the set of 3\underline{5}241OK permutations on [n] with k − 1 distinct LIT entries other than n preceded (or marked) by a star. We now show that the following result suffices to construct the desired bijection.

Theorem 5. With X_{n,k} as just defined, there is a bijection from X_{n,k} to the set of k-lists of nonempty 3\underline{5}241OK permutations of total length n.

Consider a permutation with (possibly) multiple stars in the allowed locations, for example, with k = 8 and hence 7 stars and with a, b denoting non-max LIT entries,

… ∗ ∗ ∗ a … ∗ b … ∗ n ∗ ∗ …

We will show how to represent this as an element of X_{n,j} for some j together with a bit sequence of j 0s and k − j 1s. The preceding Theorem then converts the element of X_{n,j} to a j-list of nonempty 3\underline{5}241OK permutations of total length n, while the 1s in the bit sequence specify the locations for empty permutations and we have the desired k-list of permutations of total length n.

To obtain the element of X_{n,j} associated with the given permutation, collapse all contiguous stars to a single star and delete the stars (if any) surrounding n. The example yields

… ∗ ∗ ∗ a … ∗ b … ∗ n ∗ ∗ … → … ∗ a … ∗ b … n … ∈ X_{n,j}

with j = 3 and j − 1 = 2 stars. To obtain the bit sequence associated with the given permutation, replace each star immediately preceding a non-max LIT entry and n itself by 1, all other stars by 0, and then suppress the permutation entries to get a bit sequence j 1s and k − j 0s; the example yields

… ∗ ∗ ∗ a … ∗ b … ∗ n ∗ ∗ … → (0 0 1^{∗a} 1^{∗b} 0 1^{n} 0 0).

Clearly, the original “multiple-starred” permutation can be uniquely recovered from the element of X_{n,j} and the bit sequence, and we are all done as soon as we establish Theorem 5. In fact, we will prove Theorem 5 with a specific type of bijection that permits a further reduction in the problem.

Define the LRmax factors of a permutation m_{1}L_{1}m_{2}L_{2} … m_{r}L_{r} to be m_{1}L_{1}, m_{2}L_{2}, …, m_{r}L_{r}. Then there is a refined form of Theorem 5 that goes as follows.

Theorem 6. Let X_{n,k} denote the set of 3\underline{5}241OK permutations on [n] with k − 1 of the non-max LIT entries marked. Let Y_{n,k} denote the set of k-lists of nonempty 3\underline{5}241OK permutations of total length n. There is a bijection from X_{n,k} to Y_{n,k}, π → v, of the following type: it rearranges the LRmax factors of π, then suitably concatenates some of them to form a k-list of permutations and, finally, reduces each one to yield v.

It suffices to present this bijection for the special case where L_{1}, L_{2}, …, L_{r} are all increasing lists, equivalently, since L_{1} < L_{2} < … < L_{r} for a 3\underline{5}241OK permutation, the entire list L_{1}L_{2} … L_{r} is increasing. (In the general case, sort each L_{i} and then apply the special case bijection except, just before reducing, replace each sorted L_{i} by the original list L_{i}.)

Note that permutations π = m_{1}L_{1}m_{2}L_{2} … m_{r}L_{r} for which the full list L_{1}L_{2} … L_{r} is increasing are precisely the 321-avoiding permutations (and automatically 3\underline{5}241OK). In summary, we have shown in this section that the entire problem boils down to

Theorem 7. There is a bijection of the following specific type from 321-avoiding permutations π on [n] with k − 1 of the non-max LIT entries marked to k-lists v of nonempty 321-avoiding permutations of total length n: it rearranges the LRmax factors of π, then suitably concatenates some of them to form a k-list of permutations and, finally, reduces each one to yield v.

4 The Main Bijection

We now prove Theorem 7 and use

\underline{3} 1 \underline{5} 2 \underline{8} 4 6 \underline{12} 7 \underline{15} 9 \underline{17} 10 11 \underline{20} \underline{\underline{25}} \underline{\underline{26}}^{∗} 13 \underline{\underline{27}} \underline{\underline{28}}^{∗} 14 \underline{\underline{29}}^{∗} 16 \underline{\underline{30}} 18 19 21 22 23 24

with n = 30 and k = 4 as a working example (as before, the LIT entries are double underlined and the other LRmax entries are single underlined). First, we split the permutation into panes each consisting of one or more LRmax factors. To do so, use a moving window initially covering a right factor of the permutation and consisting of k panes starting, respectively, at the very first LIT entry and the first LIT entry following each starred LIT entry. (Since the window gradually moves left, dropping the last pane and sometimes acquiring a new first pane, it is drawn below the permutation for clarity.)

3 1 5 2 8 4 6 12 7 15 9 17 10 11 20 25 26 13 27 28 14 29 16 30 18 19 21 22 23 24 . . . . .  . . . . .  . . . . .  . . . . .  . . . . .

The Initial Window

Proceed as follows until the entire permutation is covered by nonoverlapping panes. (It’s just possible that the initial window covers the entire permutation but this happens only for the identity permutation. In this case associate the symbol ∅ with the window and proceed to the second step below.) Find the maximum non-LRmax entry in all but the last pane of the current window (the max of the empty set is considered to be −∞) and denote this number m. Look for LRmax entries not yet empaned that exceed m. There are 2 cases. Case 1. There is no such LRmax entry. In this case associate ∅ with the current window, and delete the last pane to obtain the next window. Case 2. There exist LRmax entries not yet empaned that exceed m. In this case associate the smallest such entry, M say, with the current window and shift the window left by prepending a pane starting at M and deleting the last pane.

The resulting panes and the successive windows, each with an associated LRmax or ∅ symbol, are shown.

3 1 5 2 8 4 6 12 7 15 9 17 10 11 20 25 26 13 27 28 14 29 16 30 18 19 21 22 23 24 → 17 → 15 → ∅ → 12 → ∅ → 8 → ∅ → 3 → ∅ . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .  . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .  . . . . .. . . . .. . . . .. . . . .. . . . .  . . . . .. . . . .. . . . .  . . . . .. . . . .  . . . . .  . . . . .  . . . . .  . . . . .  . . . . .

The Moving Window

Second, rearrange the panes using a k-row array formed from a list consisting of (i) the windows’ associated LRmax entries and ∅s, and (ii) the first entries of the k panes of the initial window:

∅ 3 ∅ 8 ∅ 12 ∅ 15 17 25 27 29 30

Insert the list entries right to left into array entries lower right to upper left moving up each column in turn EXCEPT, when a ∅ is inserted, that row is “not accepting any more entries” and is henceforth skipped over. The resulting array is

∅ 12 25
∅ 27
∅ 3 8 15 29
∅ 17 30

Now form a list of k permutations by concatenating the panes initiated by the LRmax entries in each row:

12 7 25 26 13, 27 28 14, 3 1 5 2 8 4 6 15 9 29 16, 17 10 11 20 30 18 19 21 22 23 24

Finally, reduce each one to get the desired k-list of 321-avoiding permutations:

2 1 4 5 3, 2 3 1, 3 1 5 2 7 4 6 9 8 11 10, 3 1 2 6 11 4 5 7 8 9 10.

Note that LIT entries in these reduced permutations correspond to LIT entries in the original as do LRmax entries.

To reverse the process, suppose we are given a list (π_{1}, π_{2}, …, π_{k}) of k 321-avoiding permutations of total length n and let us use the previous example with k = 4 and n = 30. Double underline the LIT entries in each π_{i} and single underline the remaining LRmax entries. Form a pane from the first LIT entry to the end of each permutation.

\underline{2} 1 \underline{\underline{4}} π_{1} \underline{\underline{5}} 3 , \underline{\underline{2}} \underline{\underline{3}} π_{2} 1 , \underline{3} 1 \underline{5} 2 \underline{7} 4 π_{3} 6 \underline{9} 8 \underline{\underline{11}} 10 , \underline{3} 1 2 \underline{6} \underline{\underline{11}} 4 π_{4} 5 7 8 9 10

The Initial Panes

Place n, n − 1, n − 2, … below the LIT entries working right to left.

\underline{2} 1 \underline{\underline{4}} \underline{\underline{5}} 25 26 3 , \underline{\underline{2}} \underline{\underline{3}} 27 28 1 , \underline{3} 1 \underline{5} 2 \underline{7} 4 6 \underline{9} 8 \underline{\underline{11}} 29 10 , \underline{3} 1 2 \underline{6} \underline{\underline{11}} 30 4 5 7 8 9 10

Place LIT Entries

Set b = largest integer in [n] not yet placed; here b = 24. Start with the last permutation in the list. Take the largest entry that is blank below (here, 10), place b in the blank, decrement b and repeat as long as these largest entries are (i) empaned or (ii) underlined. Then add a pane that begins at the leftmost newly added entry unless it is already empaned.

\underline{2} 1 \underline{\underline{4}} \underline{\underline{5}} 25 26 3 , \underline{\underline{2}} \underline{\underline{3}} 27 28 1 , \underline{3} 1 \underline{5} 2 \underline{7} 4 6 \underline{9} 8 \underline{\underline{11}} 29 10 , \underline{3} 17 1 2 \underline{6} 20 \underline{\underline{11}} 30 4 5 7 8 9 10 18 19 21 22 23 24

Work Last Permutation

Decrement b (now b = 16) and proceed to the next permutation to the left in the list (considering the last to be the left neighbor of the first). Repeat until b = 0 and no blanks remain. The second step gives

\underline{2} 1 \underline{\underline{4}} \underline{\underline{5}} 25 26 3 , \underline{\underline{2}} \underline{\underline{3}} 27 28 1 , \underline{3} 1 \underline{5} 2 \underline{7} 4 6 \underline{9} 8 \underline{\underline{11}} 15 29 16 10 , \underline{3} 17 1 2 \underline{6} 20 \underline{\underline{11}} 30 4 5 7 8 9 10 18 19 21 22 23 24

Work Penultimate Permutation

and the final result (omitting the no-longer-needed underlines) is

2 1 12 7 4 5 25 26 3 13 , 2 3 27 28 1 14 , 3 1 5 2 7 4 6 3 1 5 2 8 4 6 9 89 11 15 29 16 10 , 3 17 1 2 10 11 6 20 11 30 4 5 7 8 9 10 18 19 21 22 23 24

Final Result

The marked LIT entries are now retrieved as the max entry in the last pane of all but the last permutation, here 26, 28, 29. Arrange the panes in increasing order of first entries to retrieve the original starred permutation.

5 Underlined 3- and 4-Patterns

There are 3×3! = 18 similarly restricted patterns involving 3 letters and 4×4! = 96 involving 4 letters. Let’s call them underlined patterns; for instance, the underlined 4-pattern 4\underline{2}31 requires that a 431 pattern occur only as part of a 4231. We say that a permutation meeting this pattern restriction satisfies 4\underline{2}31 or is 4\underline{2}31OK.

Only two counting sequences arise for underlined 3-patterns. Seven require the permutation to be increasing, and seven require it to be decreasing; these 14 patterns are counted by the all-1s sequence. The remaining 4 patterns are \underline{1} 3 2, 2 1 \underline{3}, 2 3 \underline{1}, \underline{3} 1 2. A permutation π is \underline{1}32OK iff π(1) = 1, 21\underline{3}OK iff π(n) = n, and similarly for the other two. Thus these 4 underlined 3-patterns are counted by the shifted factorial sequence ((n − 1)!)_{n≥1}.

Four different counting sequences arise for underlined 4-patterns. We will show that 64 give the Catalan numbers, 16 give the Bell numbers, 12 give sequence A051295 in OEIS, and 4 give the sequence with nth term = (n−1)!+∑_{k=0}^{n−2} ∑\begin{matrix}i,j≥0 \\ i+j≤k \end{matrix} k\overline{ı} (n−2−k)\underline{j} using rising/falling

factorial notation.

The reverse and inverse of an underlined pattern are defined in the obvious way so that a permutation satisfies a given underlined pattern if and only if its reverse (resp. inverse) satisfy the reverse (resp. inverse) of the underlined pattern. The operations reverse and inverse on permutations generate a dihedral group of order 8. For example, Inverse ∘ Reverse ∘ Inverse = Complement where the complement of a permutation π on [n] is n + 1 − π (entrywise). Under the action of this group, the 96 underlined 4-patterns are partitioned into equivalence classes, the members of each one all having the same counting sequence. In fact, 64 underlined 4-patterns entail avoidance of the associated 3-pattern altogether. For each of the 6 patterns of length 3, the permutations avoiding it are counted by the Catalan numbers [2]. Hence these 64 are counted by Catalan numbers A000108. (Incidentally, they split into 11 equivalence classes: 5 of size 8 and 6 of size 4.) The remaining 32—the nontrivial underlined 4-patterns—split into 5 classes as shown in the Table (the top row contains convenient class representatives).

3 2 \underline{4} 1 3 1 \underline{4} 2 \underline{1} 3 4 2  \underline{1} 3 2 4 3 2 1 \underline{4}
1 3 4 \underline{2} \underline{3} 1 4 2 \underline{1} 4 2 3  1 3 2 \underline{4} \underline{4} 1 2 3
1 \underline{4} 2 3 3 1 4 \underline{2} 2 3 1 \underline{4}  4 2 3 \underline{1} \underline{1} 4 3 2
2 3 \underline{1} 4 3 \underline{1} 4 2 2 4 3 \underline{1}  \underline{4} 2 3 1 2 3 4 \underline{1}
\underline{2} 4 3 1 2 4 \underline{1} 3 3 1 2 \underline{4}
\underline{3} 1 2 4 \underline{2} 4 1 3 3 2 4 \underline{1}
4 \underline{1} 3 2 2 4 1 \underline{3} \underline{4} 1 3 2
4 2 1 \underline{3} 2 \underline{4} 1 3 \underline{4} 2 1 3
Bell Bell A051295 A051295 new

The 5 equivalence classes of nontrivial underlined 4-patterns and their counting sequences

It remains to verify the counting sequences for the 5 classes.

Bell Sequence Consider two canonical ways to represent a set partition of [n].

Canonical Increasing largest entry first in each block, rest of block increasing, blocks arranged in increasing order of first element, as in 412-6-735.

Canonical Decreasing each block decreasing, blocks arranged in increasing order of first element, as in 421-6-753.

Theorem 8. Splitting a permutation on [n] into its LRmax factors m_{1}L_{1}, …, m_{r}L_{r} is a bijection from

(i ) 32\underline{4}1OK permutations on [n] to set partitions of [n] in canonical increasing form. (ii ) 31\underline{4}2OK permutations on [n] to set partitions of [n] in canonical decreasing form.

Proof (i) If π is 32\underline{4}1OK yet some L_{i} fails to be increasing, then there exist u preceding v in L_{i} with u > v and m_{i}uv is an offending 321 pattern. Conversely, if each L_{i} is increasing, then a 321 must have its “2” and “1” in different blocks and π is 32\underline{4}1OK.

(ii) If π is 31\underline{4}2OK yet some LRmax factor m_{i}L_{i} fails to be decreasing, then there exist u preceding v in L_{i} with u < v and m_{i}uv is an offending 312 pattern. Conversely, if the LRmax factors of π are all decreasing, then a 312 must have its “1” and “2” in different blocks and π is 31\underline{4}2OK.

Since set partitions are counted by the Bell numbers A000110, this verifies the first 2 columns in the Table.

A051295 Sequence Let us count \underline{1}324OK permutations on [n]. We claim each such permutation π has the form π_{1}1π_{2} where π_{1} is a \underline{1}324OK permutation on [n − k + 2, n] with k the position of 1 in π, and π_{2} is an arbitrary permutation on [2, n − k + 1]. To see the claim, observe that each such π is \underline{1}324OK. Conversely, if π is \underline{1}324OK, all entries preceding 1 in π necessarily exceed all entries following 1 or else there is a subpermutation u1v with u < v forming an offending 324 pattern. While π_{1} must be \underline{1}324OK, the entry 1 relieves π_{2} of any obligation, and the claim follows. This decomposition implies that the number u_{n} of \underline{1}324OK permutations on [n] satisfies u_{n} = ∑_{k=1}^{n} u_{k−1}(n − k)!, and hence (u_{n}) is sequence A051295 in OEIS.

Next, we count \underline{1}342OK permutations on [n] by position k of 1. If 1 occurs in first position, the rest of the permutation is arbitrary. Otherwise, we claim the permutation has the form (with 1 in position k ≥ 2)

a_{1} … a_{k−1} 1 π[2, a_{k−1} − 1] π[a_{k−1} + 1, a_{k−2} − 1] … π[a_{2} + 1, a_{1} − 1] π[a_{1} + 1, n]

where a_{1} > a_{2} > … > a_{k−1} and π[b, c] denotes an arbitrary permutation on the interval of integers [b, c] (understood to be the empty permutation if b > c).

Such permutations are clearly \underline{1}342OK. Conversely, given a \underline{1}342OK permutation, the entries a_{1}, …, a_{k−1} preceding 1 are necessarily decreasing left to right for otherwise there is a subpermutation a b 1 with a < b. This is a 342 pattern with no hope of the required “1”. And for 2 ≤ i ≤ k − 1, all elements of [a_{i} + 1, a_{i−1} − 1] precede all elements of [a_{i−1} + 1, a_{i−2} − 1] ⊔ … ⊔ [a_{1} + 1, n] else some b > a_{i−1} precedes some c < a_{i−1} in the permutation and a_{i−1} b c is an offending 342 pattern because all entries preceding a_{i−1} exceed a_{i−1}. The claim follows.

With u_{n,k} the number of \underline{1}342OK permutations on [n] for which 1 occurs in position k, this decomposition implies the generating function identity for each k ≥ 1

∑_{n≥0} u_{n,k}x^{n} = x^{k}( ∑_{n≥0} n!x^{n})^{k}

and so (u_{n,k}) forms sequence A084938 in OEIS with row sums A051295. This verifies columns 3 and 4 of the Table.

The fact that \underline{1}324 and \underline{1}342 are Wilf-equivalent (that is, have the same counting sequence) despite being in different equivalence classes can be explained by a simple bijection from \underline{1}324OK permutations to \underline{1}342OK permutations. Factor a \underline{1}324OK permutation π as

m_{1} L_{1} m_{2} L_{2} … m_{r} L_{r}

where m_{1}, m_{2}, … are now the left-to-right minima of π. Then reassemble as

m_{1} m_{2} … m_{r} L_{r} L_{r−1} … L_{1}.

This works because L_{i} is a permutation on [m_{i} + 1, m_{i−1} − 1] for 1 ≤ i ≤ r (m_{0} := n + 1) for otherwise there is an entry b following m_{i} in π with b > m_{i−1} and m_{i−1} m_{i} b is an offending 324 pattern.

New Sequence The 321\underline{4}OK permutations on [n] can be counted directly by position of n. If n occurs in last position, the rest of the permutation is unrestricted—(n−1)! choices. If n occurs in position n − 1 and the last entry is i, then i + 1, i + 2, …, n must occur in that order else i terminates an offending 321. Thus the permutation is determined by the positions of 1, 2, …, i − 1, for which there are (n − 2)\underline{i−1} choices. Here j\underline{i} = j(j − 1) … (j − i + 1) is the falling factorial.

Now suppose n occurs in position k ≤ n − 2. The subpermutation following n must be increasing and hence has the form 1 ≤ a < y_{1} < y_{2} < … < y_{n−k−2} < b < n. Fix a and b and let (x_{i})_{i=1}^{r} = (a, b)\(y_{i})_{i=1}^{n−k−2} entailing r = (b − a − 1) − (n − k − 2) = b − t with t = a + n − k − 1. The subpermutation preceding n has no restriction on the entries < a and placing these entries gives (k −1)\underline{a−1} choices. However, its entries > b must be increasing left to right (else there exist u > v > b with u preceding v and u v b is an offending 321) and must all lie to the right of the x_{i}s (else some u > b precedes some x_{i} and u > b > x_{i} > a implies u x_{i} a is an offending 321). Thus the subpermutation preceding n and involving entries > a yields only r! choices: arrange the x_{i}s. All told, the desired count is (with t := a + n − k − 1 and n ≥ 1)

(n − 1)! + ∑_{i=1}^{n−1}(n − 2)\underline{i−1} + ∑_{k=1}^{n−2} ∑_{a=1}^{k} ∑_{b=t}^{n−1}(k − 1)\underline{a−1}\binom{b − a − 1}{n − k − 2}(b − t)! =

(n − 1)! + ∑_{k=0}^{n−2} ∑_{\begin{matrix}i,j≥0 \\ i+j≤k \end{matrix}} k\overline{ı} (n − 2 − k)\underline{j}.

This sequence begins (1, 1, 2, 5, 15, 55, 248, 1357, 8809, 66323, 568238, …)_{n≥0} and is entrywise ≥ the next largest counting sequence A051295 = (1, 1, 2, 5, 15, 54, 235, 1237 …); both seem to grow asymptotically as (n − 1)!.

A pattern restriction similar to one of our underlined 4-patterns arises in a recent paper [4] on “patience sorting” of a deck of cards into piles, namely, the restriction that a 342 pattern in which the “4” and “2” are contiguous occurs only as part of a 3142 pattern. It is almost immediate, however, that the permutations satisfying this seemingly weaker restriction coincide with our 3\underline{1}42OK permutations (and hence are counted by the Bell numbers).

Added in Proof. The main result of this paper is used to obtain another manifestation of the eigensequence for composition A030266 strictly in terms of pattern avoidance in [5].

Acknowledgment

I thank the referee for a careful reading of the paper and several helpful remarks.

References

[1] Mira Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra and its Applications, Vol. 226-228 (1995), pp. 57–72; errata Vol. 320 (2000), p. 210, arXiv math.CO/0205301.

[2] Richard P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, 1999. Exercise 6.19 and related material on Catalan numbers are available online at http://www-math.mit.edu/ rstan/ec/ .

[3] S. Dulucq, S. Gire, and O. Guibert, A combinatorial proof of J. West’s conjecture, Discrete Math. 187 (1998) 71–96.

[4] Alexander Burstein, Combinatorics of Patience Sorting Piles, arXiv math.CO/0506358, 18 Jun 2005, 19 pp.

[5] David Callan, A Wilf Equivalence Related to Two Stack Sortable Permutations, 2005, preprint, arXiv math.CO/0510211 .

2000 Mathematics Subject Classification: 05A15. Keywords: eigensequence, 3\underline{5}241OK permutation, restricted pattern, underlined pattern.

(Concerned with sequences \underline{A000108}, \underline{A000110}, \underline{A030266}, \underline{A051295}, \underline{A084938}, and \underline{A110447}.)

Received August 4 2005; revised version received December 19 2005. Published in Journal of Integer Sequences, January 3 2006.

Return to Journal of Integer Sequences home page.