0812/0812.0143.md

Title: Permutations sortable by 𝑛-4 passes through a stack

URL Source: https://arxiv.org/html/0812.0143

Markdown Content:

Permutations sortable by

n-4 passes through a stack Thanks:The first and third authors were supported by grant no. 060005013 from the Icelandic Research Fund. The second author acknowledges funding by the EC’s Research Training Network ‘Algebraic Combinatorics in Europe’, grant HPRN-CT-2001-00272 while at Université Bordeaux 1, France.

Anders Claesson, Mark Dukes and Einar Steingrímsson Address:The Mathematics Institute, Reyjavík University, 103 Reykjavík, Iceland. Address:Science Institute, University of Iceland, 107 Reykjavík, Iceland.

Abstract.

We characterise and enumerate permutations that are sortable by n-4 passes through a stack. We conjecture the number of permutations sortable by n-5 passes, and also the form of a formula for the general case n-k, which involves a polynomial expression.

1. Background

We view permutations as words without repeated letters; if \pi is a permutation of an n element set and \pi(i)=\pi_{i}, then we write \pi=\pi_{1}\dots\pi_{n}. The stack sorting operator S can be defined recursively on permutations of finite subsets of {1,2,\dots} as follows. If \pi is empty then S(\pi)=\pi. If \pi is nonempty write \pi as the concatenation \pi=LnR, where n is the greatest element of \pi and L and R are the subwords to the left and right of n respectively. Then

S(\pi)=S(L)S(R)n.

For example, S(42513)=24135. We say that a permutation \pi is k-stack sortable if S^{k}(\pi)=\mbox{id}, where S^{k}=S\circ S^{k-1}, S^{0} is the identity operator and id is the identity permutation 12\dots n. Let the (stack sorting) complexity of \pi, denoted \ssc\pi, be the smallest k such that \pi is k-stack sortable. Let \mathfrak{S}{n} be the set of permutations of {1,\dots,n}. For the permutations in \mathfrak{S}{3} we have

\begin{array}[]{rc|c|c|c|c|c}\pi;,=&123&132&213&231&312&321\ \ssc\pi;,=&0&1&1&2&1&1\end{array}

Let W_{n,k} be the set of all k-stack sortable permutations in \mathfrak{S}{n}; in other words, W{n,k} is the set of permutations in \mathfrak{S}{n} whose complexity is at most k. Let E{n,k} be the set of permutations in \mathfrak{S}_{n} whose complexity is exactly k. Note that

\displaystyle E_{n,k}\displaystyle=W_{n,k}-W_{n,k-1}; \displaystyle W_{n,k}\displaystyle=\mathfrak{S}{n}-(E{n,k+1}\cup\dots\cup E_{n,n-1}).

It is easy to see that W_{n,n-1}=\mathfrak{S}{n}. Knuth[1, 2.2.1.5] leaves as an exercise to the reader to show that W{n,1}=\mathfrak{S}_{n}(231). In his PhD thesis West [3] showed that

W_{n,2}=\mathfrak{S}_{n}(2341,3\overline{5}241),

where \mathfrak{S}{n}(2341,3\overline{5}241) is the set of permutations in \mathfrak{S}{n} that avoid the pattern 2341 and the “barred” pattern 3\overline{5}241; for information on these, see [2], especially Section 7. West also showed that W_{n,n-2} are precisely those permutations that do not have suffix n1. This last statement is easily shown by proving that the permutations in E_{n,n-1} are those with suffix n1.

In addition, West characterized E_{n,n-2}. To state that result it is convenient to introduce some notation for special sets of words over the alphabet {1,2,\dots}. Let an asterisk (\ast) stand for any word of zero or more characters, and let a question mark (\scriptstyle{?}) stand for any single letter. These conventions are adopted from the so called glob patterns in computer science. For a word w over {\mbox{$\ast$},\mbox{$\scriptstyle{?}$}}\cup{1,2,\dots}, let \langle,w,\rangle denote the set of words of the form w. For instance, \langle,\mbox{$\ast$}n1,\rangle consists of all words with suffix n1, and \mathfrak{S}_{5}\cap\langle,\mbox{$\ast$}51\mbox{$\scriptstyle{?}$},\rangle={23514,24513,32514,34512,42513,43512}. Let

