Lagrange Inversion Counts 3\overline{5}241-Avoiding Permutations

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

                     callan@stat.wisc.edu

Abstract

In a previous paper, we showed that 3\overline{5}241-avoiding permutations are counted by the unique sequence that starts with a 1 and shifts left under the self-composition transform. The proof uses a complicated bijection. Here we give a much simpler proof based on Lagrange inversion.

1 Introduction

A permutation avoids the barred pattern 3\overline{5}241 [1] when the (not necessarily consecutive) pattern 3241 occurs only as part of a 35241 pattern. The composition of two sequences (a_{n})_{n≥1} and (b_{n})_{n≥1} is defined by composition of their (ordinary) generating functions. A sequence is unital if its first term is 1. There is a unique unital sequence (b_{n})_{n≥1} whose composition with itself is equal to its left shift, (b_{2}, b_{3}, …), the so-called left-shift eigensequence for self-composition. This sequence begins (b_{n})_{n≥1} = (1, 1, 2, 6, 23, 104, 531, …). In a previous paper [1], we showed that the counting sequence for 3\overline{5}241-avoiding permutations is this sequence indexed from 0. More precisely, with S_{n}(τ) denoting the set of permutations of [n] that avoid the pattern τ, we established

Theorem 1. The sequence (a_{n})_{n≥1} defined by a_{1} = 1 and, for n ≥ 1, a_{n+1} = | S_{n}(3\overline{5}241) | is the left-shift eigensequence for self-composition.

The proof used a rather complicated bijection. Our objective here is to simplify the proof using Lagrange inversion. We start with the characterization of 3\overline{5}241-avoiding permutations given in [1], and recall some notation. Every permutation π on [n], considered as a list (or word), 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 of π (LRmax for short) and the L_{i} are the intervening words. We call m_{1}L_{1} / m_{2}L_{2} / … / m_{r}L_{r} the LRmax decomposition of π.

Theorem 2. [1, Theorem 1] A permutation π on [n] is 3\overline{5}241-avoiding if and only if its LRmax decomposition satisfies

