Deterministic stack-sorting for set partitions

We show directly what happens to input sock sequence $p=x^{l_{1}}s_{1}x^{l_{2}}s_{2}\cdots x^{l_{m}}s_{m}x^{l_{m+1}}$. By definition, we first push the first $l_{1}$ occurrences of $x$ onto the stack. We then have the following for all $i\in[m-1]$. We i) push all socks in $s_{i}$ onto the stack, which only contains $l_{1}+\cdots+l_{i}$ occurrences of $x$. This results in $s_{i}$ getting sorted by $\phi_{aba}$ independently, since $s_{i}$ contains no occurrences of $x$ and therefore does not interact with the occurrences of $x$ at the bottom of the stack. We then ii) must pop all remaining socks in $s_{i}$ in the stack before pushing the next occurrences of $x$, to avoid having the pattern $aba$ occur in the stack. Finally, we iii) push the next $l_{i+1}$ consecutive occurrences of $x$ in our input. After $m-1$ rounds of this process, we are left with $s_{m}x^{l_{m+1}}$ in our input, $\phi_{aba}(s_{1})\cdots\phi_{aba}(s_{m-1})$ in our output, and exactly $l_{1}+\cdots+l_{m}$ occurrences of $x$ on our stack. Again, we push all socks in $s_{m}$ and independently sort them. If $l_{m+1}=0$, we finally pop all remaining socks in $s_{m}$ in the stack and all $l_{1}+\cdots+l_{m}$ occurrences of $x$ at the bottom of the stack, giving us $\phi_{aba}(s_{1})\cdots\phi_{aba}(s_{m})x^{l_{1}+\cdots+l_{m}}$ as our final output. If $l_{m+1}>0$, we pop all remaining socks in $s_{m}$ in the stack before pushing the next $l_{m+1}$ occurrences of $x$, and finally pop all $l_{1}+\cdots+l_{m+1}$ occurrences of $x$ in the stack to obtain $\phi_{aba}(s_{1})\phi_{aba}(s_{2})\cdots\phi_{aba}(s_{m})x^{l_{1}+\cdots l_{m+1}}$. Thus our output always becomes $\phi_{aba}(s_{1})\phi_{aba}(s_{2})\cdots\phi_{aba}(s_{m})x^{l_{1}+\cdots+l_{m+1}}$, as desired. ∎

Say that a sock is clumped if all occurrences of that sock appear consecutively. Then we can see that any sock that is clumped stays clumped under $\phi_{aba}$; if we can push one of the clumped socks onto the stack and avoid the pattern $aba$, then we can push all of them onto the stack. Likewise, once we must pop a clumped sock out of the stack, then all of the socks can constitute the last sock in the pattern $aba$, so they must all be popped out together.

We claim that each application of $\phi$ adds at least one more clumped sock. In particular, if the first sock $x$ is not clumped, then by Lemma 3.1, one application of $\phi_{aba}$ clumps together all occurrences of sock $x$ and sends them to the back of the output sock sequence. If the first sock $x$ is already clumped, then we have $p=x\cdots xq$ where $q$ is some sock sequence. Then $\phi_{aba}(p)=\phi(q)x\cdots x$, and we can use the same argument on $q$. Thus, the first sock that is not already clumped becomes clumped under $\phi_{aba}$. Because socks that are clumped stay clumped in any subsequent application of $\phi_{aba}$, we need at most $n$ stacks to sort $p$.

To show that this bound is tight for any $n$, consider the sock sequence $p^{*}=a_{1}\cdots a_{n}a_{1}\cdots a_{n}$ where $a_{i}$ is a sock for all $i\in[n]$ and $p^{*}$ contains exactly two copies of each distinct sock $a_{i}$. We will show that $p^{*}$ is not $(n-1)$-sortable under $\phi_{aba}$. To do so, we claim that the after $k$ iterations of $\phi_{aba}$ for, our sock sequence becomes $X_{1}qX_{2}qX_{3}$ where $q$ is a sock sequence of length $|q|=n-k$ containing only single occurrences of socks, and $X_{1},X_{2}$, and $X_{3}$ are sock sequences of lengths $|X_{1}|=2\left\lfloor\frac{k}{3}\right\rfloor,|X_{2}|=2\left\lfloor\frac{k+1}{3}\right\rfloor$ and $|X_{3}|=2\left\lfloor\frac{k+2}{3}\right\rfloor$. We prove this by induction on $k$.