\langle,w_{1},\dots,w_{k},\rangle=\langle,w_{1},\rangle\cup\dots\cup\langle,w_{k},\rangle.

West’s characterisation of E_{n,n-1} and E_{n,n-2} can then be stated as in the following two lemmas, which follow from Theorems 4.2.4 and 4.2.17 in [3] and their proofs.

Lemma 1.1.

For all n\geq 2,

E_{n,n-1}=\mathfrak{S}_{n}\cap\langle,\mbox{$\ast$}n1,\rangle.

Thus, the cardinality of E_{n,n-1} is (n-2)!.

Lemma 1.2.

For all n\geq 4,

E_{n,n-2}=\mathfrak{S}_{n}\cap\langle,;\mbox{$\ast$}n2,;\mbox{$\ast$}(n-1)1n,;\mbox{$\ast$}n1\mbox{$\scriptstyle{?}$},;\mbox{$\ast$}n\mbox{$\scriptstyle{?}$}1,;\mbox{$\ast$}n\mbox{$\ast$}(n-2)\mbox{$\ast$}(n-1)1;,\rangle.

Thus, the cardinality of E_{n,n-2} is (n-3)!(7n-12)/2.

By subtracting the cardinalities in Lemmas 1.1 and 1.2 from n!, we get the following result.

Proposition 1.3.

For all n\geq 4 the cardinality of W_{n,n-3} is

\dfrac{(n-3)!}{2}\left(2n^{3}-6n^{2}-5n+16\right).

2. Permutations requiring exactly (n-3)-stack sorts

Theorem 2.1.

For all n\geq 6, the set of permutations E_{n,n-3} are those given in column labeled “Type” of Table1. The number of such permutations is

\displaystyle\frac{(n-4)!}{3}\left(47\binom{n-6}{2}+194\binom{n-6}{1}+297\right).(2.1)

To prove this we require some terminology and results from West[3, §4.2]. A forbidden pattern of order k in a permutation \pi is a triple (B,c,a), where B is a subsequence of length k in \pi and (c,a) is a pair of entries in \pi such that for every b\in B the subsequence bca is an occurrence of the pattern 231, that is, a<b<c. In such a situation we say that the pair (c,a)_witnesses_ the forbidden pattern B. We call a forbidden pattern (B,c,a)_uninterrupted_ if there is no subsequence bxb^{\prime} in \pi where b,b^{\prime}\in B and x>c.

Lemma 2.2.

[3, Theorems 4.2.10 and 4.2.14] Let \pi be a permutation.

• (i) \ssc(\pi)\leq k if \pi does not contain any forbidden pattern of order k;

• (ii) \ssc(\pi)>k if \pi contains an uninterrupted forbidden pattern of order k.

