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$. We know
$$I\_n=\sum\_{k\geq0}\frac{n!}{2^kk!(n-2k)!}.$$
Some experimental evidence convinces me that it is possible to express $I\_{n+m}$ in terms of a sum of polynomials in $\operatorname{tr}(\pi)$ over $\operatorname{Inv}(\mathfrak{S}\_n)$. We may attempt a modest special case.



> 
> **Question.** Is this true?
>  $$I\_{n+2}=\sum\_{\pi\in \operatorname{Inv}(\mathfrak{S}\_n)}\left(\operatorname{tr}(\pi)^2+\operatorname{tr}(\pi)+2\right).$$
> 
> 
> 


**Note.** $\operatorname{tr}(\pi)^2$ is understood as $\operatorname{tr}(\pi)\operatorname{tr}(\pi)$.



trace and involution permutations: Part I
Let us identify an involution $\sigma$ in $\mathfrak{S}\_n$ with a set partition $\Pi\_\sigma$ of $[n] := \{1,2,...,n\}$ into nonempty blocks of size at most two in the obvious way: we have $\{a,b\} \in \Pi\_\sigma$ if and only if $\sigma(a)=b$. This is obviously a bijection between involutions and such set partitions; and the fixed points of $\sigma$ correspond exactly to the singletons of $\Pi\_\sigma$.


Now to get a set partition $\Pi'$ of $[n+2]$ with block sizes at most two from such a set partition $\Pi\_\sigma$ of $[n]$ corresponding to the involution $\sigma \in \mathfrak{S}\_n$, we just have to decide what blocks the elements $n+1$ and $n+2$ belong to:


* they could each be singletons (one way);
* they could be in a size-two block together (one way);
* $n+1$ could form a block of size two with something that was a singleton in $\Pi\_\sigma$, while $n+2$ is a singleton ($\mathrm{tr}(\sigma)$ many ways);
* $n+2$ could form a block of size two with something that was a singleton in $\Pi\_\sigma$, while $n+1$ is a singleton ($\mathrm{tr}(\sigma)$ many ways);
* $n+1$ could form a block of size two with something that was a singleton in $\Pi\_\sigma$, and $n+2$ could form a block of size two with a different singleton in $\Pi\_\sigma$ ($\mathrm{tr}(\sigma)(\mathrm{tr}(\sigma)-1)$ many ways).


Adding these all together, we get $1+1+\mathrm{tr}(\sigma)+\mathrm{tr}(\sigma)+\mathrm{tr}(\sigma)(\mathrm{tr}(\sigma)-1)=\mathrm{tr}(\sigma)^2+\mathrm{tr}(\sigma)+2$ such set partitions for each involution $\sigma \in \mathfrak{S}\_n$, proving your claimed identity.


EDIT:


Here is the formula for the more general case of $I\_{n+m}$:


$$ I\_{n+m} = \sum\_{\sigma \in \mathrm{Inv}(\mathfrak{S}\_n)} \sum\_{j=0}^{m} \binom{m}{j} \cdot I\_{m-j} \cdot \frac{\mathrm{tr}(\sigma)!}{(\mathrm{tr}(\sigma)-j)!}.$$


It can be proved in the same manner: for each involution $\sigma \in \mathfrak{S}\_n$, we choose $j$ of the elements of $\{n+1,n+2,\ldots,n+m\}$ to join with singletons in $\Pi\_{\sigma}$, and hence choose an ordered subset of $j$ singletons from $\Pi\_{\sigma}$ to pair with these elements, and then we put an involution on the remaining $m-j$ elements of $\{n+1,n+2,\ldots,n+m\}$ in $I\_{m-j}$ ways (with the convention $I\_0 =1$).


EDIT 2:


Maybe one final repackaging of this result is worth recording.


Set $I\_n(t) := \sum\_{\sigma \in \mathrm{Inv}(\mathfrak{S}\_n)} t^{\mathrm{tr}(\sigma)}$ for all $n \geq 0$ (with $I\_0(t)=1$). Then for all $m \geq 0$,
$$ I\_{n+m}(t) = \left(\sum\_{k=0}^{m}\binom{m}{k} \, I\_{m-k}(t) \, \frac{d^k}{dt^k} \right) \, I\_{n}(t).$$
In particular,
$$ I\_{n+1}(t) = \left(t+\frac{d}{dt}\right) I\_{n}(t);$$
hence we also have,
$$ I\_{n+m}(t) = \left(t+\frac{d}{dt}\right)^m I\_{n}(t).$$


