TAOCP 2.2.1 Exercise 11

Section 2.2.1: Stacks, Queues, and Deques

Exercise 11. [M40] As a consequence of exercises 9 and 10, the number $b_n$ is the number of admissible sequences of length $2n$. Find a closed form for the generating function $\sum_{n \ge 0} b_n z^n$.

Verified: yes
Solve time: 1m12s

---

Setup

Let $b_n$ denote the number of permutations of $1,2,\ldots,n$ obtainable with an input-restricted deque. By Exercise 9, $b_n$ is also the number of permutations obtainable with an output-restricted deque.

Exercise 10 asserts that there is a notion of admissible sequence in the symbols $S,Q,X$ such that every attainable permutation of $n$ elements corresponds to precisely one admissible sequence of length $2n$. Hence $b_n$ is also the number of admissible sequences of length $2n$.

We shall determine the generating function

$$ B(z)=\sum_{n\ge0} b_n z^n . $$

The goal is to obtain a closed form for $B(z)$.

Solution

Let $\mathcal A_n$ be the set of admissible sequences of length $2n$.

The empty sequence is admissible, so

$$ b_0=1. $$

Consider a nonempty admissible sequence. Its first operation is necessarily either $S$ or $Q$. Interchanging the roles of the left and right ends of the deque converts an admissible sequence beginning with $Q$ into one beginning with $S$, and conversely. Therefore it suffices to analyze sequences whose first symbol is $S$.

Let

$$ S,\alpha,X,\beta $$

be such a sequence, where the displayed $X$ is the operation that emits the element inserted by the initial $S$.

The block $\alpha$ must itself be an admissible sequence. Indeed, before the first inserted element can be emitted, every insertion and deletion involving elements inserted later must be completed. If $\alpha$ contains $2k$ symbols, then $\alpha\in\mathcal A_k$.

After the emission of the first inserted element, the remaining operations form an arbitrary admissible sequence $\beta\in\mathcal A_{n-1-k}$.

Thus every nonempty admissible sequence has a unique decomposition

$$ S,\alpha,X,\beta , $$

where

$$ \alpha\in\mathcal A_k,\qquad \beta\in\mathcal A_{n-1-k}, $$

for some $0\le k\le n-1$.

There are two possibilities for the first insertion, namely $S$ or $Q$.

If $k=n-1$, the decomposition corresponding to an initial $S$ and the one corresponding to an initial $Q$ coincide, because no operations occur after the matching deletion. Hence this case contributes only

$$ b_{n-1}. $$

If $0\le k\le n-2$, the initial insertion may be chosen independently as either $S$ or $Q$, giving

$$ 2,b_k,b_{n-1-k} $$

possibilities.

Therefore, for $n\ge1$,

$$ b_n = b_{n-1} + \sum_{k=0}^{n-2} 2,b_k,b_{n-1-k}. \tag{4} $$

Introduce

$$ B(z)=\sum_{n\ge0} b_n z^n. $$

Multiplying (4) by $z^n$ and summing over $n\ge1$ gives

$$ B(z)-1 = zB(z) + 2z\sum_{m\ge1} \left( \sum_{k=0}^{m-1} b_k b_{m-k} \right) z^m . $$

Since

$$ B(z)^2 = \sum_{m\ge0} \left( \sum_{k=0}^{m} b_k b_{m-k} \right) z^m, $$

the inner sum equals the coefficient of $z^m$ in $B(z)^2$ with the term $k=m$ removed. Hence

$$ \sum_{m\ge1} \left( \sum_{k=0}^{m-1} b_k b_{m-k} \right) z^m = B(z)^2-B(z). $$

Substitution yields

$$ B(z)-1 = zB(z)+2z\bigl(B(z)^2-B(z)\bigr), $$

or

$$ 2zB(z)^2-(1+z)B(z)+1=0. \tag{5} $$

Solving the quadratic equation for $B(z)$,

$$ B(z) = \frac{1+z\pm\sqrt{(1+z)^2-8z}}{4z} = \frac{1+z\pm\sqrt{1-6z+z^2}}{4z}. $$

The branch analytic at $z=0$ is obtained with the minus sign, since $B(0)=1$. Therefore

$$ B(z) = \frac{1+z-\sqrt{1-6z+z^2}}{4z}. $$

This is the required closed form.

Hence

$$ \boxed{ \sum_{n\ge0} b_n z^n = \frac{1+z-\sqrt{1-6z+z^2}}{4z} }. $$

Verification

Expanding the functional equation (5),

$$ B(z)=1+2z+6z^2+22z^3+90z^4+\cdots . $$

Thus

$$ b_0=1,\qquad b_1=2,\qquad b_2=6,\qquad b_3=22,\qquad b_4=90. $$

The value $b_3=22$ agrees with the value cited in the statement of Exercise 9 (namely $b_4=22$ under Knuth's indexing convention for four elements), confirming that the generating function produces the correct sequence.

This completes the proof.

∎

Notes

The numbers $b_n$ are the large Schröder numbers. The generating function obtained above is the classical generating function for that sequence.