Our base case is easily verifiable; $\phi_{aba}((a_{1}\cdots a_{n})^{2})=a_{n}\cdots a_{2}a_{n}\cdots a_{2}a_{1}a_{1})$, which we can rewrite in the form $X_{1}qX_{2}qX_{3}$ where $X_{1}$ and $X_{2}$ are empty, $X_{3}=a_{1}a_{1}$, and $q=a_{n}\cdots a_{2}$, which are all of the correct form. Now we assume our hypothesis holds up to iteration $k$, and show that it remains true after iteration $k+1$. Indeed, if we write $q=aq^{\prime}$, we have

which we can rewrite as $X_{1}^{\prime}q^{\prime}X_{2}^{\prime}q^{\prime}X_{3}^{\prime}$, where $X_{1}^{\prime}=\overline{X_{2}}$, $X_{2}^{\prime}=\overline{X_{3}}$, and $X_{3}^{\prime}=aa\overline{X_{1}}$. Then we can verify that $|X_{1}^{\prime}|=|X_{2}|=2\left\lfloor\frac{k+1}{2}\right\rfloor$, $|X_{2}^{\prime}|=|X_{3}|=2\left\lfloor\frac{k+2}{2}\right\rfloor$, $|X_{3}^{\prime}|=2+2\left\lfloor\frac{k}{3}\right\rfloor=2\left\lfloor\frac{k+3}{3}\right\rfloor$, and $q=n-k-1$, as desired.

Given the claim, we now have that $X_{2}$ is nonempty for all sufficiently large $k$. The $X_{1}qX_{2}qX_{3}$ cannot be sorted until $q$ is empty, which takes at least $n$ iterations as desired. ∎

We use Lemma 3.1. Let $p=x^{l_{1}}s_{1}x^{l_{2}}s_{2}\cdots x^{l_{m}}s_{m}x^{l_{m+1}}$ be a $1$-stack-sortable sock pattern under $\phi_{aba}$ where $x\notin s_{i}$ for any $i\in[m]$. Note that in order for

to be sorted, we must have that for all $i\in[m]$, each $s_{i}$ individually is a $1$-stack-sortable sock pattern under $\phi_{aba}$.

Then given any fixed $s_{i}$, we only need to consider their relationship to each other in the full sock pattern. In particular, we claim that for any $l_{1},l_{2}>0$ and nonempty sock patterns $s_{1},s_{2}$ that are each $1$-stack-sortable under $\phi_{aba}$, there are exactly two possible sock patterns $x^{l_{1}}s_{1}x^{l_{2}}s_{2}$ that are $1$-stack-sortable under $\phi_{aba}$. To see this, we must have $|C(s_{i})\cap C(s_{i+1})|\leq 1$, as otherwise the subsequence $\phi_{aba}(s_{i})\phi_{aba}(s_{i+1})$ in $\phi_{aba}(p)$ contains either $abab$ or $abba$ as a subsequence and is not sorted. We then consider the following two cases:

1. i)

   If $|C(s_{1})\cap C(s_{2})|=0$, then there is exactly one way to assign sock names to $s_{1}$ and $s_{2}$ up to standardization. Namely, we can assign any sock names such that the socks in $s_{1}$ and $s_{2}$ are disjoint, and then standardize.

2. ii)

   If $|C(s_{1})\cap C(s_{2})|=1$, then again there is exactly one way to assign sock names to $s_{1}$ and $s_{2}$ up to standardization. Namely, we assign the same name to the last element that appears in $\phi_{aba}$ and to the first element that appears in $\phi_{aba}(s_{2})$, and consider all other socks in $s_{1}$ and $s_{2}$ disjoint.

Then we can see that up to equivalence, $p$ is determined by the sock patterns $s_{i}$ together with the choice for $1\leq i\leq m-1$ of whether or not $s_{i}$ and $s_{i+1}$ share a sock, for a total of $2^{m-1}$ choices. We can now consider the cases where $m=0$ and $m\geq 1$ separately, which allows us to write the following relation on $P(x)$:

To see why Equation 1 holds, we can consider the coefficient of $x^{n}$ for any $n\in\mathbb{Z}_{\geq 0}$. On the left-hand side, this is $s(n)$ by definition. On the right-hand side, we have two main terms. The first term $\frac{x}{1-x}=\sum_{n\geq 1}1x^{n}$ counts the unique sock pattern with length $n$ that is $1$-stack-sortable under $\phi_{aba}$ when $m=0$, namely $p=x\cdots x$. The second term contributes a sum of $2^{m-1}s(n_{1})s(n_{2})\cdots s(n_{m})$ over all possible lengths $n_{1},\dots,n_{m},l_{1},\dots,l_{m+1}$ with $n_{i}>0$ for $i\in[m]$ and $l_{i}>0$ such that $n_{1}+\cdots+n_{m}+l_{1}+\cdots+l_{m}=n$. This counts the number of sock patterns that are $1$-stack-sortable under $\phi_{aba}$ when $m\geq 1$, since we can take any nonempty sock patterns $s_{i}$ that are independently $1$-stack-sortable under $\phi_{aba}$ and append them in $2^{m-1}$ ways.

