TAOCP 5.1.4 Exercise 32
Let \(X\) be a normal random variable with mean \(1\) and variance \(1\).
Section 5.1.4: Tableaux and Involutions
Exercise 32. [HM21] Prove that the involution number $t_n$ is the expected value of $X^n$, when $X$ is a normal deviate with mean 1 and variance 1.
Verified: yes
Solve time: 13m11s
Solution
Let (X) be a normal random variable with mean (1) and variance (1). Its moment generating function is [ M(t) = \mathbb{E}[e^{tX}] = \exp!\left(t + \frac{t^2}{2}\right). ] Expanding as a power series gives [ M(t) = \sum_{n=0}^{\infty} \mathbb{E}[X^n],\frac{t^n}{n!}. ]
The involution numbers (t_n) count the permutations of ({1,\dots,n}) that are their own inverse. They satisfy (t_0 = 1), (t_1 = 1), and the recurrence [ t_n = t_{n-1} + (n-1),t_{n-2}\qquad (n\ge 2). ] The exponential generating function (T(x) = \sum_{n=0}^{\infty} t_n x^n/n!) therefore satisfies the differential equation (T'(x) = (1+x)T(x)) with (T(0)=1), whose unique solution is [ T(x) = \exp!\left(x + \frac{x^2}{2}\right). ] (Equivalently, by direct counting: an involution consists of (k) 2‑cycles and (n-2k) fixed points, giving [ t_n = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{(n-2k)!,k!,2^k}, ] and summing the EGF yields (\exp(x)\exp(x^2/2) = \exp(x+x^2/2)).)
Hence (T(x) = M(x)) for all (x). Equating coefficients of (x^n/n!) in the two series yields [ \mathbb{E}[X^n] = t_n \qquad\text{for all } n\ge 0. ]
This completes the proof. ∎
Notes
The identity can be checked for small values: (\mathbb{E}[X^0]=1=t_0), (\mathbb{E}[X]=1=t_1), (\mathbb{E}[X^2]=\operatorname{Var}(X)+(\mathbb{E}[X])^2=1+1=2=t_2), (\mathbb{E}[X^3]=1+3=4=t_3), etc. The result is a special case of the fact that the number of involutions in the symmetric group (S_n) equals the (n)-th moment of a normal distribution with mean (1) and variance (1).