TAOCP 5.3.1 Exercise 1

For $n>0$, the recurrence $P_n=\sum_{k=1}^{n} \binom{n}{k} P_{n-k}$ together with $P_0=1$ is multiplied by $z^n/n!$ and summed over all $n\ge 1$.

taocpmathematicsalgorithmsvolume-3

Section 5.3.1: Minimum-Comparison Sorting

Exercise 1. [**] [M22] (Weak orderings.) When equality between keys is allowed, there are 13 possible outcomes when sorting three elements:

K1 = K2 = K3,
K1 = K2 < K3,
K1 = K3 < K2,
K2 = K3 < K1,
K1 < K2 = K3,
K1 < K3 = K2,
K2 < K1 = K3,
K2 < K3 = K1,
K3 < K1 = K2,
K3 < K2 = K1,
K1 < K2 < K3,
K1 < K3 < K2,
K2 < K1 < K3

Let $P_n$ denote the number of possible outcomes when $n$ elements are sorted with ties allowed, so that $(P_0, P_1, P_2, P_3, P_4, P_5, \dots) = (1, 1, 3, 13, 75, 541, \dots)$. Prove that the generating function

$$P(z) = \sum_{n=0}^{\infty} P_n \frac{z^n}{n!}$$

is equal to $1/(2 - e^z)$. Hint: Show that

$$P_n = \sum_{k>0} \binom{n}{k} P_{n-k} \quad \text{when } n > 0.$$

Verified: yes
Solve time: 1m04s

For $n>0$, the recurrence

$P_n=\sum_{k=1}^{n} \binom{n}{k} P_{n-k}$

together with $P_0=1$ is multiplied by $z^n/n!$ and summed over all $n\ge 1$. The left-hand side becomes

$\sum_{n\ge 1} P_n \frac{z^n}{n!}=P(z)-P_0=P(z)-1.$

On the right-hand side,

$\sum_{n\ge 1}\sum_{k=1}^{n} \binom{n}{k} P_{n-k}\frac{z^n}{n!}.$

Using $\binom{n}{k}/n!=1/(k!(n-k)!)$, the summand becomes

$P_{n-k}\frac{z^{n-k}}{(n-k)!}\cdot \frac{z^k}{k!}.$

Letting $m=n-k$ transforms the double sum into

$\left(\sum_{k\ge 1}\frac{z^k}{k!}\right)\left(\sum_{m\ge 0} P_m\frac{z^m}{m!}\right)=(e^z-1)P(z).$

Hence

$P(z)-1=(e^z-1)P(z).$

Rearranging gives

$P(z)\bigl(1-(e^z-1)\bigr)=1,$

so

$P(z)(2-e^z)=1,$

and therefore

$P(z)=\frac{1}{2-e^z}.$

This completes the proof. ∎