Given Equation 4, one can now easily solve the quadratic in $P(x)$ to obtain the closed form

as desired. ∎

For any power series $f$ and $n\geq 0$, let $[x^{n}]\{f(x)\}$ denote the coefficient of $x^{n}$ in the series $f(x)$. We wish to find asymptotics for $s(n)=[x^{n}]\{P(x)\}$.

Let $P^{*}(x):=\frac{\sqrt{1-6x+7x^{2}-2x^{3}+x^{4}}}{4(x^{2}-x)}$. Note that to obtain asymptotics for $s(n)$, it suffices to compute asymptotics for the coefficients of the power series of $P^{*}(x)$ at $x=0$, since we can verify that

contributes only constant terms to $s(n)$.

In particular, we define $Q(x):=P^{*}(x_{0}x)$, where $x_{0}$ is the smallest positive root of $1-6x+7x^{2}-2x^{3}+x^{4}=0$ (and thus the singularity of $P^{*}(x)$ with smallest magnitude). Then we have that the smallest singularity of $Q(x)$ occurs at $x=1$, so we can write $Q(x)=(1-x)^{\beta}R(x)$ where $\beta=\frac{1}{2}$ and $R(x)$ is analytic in some disk $|x|<1+\varepsilon$ where $\varepsilon>0$. Let $R(x)=\sum_{j=0}^{\infty}r_{j}(1-x)^{j}$. Then Darboux’s Theorem [8, 23] tells us that

Plugging in $m=0$ and $\beta=\frac{1}{2}$ gives us

Note that $r_{0}=R(1)$, which is well-defined and computable. We can also compute $[x^{n}]\{(1-x)^{1/2}\}$ using Stirling’s approximation as follows:

Thus, we have

where $K=-\frac{R(1)}{\sqrt{4\pi}}=0.34313\cdots$ is a constant, $c=\frac{1}{x_{0}}$, and $x_{0}=\frac{1}{2}\left(1-\sqrt{8\sqrt{2}-11}\right)$ is the smallest solution to $1-6x+7x^{2}-2x^{3}+x^{4}=0$, as desired. ∎

Let $s(n,r)$ denote the number of sock patterns of length $n$ that are $1$-stack-sortable under $\phi_{aba}$ and have $r$ distinct socks. Again, for $p=x^{l_{1}}s_{1}x^{l_{2}}s_{2}\cdots x^{l_{m}}s_{m}x^{l_{m+1}}$ to be $1$-stack-sortable, we must have that $s_{i}$ are individually $1$-stack-sortable under $\phi_{aba}$ for all $i\in[m]$ (where the $s_{i}$ are potentially nonempty). Furthermore, if $p$ has $r$ distinct socks, then we have to choose how to cover those $r$ socks across the $m$ sock patterns $s_{1},\dots,s_{m}$.

We again split into two cases. When $m=0$, we have that there is exactly one sock pattern of length $n$ that is $1$-stack-sortable under $\phi_{aba}$, namely $p=x^{n}$. This pattern contains one distinct sock, so we can capture these sock patterns in the sum $\sum_{n>0}x^{n}q^{1}=\frac{qx}{1-x}$.

Now suppose $m>0$, so we have a nonzero number of nonempty sock patterns $s_{i}$. Suppose $s_{i}$ has length $n_{i}>0$ and $r_{i}>0$ distinct socks for $i\in[m]$. For each nonempty $s_{i}$, we can again either choose to i) have the first sock of $\phi_{aba}(s_{i})$ be the same as the last sock of $\phi_{aba}(s_{i-1})$, or ii) have $\phi_{aba}(s_{i})$ (and therefore $s_{i}$) have disjoint socks from $\phi_{aba}(s_{i-1})$. In the former, the total number of distinct socks added by appending $s_{i}$ is $r_{i}-1$, and in the latter, the total number of distinct socks added by adding $s_{i}$ is $r_{i}$. Thus, our contributions to $P_{[q]}(x)$ look like the product of either $s(n_{i},r_{i})x^{n_{i}}q^{r_{i}}$ or $s(n_{i},r_{i})x^{n_{i}}q^{r_{i}-1}$ terms over all $i\in[m]$, which we can factor as $P_{[q]}(x)^{m}(1+q^{-1})^{m}$. We can thus write the following relation on $P_{[q]}(x)$: