Counting Stabilized-Interval-Free Permutations

David Callan Department of Statistics University of Wisconsin-Madison 1210 W. Dayton St Madison, WI 53706-1693

                     callan@stat.wisc.edu

Abstract

A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n]. By presenting a decomposition of an arbitrary permutation into a list of SIF permutations, we show that the generating function A(x) for SIF permutations satisfies the defining property: [x^{n−1}]A(x)^{n} = n! . We also give an efficient recurrence for counting SIF permutations.

1 Introduction

A permutation on [n] = {1, 2, …, n} is stabilized-interval-free (SIF) if it does not stabilize any proper subinterval of [n] (proper means nonempty and ≠ [n]). For example, ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 1 & 5 & 3 & 4 & 2 \end{matrix} ), or 6 1 5 3 4 2 in one-line notation, fails to be SIF because it stabilizes the interval [3, 5] = {3, 4, 5}. On the other hand, the empty permutation is SIF, as is any cycle, and every SIF permutation on [n] is fixed-point-free for n ≥ 2. The SIF permutations on [n] for n ≤ 4 are as follows: n = 1 : 1; n = 2 : 2 1; n = 3 : 2 3 1, 3 1 2 (the two 3-cycles) n = 4 : 3 4 1 2 and the six 4-cycles. Let a_{n} denote the number of SIF permutations on [n] and A(x) = ∑_{n≥0} a_{n}x^{n} = 1 + x + x^{2} + 2x^{3} + 7x^{4} + … their generating function. The first objective of this paper is to show that [x^{n−1}]A(x)^{n} = n! and hence that the number of SIF permutations on [n] is given by A075834. This generating function identity amounts to the existence of a decomposition of an arbitrary permutation into a list of SIF permutations. The second objective is to obtain a recurrence relation that permits efficient computation of a_{n} :

a_{0} = a_{1} = 1, a_{n} = ∑_{j=2}^{n−2}(j − 1)a_{j}a_{n−j} + (n − 1)a_{n−1}, n ≥ 2.

A little more generally, a permutation on an arbitrary set of positive integers I is SIF if it does not stabilize any proper subinterval of I (J is a subinterval of I if a, b ∈ J, c ∈ I with a ≤ c ≤ b implies c ∈ J). Thus 5 9 2 3 is SIF on {2, 3, 5, 9} and its reduced form (replace smallest element by 1, second smallest by 2, and so on) is 3 4 1 2. The former is a labeled SIF permutation and the latter is unlabeled—we take [n] as the standard n-element totally ordered set and call a permutation on [n] unlabeled.

Let S_{I} denotes the set of all permutations on I. Given σ ∈ S_{I}, one can partition I into consecutive subintervals I_{1}, …, I_{k} such that σ stabilizes each I_{j}. The intervals in the finest such partition are called the connected intervals of σ; a permutation with exactly one such interval is connected (sometimes called indecomposable) A003319. Note that the empty permutation is not connected. The restriction of σ to its connected intervals clearly gives a decomposition of σ into a set of connected permutations on subintervals that partition I, called the connected components of σ. These permutations are labeled but we also have a decomposition into a list of unlabeled connected permutations of total length n (since we can use position in the list to determine the labels) and this decomposition is bijective. For example, 3 2 4 1 5 7 8 6 ⟷ {3 2 4 1, 5, 7 8 6}⟷ 3 2 4 1 – 1 – 2 3 1 (the dashes separate list items).

Now [x^{n−1}]A(x)^{n} is the number of length-n lists (or simply n-lists) of unlabeled SIF permutations of total length n − 1 (keeping in mind that the empty permutation has length 0). So, to show [x^{n−1}]A(x)^{n} = n!, it suffices to exhibit a bijection from S_{[n]} to n-lists of unlabeled SIF permutations of total length n−1, and we will do so below. This decomposition into unlabeled SIF permutations is analogous to the one above into unlabeled connected permutations but is not so obvious.

Before presenting the bijection we recall some relevant manifestations of the Catalan numbers [1]. A Murasaki diagram is a sequence of vertical lines some (all, or none) of which are joined at their tips by horizontal lines that never intersect the interior of a vertical line.

1 2 3 4 5 6 7 8 9 10 11 12

