# trace and involution permutations: Part II

This is a follow up on my earlier MO question.

Let $\operatorname{Inv}(\mathfrak{S}_n):=\{\pi\in\mathfrak{S}_n: \pi^2=1\}$ be the set of involutions in the symmetric group $\mathfrak{S}_n$. Denote $I_n:=\#\operatorname{Inv}(\mathfrak{S}_n)$. Let $\operatorname{tr}(\pi)$ be the number of fixed points of a permutation $\pi$. Call the functions $B_n(z)=\sum_{j=0}^nS(n,j)z^j$ as Bell polynomials; where $S(n,j)$ are Stirling numbers of the 2nd kind.

Some experimental evidence convinces me that it is possible to express of the following.

Question. Fix an integer $k\geq1$. Does this exponential generating function hold true? $$\sum_{n=1}^{\infty}\frac{z^n}{n!}\sum_{\pi\in \operatorname{Inv}(\mathfrak{S}_n)}\operatorname{tr}(\pi)^k=B_k(z)\cdot e^{z+\frac12z^2}.$$

Note. The case $k=0$ is well-known. Moreover, $\sum_{\pi\in \operatorname{Inv}(\mathfrak{S}_n)}1=\sum_{\lambda\vdash n}f_{\lambda}$ where $f_{\lambda}$ is the number of SYT of shape $\lambda$.

Let us use the convention that $\mathfrak{S}_0$ has a unique element $\sigma$ which is the identity (hence an involution) and has $\mathrm{tr}(\sigma)=0$. We also use $[n] := \{1,2,\ldots,n\}$.
The claimed identity is that for any $k\geq 0$, $$\sum_{n=0}^{\infty} \frac{z^n}{n!} \sum_{\sigma \in \mathrm{Inv}(\mathfrak{S}_n)}\mathrm{tr}(\sigma)^k = B_k(z)\cdot e^{z+\frac{1}{2}z^2}.$$
As mentioned, the case $k=0$ is well known. Hence we may assume $k \geq 1$ and that we want to prove, $$\sum_{n=1}^{\infty} \frac{z^n}{n!} \sum_{\sigma \in \mathrm{Inv}(\mathfrak{S}_n)}\mathrm{tr}(\sigma)^k = B_k(z)\cdot \sum_{n=0}^{\infty} \frac{z^n}{n!} \cdot \#\mathrm{Inv}(\mathfrak{S}_n).$$ Expanding coefficientwise the right-hand side, we see it is equal to $$\sum_{n=0}^{\infty} \frac{z^n}{n!} \sum_{j=1}^{k} \frac{n!}{(n-j)!} \cdot S(k,j) \cdot \#\mathrm{Inv}(\mathfrak{S}_{n-j}).$$ Hence the equality we want is $$\sum_{\sigma \in \mathrm{Inv}(\mathfrak{S}_n)}\mathrm{tr}(\sigma)^k = \sum_{j=1}^{k} \frac{n!}{(n-j)!} \cdot S(k,j) \cdot \#\mathrm{Inv}(\mathfrak{S}_{n-j}).$$ We can prove this bijectively. The left-hand side counts pairs $(\sigma,(i_1,i_2,\ldots,i_k))$ with $\sigma \in \mathrm{Inv}(\mathfrak{S}_n)$ and $i_\ell$ a fixed-point of $\sigma$ for each $\ell=1,\ldots,k$ (allowing repeats). Suppose that $j := \#\{i_1,\ldots,i_k\}$ is the number of distinct entries among $(i_1,i_2,\ldots,i_k)$. Let $\widetilde{\sigma} \in \mathrm{Inv}(\mathfrak{S}_{n-j})$ be the permutation obtained from $\sigma$ by deleting the fixed-points in $\{i_1,i_2,\ldots,i_k\}$ and reindexing in an order-preserving way so the set being permuted is $[n-j]$. The map $(\sigma,(i_1,\ldots,i_k)) \to (\widetilde{\sigma},(i_1,\ldots,i_k))$ is clearly bijective. To finish the proof, I claim the number of possible sequences $(i_1,i_2,\ldots,i_k)$ which have $j := \#\{i_1,i_2,\ldots,i_k\}$ is $\frac{n}{(n-j)!} \cdot S(k,j) = \binom{n}{j} \cdot j! \cdot S(k,j)$. In fact, this is clear: there are $\binom{n}{j}$ choices for the subset $\{i_1,i_2,\ldots,i_k\} = \{\hat{i}_1 < \hat{i}_2 < \cdots <\hat{i}_j\}$, and $j! \cdot S(k,j)$ choices of a surjection $f\colon[k] \to [j]$, where our surjection is given by $f(a) =b$ if $i_a = \hat{i}_b$.
A generating function proof can be given as follows. First we can take a sum over a second variable, so we need to prove $$\sum_{k,n=1}^{\infty}\frac{z^nt^k}{n!k!}\sum_{\pi\in \operatorname{Inv}(\mathfrak{S}_n)}\operatorname{tr}(\pi)^k=\sum_{k=1}^{\infty}\frac{t^k}{k!}B_k(z)\cdot e^{z+\frac12z^2}.$$ The left hand side is $$\sum_{n=1}^{\infty}\frac{z^n}{n!}\sum_{\pi\in \operatorname{Inv}(\mathfrak{S}_n)}e^{t\operatorname{tr}(\pi)}=e^{e^tz+\frac{z^2}{2}}$$ by the exponential formula. (We are counting cycles of length 1 with weight e^t, length 2 with weight 1, and every other cycle length with weight 0.)
On the other hand the generating function for Bell polynomials is $e^{(e^t-1)z}$ so the right hand side evaluates to $$e^{(e^t-1)z}\cdot e^{z+\frac{z^2}{2}}=e^{e^tz+\frac{z^2}{2}},$$ as desired.