Brian Bi
$\DeclareMathOperator{\End}{End} \DeclareMathOperator{\char}{char} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\ker}{ker} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\span}{span} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\Id}{Id} \DeclareMathOperator{\ad}{ad} \newcommand\d{\mathrm{d}} \newcommand\pref[1]{(\ref{#1})}$

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)!!$