\begin{array}[]{l|c|l}\hline\cr\hline\cr&&\[-4.30554pt] \mbox{Case}&\mbox{Type}&\mbox{Number}\[-4.30554pt] &&\ \hline\cr\hline\cr\hfil\lx@intercol\ \lx@intercol\pi_{n}=n\hfil\lx@intercol\[4.30554pt] \hline\cr&&\[-4.30554pt] \mbox{1(a)}&\mbox{$\ast$}(n-1)2n&(n-3)!\[3.44444pt] \mbox{1(b)}&\mbox{$\ast$}(n-1)\mbox{$\scriptstyle{?}$}1n&(n-3)!\[3.44444pt] \mbox{1(c)}&\mbox{$\ast$}(n-1)1\mbox{$\scriptstyle{?}$}n&(n-3)!\[3.44444pt] \mbox{1(d)}&\mbox{$\ast$}(n-1)\mbox{$\ast$}(n-3)\mbox{$\ast$}(n-2)1n&(n-3)!/2\[3.44444pt] \mbox{1(e)}&\mbox{$\ast$}(n-2)1(n-1)n&(n-4)!\[-4.30554pt] &&\ \hline\cr\hfil\lx@intercol\ \lx@intercol\pi_{n-1}=n\hfil\lx@intercol\[4.30554pt] \hline\cr&&\[-4.30554pt] \mbox{2(a)}&\mbox{$\ast$}n3&(n-2)!\[3.44444pt] \mbox{2(b)}&\mbox{$\ast$}(n-1)1n\mbox{$\scriptstyle{?}$}&(n-5)(n-4)!\[3.44444pt] \mbox{2(c)}&\mbox{$\ast$}(n-2)1n(n-1)&(n-4)!\[-4.30554pt] &&\ \hline\cr\hfil\lx@intercol\ \lx@intercol\pi_{n-2}=n\hfil\lx@intercol\[4.30554pt] \hline\cr&&\[-4.30554pt] \mbox{3(a)}&\mbox{$\ast$}n2\mbox{$\scriptstyle{?}$}&(n-3)(n-3)!\[3.44444pt] \mbox{3(b)}&\mbox{$\ast$}n\mbox{$\scriptstyle{?}$}2&(n-3)(n-3)!\[-4.30554pt] &&\ \hline\cr\hfil\lx@intercol\ \lx@intercol\pi_{n-3}=n\hfil\lx@intercol\[4.30554pt] \hline\cr&&\[-4.30554pt] \mbox{4(a)}&\mbox{$\ast$}n\mbox{$\scriptstyle{?}$}\mbox{$\scriptstyle{?}$}1,\mbox{ but not }\mbox{$\ast$}n(n-2)(n-1)1&(n-2)!-(n-4)!\[3.44444pt] \mbox{4(b)}&\mbox{$\ast$}n\mbox{$\scriptstyle{?}$}1\mbox{$\scriptstyle{?}$}&(n-2)!\[3.44444pt] \mbox{4(c)}&\mbox{$\ast$}n1\mbox{$\scriptstyle{?}$}\mbox{$\scriptstyle{?}$}&(n-2)!\[3.44444pt] \mbox{4(d)}&\mbox{$\ast$}n(n-2)(n-1)2&(n-4)!\[-4.30554pt] &&\ \hline\cr\hfil\lx@intercol\ \lx@intercol\pi_{n-i}=n\mbox{ and }i>3\hfil\lx@intercol\[4.30554pt] \hline\cr&&\[-3.87495pt] \mbox{5(a)}&\mbox{$\ast$}nA(n-2)B(n-1)2,\mbox{ where $A\cup B\neq\emptyset$}&(n-2)!/2-(n-4)!\[3.44444pt] \mbox{5(b)}&\mbox{$\ast$}n\mbox{$\ast$}(n-3)\mbox{$\ast$}(n-1)(n-2)1&(n-3)!/2\[3.44444pt] \mbox{5(c)}&\mbox{$\ast$}n\mbox{$\ast$}(n-1)\mbox{$\ast$}(n-3)\mbox{$\ast$}(n-2)1&(n-2)!/6\[3.44444pt] \mbox{5(d)}&\mbox{$\ast$}(n-1)\mbox{$\ast$}n\mbox{$\ast$}!\left{!!!\begin{array}[]{c}(n-3)\mbox{$\ast$}(n-4)\ (n-4)\mbox{$\ast$}(n-3)\end{array}!!!\right}!\mbox{$\ast$}(n-2)1&(n-2)!/12\[8.61108pt] \mbox{5(e)}&\mbox{$\ast$}n\mbox{$\ast$}(n-2)\mbox{$\ast$}(n-1)!\left{!!!\begin{array}[]{c}1\mbox{$\scriptstyle{?}$}\ \mbox{$\scriptstyle{?}$}1\end{array}!!!\right}&(n-4)(n-3)!\[8.61108pt] \mbox{5(f)}&\mbox{$\ast$}n\mbox{$\ast$}(n-3)\mbox{$\ast$}(n-1)1(n-2)&(n-3)!/2\[3.44444pt] \mbox{5(g)}&\mbox{$\ast$}n\mbox{$\ast$}(n-3)\mbox{$\ast$}(n-2)1(n-1)&(n-3)!/2\[3.44444pt] \mbox{5(h)}&\mbox{$\ast$}(n-2)\mbox{$\ast$}n\mbox{$\ast$}!\left{!!!\begin{array}[]{c}(n-3)\mbox{$\ast$}(n-4)\ (n-4)\mbox{$\ast$}(n-3)\end{array}!!!\right}!\mbox{$\ast$}(n-1)1&(n-2)!/12\[-4.30554pt] &&\ \hline\cr\end{array}

