TAOCP 2.2.1 Exercise 9

Section 2.2.1: Stacks, Queues, and Deques

Exercise 9. [M20] Let $b_n$ be the number of permutations on $n$ elements obtainable by the use of an input-restricted deque. (Note that $b_4 = 22$, as shown in exercise 7.) Show that $b_n$ is also the number of permutations on $n$ elements with an output-restricted deque.

Verified: no
Solve time: -

Solution

We denote by $b_n$ the number of permutations on $n$ elements obtainable with an input-restricted deque. By definition, an input-restricted deque allows insertion at only one end, say the left end, but permits deletion at either end. Symmetrically, an output-restricted deque allows deletion at only one end, say the left end, but permits insertion at either end. The claim is that these two sets of permutations have the same cardinality, $b_n$.

Consider an input-restricted deque. Let the input sequence be $1,2,\ldots,n$. The deque operates according to the rules: insertions only at the left end, deletions from either end. At any stage, let $k$ elements currently reside in the deque. Denote these elements in left-to-right order as $D_1,D_2,\ldots,D_k$, where $D_1$ is the leftmost element. Inserting a new element $x$ appends it to the left end: $D_1\Leftarrow x$. A deletion may remove either $D_1$ or $D_k$.

For the output-restricted deque, insertions are allowed at either end, while deletions are allowed only at one end, say the left end. Let the current elements be $E_1,E_2,\ldots,E_k$ in left-to-right order, with deletions allowed only from $E_1$.

We define a bijection between sequences of operations in the input-restricted and output-restricted deques as follows. Let the input-restricted deque sequence be given by a string of operations: $I$ for insertion (always at the left end), $L$ for deletion from the left, $R$ for deletion from the right. Map each $I$ to a deletion in the output-restricted deque: if the output-restricted deque allows insertion at both ends and deletion only at the left, we can simulate an insertion at the left in the input-restricted deque by inserting at the left in the output-restricted deque, and similarly for the right deletions. More explicitly, consider the following procedure:

1. Reverse the order of the input elements $1,2,\ldots,n$ to $n,n-1,\ldots,1$.
2. For each insertion in the input-restricted deque, perform a deletion in the output-restricted deque.
3. For each deletion in the input-restricted deque, perform an insertion at the corresponding end in the output-restricted deque.

This mapping preserves the output permutation: the sequence of elements removed from the deque in the input-restricted case becomes exactly the sequence of elements inserted in the output-restricted case. Conversely, any permutation obtained with an output-restricted deque can be mapped to an input-restricted deque in the same manner. Therefore, the sets of obtainable permutations are in bijective correspondence.

As an alternative argument, note that an input-restricted deque is equivalent to a stack with a single additional allowed deletion at the rear. The output-restricted deque is similarly a stack with a single additional insertion at the rear. By symmetry, the number of obtainable permutations depends only on the relative positions of the operations, not on which end is restricted. Therefore $b_n$ counts both cases.

Thus, the number of permutations obtainable with an input-restricted deque is equal to the number obtainable with an output-restricted deque. This completes the proof.

∎