( 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\overline{5}241-avoiding.

2 The revert-reciprocal transform

Let us define a transform on sequences, (a_{n})_{n≥1} → (b_{n})_{n≥1}, using generating functions, by

A(x) → B(x) := (\frac{x}{1 + A(x)})^{⟨−1⟩} ,

where ^{⟨−1⟩} denotes compositional inverse. We shall call it the revert-reciprocal transform. The Lagrange inversion formula [2, Theorem 5.4.2, p. 38] is just the ticket to find an explicit form for the entries of the transformed sequence—we find that b_{1} = 1 and for n ≥ 1,

b_{n+1} = \frac{1}{n + 1} ∑_{1^{r_{1}}... n^{rn}⊢n} \binom{n + 1}{n + 1 − ∑_{i=1}^{n}r_{i}, r_{1}, …, r_{n}}a_{1}^{r_{1}}a_{2}^{r_{2}} … a_{n}^{r_{n}},

where the sum is over all partitions 1^{r_{1}} … n^{r_{n}} of n, written in frequency-count form. Thus the unique fixed point (a_{n})_{n≥1} for the revert-reciprocal transform is defined by a_{1} = 1 and for n ≥ 1,

a_{n+1} = \frac{1}{n + 1} ∑_{1^{r_{1}}... n^{rn}⊢n} \binom{n + 1}{n + 1 − ∑_{i=1}^{n}r_{i}, r_{1}, …, r_{n}}a_{1}^{r_{1}}a_{2}^{r_{2}} … a_{n}^{r_{n}}.  (1)

Proposition 3. The fixed point for revert-reciprocal coincides with the left-shift eigensequence for self-composition.

Proof. With B(x) := (\frac{x}{1+A(x)})^{⟨−1⟩}, the revert-reciprocal transform of A(x), we have

B(x)  = A(x) ⇔
\frac{A(x)}{1 + A(A(x))} = x  ⇔
A(A(x)) = \frac{A(x) − x}{x},

which is the defining relation for the left-shift eigensequence for self-composition.

3 Permutations and trees

We consider a permutation as a word of distinct letters from the alphabet of positive integers. A cycle is a permutation in which the largest entry occurs first. A standard permutation is one on an initial segment of the positive integers. To standardize a permutation means to replace its smallest entry by 1, second smallest by 2, and so on. A cycle-labeled ordered tree is an ordered tree in which, for each non-leaf vertex v, the child edges of v are labeled, left to right, with the entries of a standard cycle.

Theorem 4. Permutations on [n] satisfying condition (i ) of Theorem 2 are in bijective correspondence with cycle-labeled ordered trees on n edges.

Proof. In the LRmax decomposition, m_{1}L_{1} / m_{2}L_{2} / … / m_{r}L_{r}, of a permutation π on [n], set a_{i} = length of m_{i}L_{i} and b_{i} = m_{i} − m_{i−1} for 1 ≤ i ≤ r, with m_{0} := 0. Now create a_{r} edges from the root labeled with the entries of m_{r}L_{r} from left to right. Then, at the b_{r}-th leaf, place a_{r−1} edges labeled with m_{r−1}L_{r−1}. Proceed to place a_{r−2} edges labeled with m_{r−2}L_{r−2} in the current tree at leaf number b_{r−1} starting from the newly created leaf in the current tree as leaf number 1, and so on. (This means that at the k-th step, when a_{r−k} edges are inserted at a leaf in the current tree, precisely ∑_{i=1}^{k}(b_{r−i+1} − 1) = n − m_{r−k} − k leaves in the current tree will precede the insertion leaf.)

The result for π = 3 1 2 / 5 4 / 11 7 6 8 / 12 / 14 13 10 9 is shown on the left in Figure 1 below.

(a_{i})_{i=1}^{r} = (3, 2, 4, 1, 4), (b_{i})_{i=1}^{r} = (3, 2, 6, 1, 2) 11  7 6  8 12 14  13  10 9 5  4 1 3  2 edge-labeled tree ^{4  2 1  3 1 4  3  2  1 2  1 1 3  2 cycle-labeled tree}

Figure 1

Next, for each non-leaf vertex, erase the label on its leftmost child edge (a LRmax entry), standardize the permutation labeling the remaining child edges, and relabel the leftmost child edge with the outdegree of the vertex, thereby obtaining a standard cycle as the labeling on the child edges of the vertex. The result is shown on the right in Figure 1 above with leftmost child edge labels in red.

The LRmax entries are encoded in the cycle-labeled tree by the locations of the nonleaf vertices, and so can be recovered. The leftmost child edge labels on non-leaf vertices taken in preorder (aka clockwise walkaround order) give the lengths of the m_{i}L_{i} segments in reverse order. Since we know the LRmax entries, the support sets of the L_{i}’s can then be determined. Finally, the permutations labeling the child edges of the non-leaf vertices (ignoring the label on the leftmost edge) determine the actual words L_{i} from their support sets.

4 The coup de grâce

The number of ordered trees on n edges (hence, n + 1 vertices) with outdegree sequence (r_{i})_{i=0}^{n}—r_{i} is the number of vertices with i children—is [2, Theorem 5.3.10, p. 34]

\frac{1}{n + 1}\binom{n + 1}{r_{0}, r_{1}, …, r_{n}}.

Necessarily, ∑_{i=0}^{n} r_{i} = n + 1, the number of vertices, and ∑_{i=0}^{n} ir_{i} = n, the number of edges. Under the correspondence of Theorem 4, Theorem 2 (ii) says that 3\overline{5}241-avoiding permutations on [n] correspond to cycle-labeled trees with n edges in which each cycle (or, equivalently, each cycle without its first entry) is 3\overline{5}241-avoiding.

Consequently, by counting cycle-labeled trees in which the label lists associated with the vertices are 3\overline{5}241-avoiding permutations, we find, letting a_{n} denote the number of 3\overline{5}241avoiding permutations on [n − 1], that

a_{n+1} = \frac{1}{n + 1} ∑_{1^{r_{1}}... n^{rn}⊢n} \binom{n + 1}{n + 1 − ∑_{i=1}^{n}r_{i}, r_{1}, …, r_{n}}a_{1}^{r_{1}}a_{2}^{r_{2}} … a_{n}^{r_{n}}.

But this is precisely the relation (1) that defines the fixed point sequence for revert-reciprocal and so, since this fixed point coincides with the left-shift eigensequence for self-composition by Proposition 3, Theorem 1 is established.

5 Concluding remarks

The revert-reciprocal transform as defined in Section 2 is convenient for our purposes. But the transform always starts with a 1. If we redefine the revert-reciprocal transform to delete this 1,

A(x) → B(x) := \frac{(\frac{x}{1 + A(x)})^{⟨−1⟩} − 1}{x},

then it becomes an invertible transform from sequences (a_{n})_{n≥1} to (b_{n})_{n≥1} and, with this modified definition of revert-reciprocal, Proposition 3 has the form

The (unique) left-shift eigensequences for the transforms revert-reciprocal and self-composition coincide. The two transforms, however, are quite different: the only sequence on which they agree is this left-shift eigensequence. Self-composition is not quite invertible, but it is invertible on the set of real sequences with positive first entry, {(a_{n})_{n≥1} : a_{1} > 0}.

6 Acknowledgement

My thanks to a sharp-eyed referee for catching a garbled description of the bijection of Theorem 4 in the original version.

References

[1] J David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, J. Integer Seq., 9 (2006), Article 06.1.4.

[2] Richard P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, 1999.

2010 Mathematics Subject Classification: 05A15. Keywords: eigensequence, barred pattern, Lagrange inversion.

(Concerned with sequence \underline{A110447}.)

Received June 10 2011; revised version received September 26 2011. Published in Journal of Integer Sequences, October 16 2011.

Return to Journal of Integer Sequences home page.