Table 1. Permutations in E_{n,n-3}

Proof of Theorem2.1.

Let \pi\in\mathfrak{S}{n}. Using the contrapositive of (i) and (ii) in Lemma2.2, if \ssc(\pi)=n-3, then \pi contains a forbidden pattern of order n-4 and does not contain an uninterrupted forbidden pattern of order n-3. The forbidden pattern of order n-4 must be witnessed by entries that appear in some two of the positions n-3, n-2, n-1 or n of the permutation. We will first condition on the position of the largest entry in the permutations, then condition on those permutations that contain a forbidden pattern of the required order, and finally single out those permutations that are in E{n,n-3}.

Suppose \pi_{n}=n. A permutation \pi=\pi^{\prime}n is a member of E_{n,n-3} precisely when \pi^{\prime} is a member of E_{n-1,n-3}. Thus entries 1(a)–1(e) of Table1 immediately follow from Lemma1.2.

Suppose \pi_{n-1}=n. We must have \pi_{n}\geq 3, for otherwise, by Lemmas1.1 and1.2, we would have \pi\in E_{n,n-1} or \pi\in E_{n,n-2}. If \pi_{n}=3 then the permutation is in E_{n,n-3}, and hence we get 2(a). If k=\pi_{n}>3 then it is impossible for (n,k) to witness a forbidden pattern F of order n-4 since there could be at most n-k-1<n-4 elements in F. Thus the forbidden pattern F must be witnessed by (\pi_{n-3},\pi_{n-2}). As there are now n-2 values from which to form the forbidden pattern F, we are forced to choose the extreme values from this set as the values for (\pi_{n-3},\pi_{n-2}). Consequently, if k=n-1 then we must have (\pi_{n-3},\pi_{n-2})=(n-2,1), giving case 2(c). Otherwise 3<k<n-1 and (\pi_{n-3},\pi_{n-2})=(n-1,1) which gives case 2(b). One easily verifies that all such permutations are in E_{n,n-3}.

Suppose \pi_{n-2}=n. By Lemma1.2 the value 1 cannot be to the right of n. Let k be the smaller of the two values \pi_{n-1} and \pi_{n}. If k>2 then the pair (n,k) witnesses a forbidden pattern of order at most n-k-1-1,<,n-4. For the same reason, (\pi_{n-1},\pi_{n}) cannot witness a forbidden pattern of order n-4. So exactly one of the entries to the right of n must be 2, giving 3(a) and (b). One easily verifies that all such permutations are in E_{n,n-3}.

Suppose \pi_{n-3}=n. If 1 is to the right of n in \pi then (n,1) witnesses a forbidden pattern of order n-4. However, if \pi\in\langle,\mbox{$\ast$}n(n-2)(n-1)1,\rangle, it has one of the forms given in Lemma1.2. In all other cases the permutation is in E_{n,n-3}. This gives 4(a), (b) and (c).

