

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


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|cite|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



Browse other questions tagged or ask your own question.