This is a follow up on [my earlier MO question](https://mathoverflow.net/questions/263797/trace-and-involution-permutations). 


Let $\operatorname{Inv}(\mathfrak{S}\_n):=\{\pi\in\mathfrak{S}\_n: \pi^2=1\}$ be the set of [*involutions*](http://mathworld.wolfram.com/PermutationInvolution.html) 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](http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html).


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$.



trace and involution permutations: Part II
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$.