Alternatively, if 1 is to the left of n, let k be the value of the smallest entry to the right of n. Since there are at most n-5 entries to the left of n in \pi that take values between k and n, the pair (n,k) cannot witness a forbidden pattern of order n-4. In order for \pi to contain a forbidden pattern F of order n-4 it must be witnessed by the pair (\pi_{n-1},\pi_{n}) and have as the block of n-4 values the value \pi_{n-2} along with the n-5 elements to the left of n that are not 1. Thus \pi_{n}=2, \pi_{n-1}=n-1 and

\pi\in\langle,\mbox{$\ast$}nk(n-1)2,\rangle

for some k\neq 1. One easily checks that the only value of k for which \pi\in E_{n,n-3} is k=n-2. This gives 4(d).

Suppose \pi_{n-i}=n for some i>3. Then (n,k) can never witness a forbidden pattern of order n-4. In the remainder of the proof, we condition on the relative positions of (n-2), (n-1) and n. If \pi=AnB(n-1)C(n-2)D where |B\cup C\cup D|\geq 2, then

S(\pi)=S(A)S(B)S(C)S(D)(n-2)(n-1)n.

This gives

\displaystyle{\pi\in E_{n,n-3}}\displaystyle\iff S(A)S(B)S(C)S(D)\in E_{n-3,n-4} \displaystyle\iff S(A)S(B)S(C)S(D)\in\langle,*(n-3)1,\rangle.

Since |B\cup C\cup D|\geq 2, the ways in which this can happen are restricted to

• (i) D=1 and n-3\in C, giving case 5(c),

• (ii) D=1, C=\emptyset and n-3\in B, giving case 5(b),

• (iii) D=\emptyset, C=1 and n-3\in B, giving case 5(f).

If \pi=AnB(n-2)C(n-1)D where |B\cup C\cup D|\geq 2, then

S(\pi)=S(A)S(B)S(C)(n-2)S(D)(n-1)n.

This implies that \pi belongs to E_{n,n-3} if and only if

S(A)S(B)S(C)(n-2)S(D)\in E_{n-2,n-4}.

If D=\emptyset then \pi belongs to E_{n,n-3} if and only if S(A)S(B)S(C) belongs to E_{n-3,n-4}, which happens if and only if C=1 and (n-3)\in B, from which we get 5(g). Otherwise S(A)S(B)S(C)(n-2)S(D) belongs to the types listed in Lemma1.2. There are 3 cases to consider:

• (i) S(D)=2, so \pi=AnB(n-2)C(n-1)2 where B\cup C\neq\emptyset, giving case 5(a);

• (ii) S(D)=1k, so D=1k or D=k1, giving case 5(e); and

• (iii) it is not possible that S(A)S(B)S(C)(n-2)S(D) matches the last type in Lemma1.2 since this would mean that S(D) ends in 1, its smallest entry.

If \pi=A(n-1)BnC(n-2)D where |C\cup D|\geq 3, then a forbidden pattern of order n-4 can only be witnessed by the pair (n-2,1). Furthermore, all elements 2 through n-3 must be to the left of n-2, so \pi_{n-1}=n-2 and \pi_{n}=1, that is \pi=A(n-1)BnC(n-2)1 where |C|\geq 2. From this we have S^{2}(\pi)=S(S(A)S(B))S(S(C)1)(n-2)(n-1)n and

\displaystyle\pi\in E_{n,n-3}\displaystyle\iff\pi^{\prime}=S(S(A)S(B))S(S(C)1)\in E_{n-3,n-5}.

The conditions on \pi^{\prime} (and therefore \pi) are easily derived by comparing \pi^{\prime} to the types in Lemma1.2. Since |C|\geq 2 one cannot have (n-3)2 as a suffix of S(S(C)1). Similarly, (n-3)1k and (n-3)k1 cannot be suffixes of S(S(C)1). Also, it is only possible that

