It is obvious that $\sum_{p \in S_n} 1=n!$ because it is just counting how many permutations there are of $n$ symbols.
But I have also observed that $\sum_{p \in S_n} 2^{c(p)}=(n+1)!$, where $c(p)$ is the number of cycles of $p$.
What is the combinatorial interpretation of this identity?
An example. In $S_3$ we have one permutation with 3 cycles, three permutations with 2 cycles and two with 1 cycle. Then $1\times 2^3+3\times 2^2+2\times 2^1=24=4!$
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment