TAOCP 5.1.4 Exercise 25

Exercise 25. [M30] Why is (42) the generating function for involutions?

Verified: yes
Solve time: 52m41s

Setup

By Theorem A in this section, there is a bijection between permutations of ({1,2,\ldots,n}) and ordered pairs ((P,Q)) of standard Young tableaux of the same shape. Under this correspondence, the inverse of a permutation corresponds to swapping (P) and (Q). Hence a permutation is an involution (equal to its own inverse) if and only if (P = Q). Consequently, the number of involutions (I_n) on (n) elements equals the number of standard Young tableaux of size (n).

Equation (42) in the text states that the exponential generating function for the numbers (I_n) is [ \sum_{n=0}^{\infty} I_n \frac{z^n}{n!} = e^{z + z^2/2}. ]

Solution

The numbers (I_n) satisfy the recurrence [ I_n = I_{n-1} + (n-1)I_{n-2} \qquad (n \ge 2), ] with initial conditions (I_0 = 1), (I_1 = 1). This follows directly from the definition of an involution: either (n) is a fixed point (leaving (I_{n-1}) ways to complete the involution on the remaining (n-1) elements), or (n) belongs to a (2)-cycle with one of the other (n-1) elements ((n-1) choices for the partner, after which the remaining (n-2) elements can form any involution in (I_{n-2}) ways).

Let (F(z) = \sum_{n=0}^{\infty} I_n \frac{z^n}{n!}). Differentiating termwise gives [ F'(z) = \sum_{n=1}^{\infty} I_n \frac{z^{n-1}}{(n-1)!} = \sum_{n=0}^{\infty} I_{n+1} \frac{z^n}{n!}. ] Using the recurrence (I_{n+1} = I_n + n I_{n-1}) (valid for (n \ge 1), and also for (n=0) if we interpret (I_{-1}=0)), [ F'(z) = \sum_{n=0}^{\infty} I_n \frac{z^n}{n!} + \sum_{n=1}^{\infty} n I_{n-1} \frac{z^n}{n!} = F(z) + \sum_{n=1}^{\infty} I_{n-1} \frac{z^n}{(n-1)!}. ] The last sum is (z \sum_{m=0}^{\infty} I_m \frac{z^m}{m!} = z F(z)). Hence [ F'(z) = (1+z)F(z). ] With the initial condition (F(0)=I_0=1), the unique solution is (F(z) = e^{z + z^2/2}), which is exactly equation (42).

Verification

We check the first few coefficients of (e^{z+z^2/2}): [ e^{z+z^2/2} = 1 + z + \frac{2}{2!}z^2 + \frac{4}{3!}z^3 + \frac{10}{4!}z^4 + \frac{26}{5!}z^5 + \cdots ] The numbers (1,1,2,4,10,26) are the well‑known involution counts (I_0) through (I_5). They satisfy the recurrence: (2 = 1 + 1\cdot1), (4 = 2 + 2\cdot1), (10 = 4 + 3\cdot2), (26 = 10 + 4\cdot4). The generating function therefore satisfies the differential equation derived from the recurrence, confirming the result independently.

This completes the proof. ∎