Home > Algebra, Combinatorics, IMO, Olympiad > Romanian TST 2011 Problem 4

## Romanian TST 2011 Problem 4

Suppose $n \geq 2$ and denote $S_n$ the permutations of the set $\{1,2,..,n\}$. For $\sigma \in S_n$ denote by $\ell(\sigma)$ the number of cycles in the disjoint cycle decomposition of the permutation $\sigma$. Calculate the sum $\displaystyle \sum_{\sigma \in S_n} \text{sgn}(\sigma) n^{\ell(\sigma)}$.

Official Solution: Denote by $f_n(x)=\displaystyle \sum_{\sigma \in S_n} \text{sgn}(\sigma) x^{\ell(\sigma)},\ \forall n \geq 2$, and try to find a recurrence relation for $f_n$.

To do this, consider $\sigma \in S_n$ and $\sigma_1 \in S_{n-1}$ obtained by deleting $n$ from $\sigma$. If $\sigma$ has $n$ as a fixed point, then $\text{sgn}\sigma=\text{sgn}\sigma_1$ and $\ell(\sigma_1)=\ell(\sigma)-1$. If $\sigma_1 \in S_{n-1}$ then we can obtain exactly one permutation which fixes $n$ in $S_n$ by inserting $n$, and exactly $n-1$ permutations which do not fix $n$. Therefore $f_n(x)=xf_{n-1}(x)-(n-1)f_{n-1}(x)=(x-n+1)f_{n-1}(x)=...=(x-(n-1))(x-(n-2))...(x-1)x$.

For $x=n$ we get $f_n(n)= n!$ which is the requested answer.