Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
A simple example of a signed involution is just the map $\sigma \mapsto \tau \circ \sigma$ where $\tau$ is the transposition $(1 \quad 2)$. Have you tried this? What does it give you? –  Srivatsan Nov 26 '11 at 23:08
    
Does this involution preserve the displacement? –  Alex M Nov 27 '11 at 22:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.