TAOCP 2.2.1 Exercise 12
Let $a_n$ denote the number of permutations obtainable with a stack, as defined in Exercise 4, and let $b_n$ denote the number of permutations obtainable with an input-restricted deque, equivalently w...
Section 2.2.1: Stacks, Queues, and Deques
Exercise 12. [HM34] Compute the asymptotic values of the quantities $a_n$ and $b_n$ in exercises 4 and 11.
Verified: no
Solve time: -
Setup
Let $a_n$ denote the number of permutations obtainable with a stack, as defined in Exercise 4, and let $b_n$ denote the number of permutations obtainable with an input-restricted deque, equivalently with an output-restricted deque by Exercise 9.
Exercise 4 gives the Catalan numbers
$$ a_n=\frac1{n+1}\binom{2n}{n}, $$
whose generating function is
$$ A(z)=\sum_{n\ge0}a_nz^n =\frac{1-\sqrt{1-4z}}{2z}. $$
Exercise 11 gives the generating function
$$ B(z)=\sum_{n\ge0}b_nz^n =\frac{1-z-\sqrt{1-6z+z^2}}{2z}. $$
The problem is to determine the asymptotic behavior of $a_n$ and $b_n$.
Solution
For $a_n$, Stirling's formula gives
$$ n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n. $$
Hence
$$ \binom{2n}{n} =\frac{(2n)!}{(n!)^2} \sim \frac{\sqrt{4\pi n}(2n/e)^{2n}} {2\pi n,(n/e)^{2n}} = \frac{4^n}{\sqrt{\pi n}}. $$
Since
$$ a_n=\frac1{n+1}\binom{2n}{n}, $$
and
$$ \frac1{n+1}\sim\frac1n, $$
we obtain
$$ a_n \sim \frac{4^n}{\sqrt{\pi},n^{3/2}}. $$
Therefore
$$ \boxed{ a_n\sim \frac{4^n}{\sqrt{\pi},n^{3/2}} }. $$
For $b_n$, consider
$$ B(z)=\frac{1-z-\sqrt{1-6z+z^2}}{2z}. $$
The singularities occur at the zeros of
$$ 1-6z+z^2. $$
These are
$$ \rho=3-2\sqrt2, \qquad \alpha=3+2\sqrt2. $$
Since $\rho<\alpha$, the dominant singularity is $\rho$.
Because $\rho\alpha=1$,
$$ 1-6z+z^2 = (1-z/\rho)(1-z/\alpha). $$
Hence
$$ \sqrt{1-6z+z^2} = \sqrt{1-\rho/\alpha}, \sqrt{1-z/\rho} +O!\left((1-z/\rho)^{3/2}\right). $$
Substituting into $B(z)$,
$$ B(z) = C - K\sqrt{1-z/\rho} + O!\left((1-z/\rho)^{3/2}\right), $$
where
$$ K = \frac{\sqrt{1-\rho/\alpha}}{2\rho}. $$
Since $\alpha=1/\rho$,
$$ K = \frac{\sqrt{1-\rho^2}}{2\rho}. $$
Now
$$ \rho=3-2\sqrt2, $$
so
$$ 1-\rho^2 = 1-(3-2\sqrt2)^2 = 12\sqrt2-16, $$
and a direct simplification yields
$$ K=\sqrt{4+3\sqrt2}. $$
The standard coefficient estimate
$$ [z^n]\sqrt{1-z/\rho} \sim -\frac{\rho^{-n}}{2\sqrt{\pi},n^{3/2}} $$
therefore gives
$$ b_n \sim \frac{K}{2\sqrt{\pi}} ,\rho^{-n}n^{-3/2}. $$
Since
$$ \rho^{-1}=3+2\sqrt2, $$
we obtain
$$ b_n \sim \frac{\sqrt{4+3\sqrt2}} {2\sqrt{\pi}} , (3+2\sqrt2)^n n^{-3/2}. $$
Therefore
$$ \boxed{ b_n \sim \frac{\sqrt{4+3\sqrt2}} {2\sqrt{\pi}} , \frac{(3+2\sqrt2)^n}{n^{3/2}} }. $$
Verification
For $a_n$, the asymptotic formula agrees with the known Catalan asymptotic obtained directly from Stirling's formula.
For $b_n$, the dominant singularity of $B(z)$ is $\rho=3-2\sqrt2$, so the exponential growth factor must be
$$ \rho^{-1}=3+2\sqrt2. $$
The square-root singularity contributes the universal factor $n^{-3/2}$, and the coefficient of $\sqrt{1-z/\rho}$ is
$$ -\sqrt{4+3\sqrt2}, $$
which produces the constant
$$ \frac{\sqrt{4+3\sqrt2}}{2\sqrt{\pi}}. $$
Thus both asymptotic formulas are internally consistent with the singular structure of the generating functions.
Notes
The numbers $a_n$ are Catalan numbers. The numbers $b_n$ are the large Schröder numbers. Both sequences have generating functions with square-root singularities, hence both possess the characteristic factor $n^{-3/2}$ in their asymptotic expansions.