\pi^{\prime}\in\langle,\mbox{$\ast$}(n-3)\mbox{$\ast$}(n-5)\mbox{$\ast$}(n-4)1,\rangle

if C=\emptyset, which is not allowed. The only possibility for \pi^{\prime} is that it has (n-4)1(n-3) as a suffix, and so n-4,n-3\in C since |C|\geq 2. Under these conditions, S^{2}(\pi) has suffix (n-4)1(n-3)(n-2)(n-1)n and \pi\in E_{n,n-3}. Thus D=1 and n-4,n-3\in C, from which we get case 5(d).

If \pi=A(n-2)BnC(n-1)D where |C\cup D|\geq 3 then

S(\pi)=S(A)S(B)(n-2)S(C)S(D)(n-1)n.

Now, \pi belongs to E_{n,n-3} if and only if \pi^{\prime}=S(A)S(B)(n-2)S(C)S(D) belongs to E_{n-2,n-4}. Since |C\cup D| is at least 3, the entry n-2 has at least 3 entries to its right in \pi^{\prime}. By comparing this to the possible types that it may take in Lemma1.2, we find that the only possibility is

\pi^{\prime}\in\langle,\mbox{$\ast$}(n-2)\mbox{$\ast$}(n-4)\mbox{$\ast$}(n-3)1,\rangle.

This happens if and only if D=1 and n-4,n-3\in C, which gives case 5(h).

For the two final cases in which n-2 and n-1 are to the left of n, it is not possible for \pi to contain a forbidden pattern of order n-4, since at least one of n-2, n-1 and n is needed in order to witness such a pattern, and none of them are in the rightmost four positions of the permutation.

The number of permutations of each type is shown in column three of Table1. Adding these gives (47n^{2}-223n+240)(n-4)!/6 which may be be rewritten as in formula (2.1). ∎

Corollary 2.3.

For n\geq 6, the collection of (n-4)-stack sortable permutations in \mathfrak{S}_{n} are those permutations that are not of the types listed in Lemma1.1, Lemma1.2 or Table1. The number of these is (n-4)!(3n^{4}-18n^{3}-4n^{2}+158n-192)/3.

It is now straightforward to write down (a lengthy expression for) the descent polynomial of the (n-4)-stack sortable permutations, that is, the polynomial whose k-th coefficient is the number of (n-4)-stack sortable permutations with exactly k descents (a descent in \pi=a_{1}a_{2}\dots a_{n} is an i such that a_{i}>a_{i+1}).

The following conjecture is based on computer generated data for n\leq 13.

Conjecture 2.4.

For all n\geq 8, the number of permutations in E_{n,n-4} is

\frac{(n-5)!}{10}\left(854\binom{n-8}{3}+5099\binom{n-8}{2}+12545\binom{n-8}{1}+16130\right),

or equivalently, the number of (n-5)-stack sortable permutations is

\frac{(n-5)!}{60}\left(60n^{5}-600n^{4}+506n^{3}+11241n^{2}-38369n+34236\right).

We end with a conjecture about the form of an expression for the number of permutations needing exactly n-k stack sorts. This has been verified for all n\leq 14 and all relevant k.

Conjecture 2.5.

For all n\geq 2k, the number of permutations in E_{n,n-k} may be written as

\frac{(k-1)!(n-k-1)!}{\big(2(k-1)\big)!}\sum_{i=0}^{k-1}a_{i}\binom{n-2k}{i}

where a_{i}\in\mathbb{N}.

References

• [1] D. E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Addison Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969.
• [2] E. Steingrímsson: Generalized permutation patterns — a short survey, “Permutation Patterns, St Andrews 2007,” S.A. Linton, N. Ruskuc, V. Vatter (eds.), LMS Lecture Note Series, Cambridge University Press, to appear.
• [3] J. West, Permutations with forbidden subsequences; and, Stack sortable permutations, Ph.D. thesis, Massachusetts Institute of Technology, 1990.