3
$\begingroup$

We define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I know that it's even. Could you help me to find a good signed involution of the set of permutation with displacement $2k$ that helps me (counting the fixed points) to solve this problem:

let $e_{n,k}$ (Respectively $o_{n,k}$) be the number of even (odd) permutations in $S_n$ with displacement $2k$, then

$e_{n,k}-o_{n,k}=(-1)^k\binom{n-1}{k}$

Thank you

(signed means that if a permutation is not fixed then if it is even the image is odd and if it is odd the image is even)

(using the involution we should get a recurrence for $f_{n,k}=e_{n,k}-o_{n,k}$ and then solve it)

  • 0
    Does this involution preserve the displacement?2011-11-27

0 Answers 0