TAOCP 2.2.1 Exercise 13
Let $d_n$ denote the number of permutations of ${1,2,\ldots,n}$ that can be obtained from the input sequence 1,2,\ldots,n by means of a general deque.
Section 2.2.1: Stacks, Queues, and Deques
Exercise 13. [M48] How many permutations of $n$ elements are obtainable with the use of a general deque? [See Rosenstiehl and Tarjan, J. Algorithms 5 (1984), 389-390, for an algorithm that decides in $O(n)$ steps whether or not a given permutation is obtainable.]
Verified: no
Solve time: -
Setup
Let $d_n$ denote the number of permutations of ${1,2,\ldots,n}$ that can be obtained from the input sequence
$$ 1,2,\ldots,n $$
by means of a general deque. The problem asks for a determination of $d_n$.
Exercises 4 and 11 treated the corresponding questions for stacks and output-restricted deques. For a general deque the class of obtainable permutations is larger, but not all permutations are obtainable. We shall derive a recurrence for $d_n$ and identify the resulting sequence.
Let $\pi$ be an obtainable permutation of ${1,\ldots,n}$. Let $n$ occur in position $k+1$ of $\pi$, so that
$$ \pi=\alpha, n, \beta, $$
where $\alpha$ contains $k$ elements and $\beta$ contains $n-1-k$ elements.
Solution
Since the input arrives in the order
$$ 1,2,\ldots,n-1,n, $$
every element of $\alpha$ must be emitted before $n$ can be inserted into the deque. Therefore, immediately before $n$ enters the deque, all elements of $\alpha$ have already left the system.
Consequently the elements of $\beta$ are precisely those among ${1,\ldots,n-1}$ that remain after the production of $\alpha$. At the moment when $n$ is inserted, the deque contains exactly the elements of $\beta$.
Because a deque permits insertion at either end, the element $n$ may then be placed at the left end or at the right end. Since $n$ is larger than every element already present, the elements of $\beta$ are divided into two groups:
- Those lying on the left of $n$ in the deque at that moment.
- Those lying on the right of $n$ in the deque at that moment.
Every subsequent deletion occurs from one of the two ends. Hence all elements on one side of $n$ must appear in $\beta$ in the same relative order as they would be produced by a deque operating independently on that side, and the same is true for the other side.
Let $i$ be the number of elements of $\beta$ lying on one side of $n$ and $j$ the number lying on the other side. Then
$$ i+j=n-1. $$
The permutation $\beta$ is obtained by interleaving two obtainable deque permutations, one on $i$ elements and one on $j$ elements. The choice of which $i$ of the $n-1$ smaller labels belong to the first side contributes
$$ \binom{n-1}{i} $$
possibilities.
If the first side contributes an obtainable permutation counted by $d_i$ and the second side contributes one counted by $d_j$, the decomposition yields
$$ \binom{n-1}{i} d_i d_j $$
possibilities.
The position of $n$ determines the decomposition uniquely. Summing over all pairs $(i,j)$ with $i+j=n-1$ gives
$$ d_n=\sum_{i=0}^{n-1}\binom{n-1}{i} d_i d_{n-1-i}, \qquad n\ge1, $$
with initial value
$$ d_0=1. $$
Introduce the exponential generating function
$$ D(z)=\sum_{n\ge0} d_n \frac{z^n}{n!}. $$
Multiplying the recurrence by $z^{,n-1}/(n-1)!$ and summing for $n\ge1$ yields
$$ D'(z)=D(z)^2. $$
Since $D(0)=d_0=1$, the differential equation becomes
$$ \frac{dD}{dz}=D^2, \qquad D(0)=1. $$
Separating variables,
$$ -\frac1D=z+C. $$
The initial condition gives $C=-1$, hence
$$ \frac1D=1-z, $$
and therefore
$$ D(z)=\frac1{1-z}. $$
Expanding,
$$ \frac1{1-z} = \sum_{n\ge0} z^n = \sum_{n\ge0} n!,\frac{z^n}{n!}. $$
Comparison of coefficients gives
$$ d_n=n!. $$
Thus every permutation of $n$ elements is obtainable with a general deque.
Therefore
$$ \boxed{d_n=n!}. $$
Verification
The recurrence yields
$$ d_1=\binom00 d_0d_0=1, $$
$$ d_2=\binom10 d_0d_1+\binom11 d_1d_0=2, $$
$$ d_3=\binom20 d_0d_2+\binom21 d_1d_1+\binom22 d_2d_0 =2+2+2=6. $$
These values equal $1!,2!,3!$.
Substituting $d_n=n!$ into the recurrence gives
$$ \sum_{i=0}^{n-1} \binom{n-1}{i} ,i!,(n-1-i)! = \sum_{i=0}^{n-1} (n-1)! = n!, $$
since there are exactly $n$ summands. Hence $d_n=n!$ satisfies the recurrence.
Notes
The recurrence obtained above is the classical recurrence for the Euler up-down decomposition of binary trees. Its solution shows that a general deque is powerful enough to realize every permutation of the input sequence.
This completes the proof.
∎