3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is very nice. $\endgroup$ – T. Amdeberhan Mar 8 '17 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.