The diagram illustrated has 3 components; the first of which has 3 segments (connected figures), the second 1 and the last 2. A partition {B_{1}, B_{2}, …, B_{k}} of [n] is noncrossing if a < b < c < d with a, c ∈ B_{i} and b, d ∈ B_{j} implies i = j. Murasaki diagrams correspond in an obvious way to noncrossing partitions: the one above corresponds to 1 7–2 3 5 6–4–8– 9 10 12–11 and we may speak of the components of a noncrossing partition. A lattice path of upsteps (1, 1) and downsteps (1, −1) (starting at the origin for convenience) is balanced if it ends on the x-axis, nonnegative if it never dips below the x-axis, Dyck if it is both. A Dyck n-path P has n upsteps and n downsteps; each downstep d has a matching upstep u: head horizontally west from d to the first upstep u that you encounter. Each x-axis point on P other than the starting point is a return of P; P is strict if it has only one return. Its returns divide a nonempty Dyck path into a list of its components, each of which is a strict Dyck path. For any path, a nonzero ascent is a maximal sequence of contiguous upsteps (we assume a zero ascent between a pair of contiguous downsteps); similarly for descents.

Noncrossing partitions π on [n] correspond to Dyck n-paths P: arrange the blocks of π in increasing order of their maximal elements; let (m_{i})_{i=1}^{k} be these maximal elements and let (n_{i})_{i=1}^{k} be the corresponding block sizes. Then, with m_{0} := 0, the lists (m_{i} − m_{i−1})_{i=1}^{k} and (n_{i})_{i=1}^{k} determine π and are, respectively, the nonzero ascent lengths and nonzero descent lengths defining P. This correspondence preserves components. For the example 1 7–2 3 5 6– 4–8–9 10 12–11 above, we have (m_{i})_{i=1}^{k} = (4, 6, 7, 8, 11, 12) and (n_{i})_{i=1}^{k} = (1, 4, 2, 1, 1, 3). So the nonzero ascent (resp. descent) lengths are given by the top (resp. bottom) row of ( \begin{matrix}4 & 2 & 1 & 1 & 3 & 1 \\ 1 & 4 & 2 & 1 & 1 & 3 \end{matrix} ) and the corresponding Dyck path is

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ^{1 2 3 4  5 6  7  8  9 10 11  12}]

To recover the noncrossing partition, label the upsteps in order 1 through n. Then each descent yields a block via the labels on its matching upsteps (the first descent gives the singleton block {4}).

An arbitrary permutation σ on [n] can be split into a set of labeled SIF permutations whose underlying sets partition [n]. First, decompose σ into its connected components σ_{1}, σ_{2}, …, σ_{k}. For each i ∈ [k], set aside the maximal proper subintervals (if any) stabilized by σ_{i}; these maximal subintervals are disjoint since, if σ_{i} stabilizes intervals J_{1}, J_{2} then σ_{i} stabilizes J_{1} ∪ J_{2} also. Because σ_{i} is connected, what’s left is a nonempty subset of [n] also stabilized by σ_{i} on which σ_{i} is SIF. Repeat this procedure on the connected components of the restriction of σ to the intervals set aside, continuing till nothing is set aside. The resulting set of labeled SIF permutations corresponds to a Murasaki diagram in which an unlabeled SIF permutation is associated with each segment; the segments record the underlying sets, the unlabeled SIF permutations record the action of the permutation. For example,

( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 7 & 5 & 6 & 4 & 2 & 3 & 1 & 8 & 10 & 12 & 11 & 9 \end{matrix} ) splits into ( \begin{matrix}1 & 7 \\ 7 & 1 \end{matrix} ) , ( \begin{matrix}2 & 3 & 5 & 6 \\ 5 & 6 & 2 & 3 \end{matrix} ) , ( \begin{matrix}4 \\ 4 \end{matrix} ) , ( \begin{matrix}8 \\ 8 \end{matrix} ) , ( \begin{matrix}9 & 10 & 12 \\ 10 & 12 & 9 \end{matrix} ) , ( \begin{matrix}11 \\ 11 \end{matrix} ). The Murasaki

diagram is the one above and unlabeled SIFs are associated with segments as follows.

segments by smallest element 1 2 4 8 9 11 corresponding unlabeled SIF 21 3412 1 1 231 1

Now we are ready to present the bijection from S_{[n]} to n-lists of unlabeled SIF permutations whose total length is n − 1, and we will use

σ = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ 2 & 4 & 3 & 1 & 8 & 7 & 6 & 5 & 13 & 10 & 9 & 16 & 11 & 15 & 14 & 12 \end{matrix})

as a working example with n = 16. First, decompose σ into its connected components (σ_{i})_{i=1}^{k}. Record the position j of n in σ (here j = 12), then delete n from σ_{k} to get a permutation σ′_{k} (deleting n simply means erasing n from its cycle and so σ′_{k}(j) = σ(n) ). Here σ′_{k} = ( \begin{matrix}9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 13 & 10 & 9 & 12 & 11 & 15 & 14 \end{matrix} ). Note that since σ_{k} is connected, j = σ^{−1}(n) is necessarily in the first component of σ′_{k}. Now draw the Murasaki diagrams for σ_{1}, …, σ_{k−1}, σ′_{k} and record the associated unlabeled SIF for each segment.

