TAOCP 2.2.1 Exercise 4
Let $a_n$ denote the number of permutations of ${1,2,\ldots,n}$ obtainable by a stack of the type described in exercise 2.
Section 2.2.1: Stacks, Queues, and Deques
Exercise 4. [M34] Find a simple formula for $a_n$, the number of permutations on $n$ elements that can be obtained with a stack like that in exercise 2.
Verified: no
Solve time: -
Setup
Let $a_n$ denote the number of permutations of ${1,2,\ldots,n}$ obtainable by a stack of the type described in exercise 2. By exercise 3, each obtainable permutation corresponds to a unique admissible sequence of stack operations consisting of $n$ symbols S and $n$ symbols X, where every initial segment contains at least as many S's as X's.
The problem is to find a simple formula for $a_n$.
An admissible sequence may be viewed as a lattice path from $(0,0)$ to $(n,n)$, where S is represented by a horizontal step $(1,0)$ and X by a vertical step $(0,1)$. The admissibility condition means that at every point of the path, the number of X's never exceeds the number of S's; hence the path never rises above the diagonal $y=x$.
Therefore $a_n$ is the number of lattice paths from $(0,0)$ to $(n,n)$ that never pass above the line $y=x$.
Solution
The total number of unrestricted paths from $(0,0)$ to $(n,n)$ equals the number of ways to arrange $n$ horizontal and $n$ vertical steps:
$$ \binom{2n}{n}. $$
To count the admissible paths, subtract the bad paths, namely those that pass above the diagonal $y=x$.
A bad path has a first point at which it enters the region $y>x$. At this first crossing, the path contains a step from a point $(k,k)$ to $(k,k+1)$ for some $0\le k<n$. Reflect the portion of the path up to and including this crossing across the diagonal $y=x$.
This reflection transforms a bad path from $(0,0)$ to $(n,n)$ into a path from $(-1,1)$ to $(n,n)$, since the first offending vertical step becomes a horizontal step and the endpoint of the reflected initial segment moves from $(k,k+1)$ to $(k+1,k)$.
Translating coordinates by $(1,-1)$, the number of such reflected paths equals the number of unrestricted paths from $(0,0)$ to $(n+1,n-1)$. Such a path contains $n+1$ horizontal steps and $n-1$ vertical steps, hence their number is
$$ \binom{2n}{n-1}. $$
The reflection process is reversible, so this gives a bijection between bad paths and unrestricted paths from $(0,0)$ to $(n+1,n-1)$.
Therefore
$$ a_n = \binom{2n}{n} - \binom{2n}{n-1}. $$
Using
$$ \binom{2n}{n-1} = \frac{n}{n+1}\binom{2n}{n}, $$
we obtain
$$ a_n = \left(1-\frac{n}{n+1}\right)\binom{2n}{n} = \frac{1}{n+1}\binom{2n}{n}. $$
Thus the number of stack-obtainable permutations is
$$ \boxed{ a_n=\frac{1}{n+1}\binom{2n}{n} }. $$
These are the Catalan numbers.
Verification
For $n=1$, the only permutation is $1$, and
$$ a_1=\frac{1}{2}\binom{2}{1}=1. $$
For $n=2$, the obtainable permutations are $12$ and $21$, giving
$$ a_2=\frac{1}{3}\binom{4}{2}=2. $$
For $n=3$, the formula gives
$$ a_3=\frac{1}{4}\binom{6}{3}=5. $$
The five obtainable permutations are
$$ 123,\quad 132,\quad 213,\quad 231,\quad 321, $$
while $312$ is impossible since producing $3$ first forces $2$ to lie above $1$ in the stack, making $1$ unavailable before $2$. Hence the formula agrees with direct enumeration.
Notes
The admissible sequences of exercise 3 are in one-to-one correspondence with balanced parenthesis systems of length $2n$ and with lattice paths below the diagonal. The numbers
$$ \frac{1}{n+1}\binom{2n}{n} $$
occur in many combinatorial problems and are known as the Catalan numbers.