13
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I'm not sure whether my edit changed what you intended. You wrote either $$I_{n+2} = \sum(\cdots\cdots)^2.$$ or $$ I_{n+2} = \sum(\cdots\cdots)^.$$ where the latter has a superscript period. Did you have a $2$ there, or just a superscript period? $\endgroup$ Mar 5, 2017 at 22:18

1 Answer 1

20
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ This basic bijection between perfect matchings of $[2n]$ and fixed point-free involutions in $\mathfrak{S}_{2n}$ should allow you to prove all the identities about $I_{n+m}$ you were considering. $\endgroup$ Mar 5, 2017 at 17:07
  • 1
    $\begingroup$ Define $f_m(x) := \sum_{j=0}^{m} \binom{m}{j} I_{m-j} \frac{x!}{(x-j)!}$. Then $f_0 = 1$, $f_1 = x+1$, $f_2 = x^2+x+2$, $f_3 = x^3+5x+4$, $f_4=x^4-2x^3+11x^2+6x+10$, etc. The presence of this negative sign in $f_4$ means you are unlikely to get a nice combinatorial formula for the coefficients of $f_m$, unfortunately. $\endgroup$ Mar 6, 2017 at 0:15
  • 2
    $\begingroup$ On the contrary, you don't always have to use $x^j$ as a basis. The family $\frac{x!}{(x-j)!}$ work equally well and the coefficients $\binom{m}jI_{m-j}$, as you showed, are perfectly combinatorial. $\endgroup$ Mar 6, 2017 at 1:03
  • 3
    $\begingroup$ As my last edit should make clear, this stuff is closely related to Stanley's theory of differential posets: dedekind.mit.edu/~rstan/pubs/pubfiles/77.pdf $\endgroup$ Mar 6, 2017 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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