1 2 3 4  5 6 7 8  9 10 11 12 13 14 15

segments by smallest element 1  3  5 6  9 10 12 14 ; corresponding unlabeled SIF \underbrace{231}_{μ_{1}} \underbrace{1}_{μ_{2}}  \underbrace{21}_{ρ_{1}} \underbrace{21}_{ρ_{2}}  \underbrace{312}_{τ_{1}} \underbrace{1}_{τ_{2}} \underbrace{1}_{τ_{3}} \underbrace{21}_{τ_{4}}

Translate each Murasaki diagram → noncrossing partition → Dyck path, recalling that segment → block → nonzero descent, so each nonzero descent is associated with an SIF, and mark upstep j unless j = n in which case σ′_{k} is the empty permutation.

[figure: .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; .....; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; j; ^{1 2 3  4  5 6 7  8  9 10  11 12  13  14 15}; μ_{1}; μ_{2}; ρ_{1}; ρ_{2}; τ_{1}; τ_{2}; τ_{3}; τ_{4}]

Dyck paths, upsteps labeled in order, nonzero descents labeled with corresponding SIF permutation (whose length = length of descent). All but the last are strict Dyck paths. The marked upstep (here 12) is in the

first component of the last path (unless the last path is empty).

Now we use a cut-and-paste technique to massage these Dyck paths into a balanced path in a reversible way (making critical use of the marked upstep). The process will preserve all nonzero descents and so we can carry their SIF labels along with them. Cut the last Dyck path just before its marked upstep into two paths R, S. For each of the first k − 1 Dyck paths, remove its last upstep thereby forming a path P_{i}, a removed upstep, and a nonzero path D_{i} consisting entirely of downsteps, 1 ≤ i ≤ k − 1. Then rearrange in the following order to form a balanced path Q: D_{1} u D_{2} u … D_{k−1} u S R P_{1} P_{2} … P_{k−1}.

[figure: ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; ^{.....}; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; . . . . .; D_{1}; u; D_{2}; u; S; R; P_{1}; P_{2}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ^{4  8 12  13  14 15  9 10  11 1 2 3  5 6 7}; μ_{2}; ρ_{2}; τ_{2}; τ_{3}; τ_{4}; τ_{1}; ↑; μ_{1}; ρ_{1}; Q]

balanced path, descents labeled with corresponding SIF permutation, (upsteps shown with their original numbering only as a visual aid)

The original Dyck paths can be recovered from the balanced path. In brief, the center point p of the first double rise (= consecutive pair of upsteps) identifies the initial vertex of the marked upstep. The path from p to the rightmost lowest point of Q following p is S. This works because the marked upstep was in the first component of the last Dyck path, forcing R to remain strictly above the rightmost lowest point of Q except initially. From there to the rightmost point q at p’s level is R. The descents preceding p are D_{1}, …, D_{k−1} and their lengths determine how far to proceed from q to recover P_{1}, …, P_{k−1}. The preceding outline needs a little elaboration to cover special cases. More precisely, prepend and append upsteps to Q to guarantee the existence of a double rise and the point p. If Q starts with an upstep, then p will be the origin, the list D_{1}, …, D_{k−1} will be vacuous and the original permutation σ will be connected. If p is the last point of Q, then Q will have a sawtooth shape, \/\/\/\/, and σ = identity. If n is a fixed point of σ, then the last Dyck path is empty (there is no marked upstep) and Q proceeds from p with an upstep and never drops back to the level of p. Also, of course, either one of the paths R, S may be empty.

Finally, scan all descents of the balanced path Q, recording ∅ (the empty permutation) for each zero descent and its associated unlabeled SIF permutation for each nonzero descent.

\underbrace{μ_{2} ρ_{2} ∅ τ_{2} τ_{3} ∅ τ_{4} ∅ τ_{1} ∅ ∅ ∅ μ_{1} ∅ ∅ ρ_{1}}

n-list of SIF permutations of total length n − 1

Thus we have shown that the generating function for the number a_{n} of SIF permutations on [n] is that of A075834 but to calculate values of a_{n} it is more efficient to develop a recurrence relation. Let a_{n,k} denote the number of permutations on [n] that do not stabilize any proper subinterval beginning at i for i < k. Thus a_{n,1} = n! A000142, a_{n,2} is the number of connected permutations on [n] A003319 (apart from the first term—we need to set a_{1,2} = 0), and a_{n,n} = a_{n}. Counting permutations by their first stabilized subinterval, it is straightforward to obtain the following recurrence (given in Mathematica code ).

