Problem 5.12.5 By Corollary 5.12.4 and Corollary 5.1.6, the sum of the dimensions of the irreps of \(S_n\) equals the number of involutions of \(S_n\). Denote this by \(T(n)\). The involutions of \(S_n\) are precisely those permutations that are a product of (possibly zero) distinct transpositions. Therefore \(T(n)\) can be computed by summing over all possible numbers of such transpositions. If there are \(k\) transpositions, then there are \(\binom{n}{2k}\) ways to select the \(2k\) elements to be involved in the transpositions, and \((2k-1)!!\) ways to pair them up. Therefore, \[ T(n) = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} (2k-1)!! \]