c[0]=0; c[n_]/;n>=1 := c[n] = n!-Sum[c[i](n-i)!,{i,n-1}]
(* c[n] = # connected perms on [n] *)
a[n_,k_]/;n>=0  && k==n+1 := 0;
a[n_,1]/;n>=1 := n!;
a[n_,k_]/;2<=k<=n := a[n,k] =
   n!-Sum[c[j-i+1]a[n-(j-i+1),i],{i,k-1},{j,i,n}];

However, there is also a direct recurrence for a_{n} (vacuous sums are 0):

a_{0} = a_{1} = 1, a_{n} = ∑_{j=2}^{n−2}(j − 1)a_{j}a_{n−j} + (n − 1)a_{n−1}, n ≥ 2.

The right hand side above counts SIF permutations σ on [n] by the parameter j = n − 1 − s where s is the size of the largest proper subinterval I of [n−1] such that σ stabilizes I ∪{n}. (I is necessarily an interior subinterval of [n − 1] and may be empty.)

To see this, first note that if σ_{n−1} is SIF on [n−1] and n is inserted anywhere into a cycle of σ_{n−1} (n − 1 possible ways) to form σ ∈ S_{[n]}, then σ is also SIF. This accounts for the last term. Now suppose σ is SIF on [n] and the result σ_{n−1} ∈ S_{[n−1]} of deleting n from its cycle in σ fails to be SIF. Consider the maximal proper subintervals of [n − 1] stabilized by σ_{n−1} (necessarily disjoint, as noted above). There is at least one such by assumption and at most one, call it I, because otherwise σ itself would stabilize all but one of them, contradicting the assumption σ is SIF. Let ρ denote the restriction of σ_{n−1} to I and τ the restriction of σ_{n−1} to [n − 1]\I. Then σ is obtained from the pair ρ, τ by inserting n into a cycle of ρ, not τ, otherwise σ would stabilize I. We may write the interval I as [k + 1, n − j + k − 1] for some 1 ≤ k < j ≤ n − 2 so that the size of I is s := n − j − 1 and I is clearly the largest proper subinterval of [n − 1] such that σ stabilizes I ∪ {n}. Now τ is SIF on [n − 1]\I since τ coincides with σ on [n − 1]\I. We claim ρ′ := σ restricted to I ∪ {n} is SIF also: if ρ′ stabilized a proper subinterval of I, then σ would too, and if ρ′ stabilized a proper terminal subinterval (containing n), then σ would stabilize the corresponding initial subinterval. All told, for each j ∈ [2, n − 2], we have j − 1 choices for k and every permutation σ formed in this way from SIF permutations ρ′ on I ∪ {n} (a_{n−j} choices) and τ on [n − 1]\I (a_{j} choices) is SIF. The recurrence follows. We note that it implies the differential equation

xA′(x) = A(x) − x − \frac{x}{A(x) − 1}

for the generating function A(x).

Asymptotically, the proportion of permutations on [n] that are connected (indecomposable) is 1 − \frac{2}{n} + O(\frac{1}{n^{2}} ) [2, p. 295, Ex. 16] and there is a simple heuristic explanation: the easiest way for a permutation on [n] to be decomposable is for it to fix 1 or n and there are 2(n − 1)! − (n − 2)! permutations that do so. Far fewer permutations stabilize any other initial interval and so the dominant term in the number of decomposable permutations on [n] is 2(n − 1)!. Similarly, the easiest way for σ ∈ S_{[n]} to fail to be SIF is for it to have a fixed point. The proportion of fixed-point-free permutations on [n] is well known to be very near \frac{1}{e}, suggesting that the proportion of SIF permutations on [n] is \frac{1}{e} + O(\frac{1}{n}), and indeed computer calculations suggest it is \frac{1}{e}(1 − \frac{1}{n}) + O(\frac{1}{n^{2}} ) and maybe \frac{1}{e}(1 − \frac{1}{n} − \frac{5}{2n^{2}} ) + O(\frac{1}{n^{3}} ). It would be interesting to prove this.

References

[1] Richard P. Stanley, Exercises on Catalan and Related Numbers,

    http://www-math.mit.edu/  rstan/ec/catalan.pdf, excerpted from Enumera-

tive Combinatorics, Vol. 2, Cambridge University Press, 1999.

[2] L. Comtet, Advanced Combinatorics, D. Reidel, Boston, 1974.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A15.

Keywords: stabilized-interval-free, connected, indecomposable, noncrossing partition, Murasaki diagram, Dyck path.

(Concerned with sequences \underline{A075834}, \underline{A003319}, and \underline{A000142}.)

Received September 25 2003; revised version received March 15 2004. Published in Journal of Integer Sequences, March 15 2004.

Return to Journal of Integer Sequences home page.