3
$\begingroup$

Could you help me to prove this: $\pi\in S_n$, we define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I have to prove the following:

$\mathrm{disp}(\pi)$ is always even.

  • 0
    I must be misunderstanding (2). I tried to do an example for $n=3$. There are 6 permutations in $S_3$. Written as products of transpositions they are: (1) (disp=0), (12) (disp=2), (13) (disp=4), (23) (disp=2), (12)(23) (disp=4), and (13)(23) (disp=6). So for $k=2$, I compute $e_{n,k}-o_{n,k}=1-1=0 \neq 1 = (-1)^k \binom{n-1}{k}$. Is the problem correct as stated, or am I just confused?2011-11-16
  • 0
    @DimitrijeKostic: The last two perms should be (123) and (132), both with disp=4. The first perm and the last 2 perms are even; the others are odd. So we have $e_{3,k}=(1,0,2)$ and $o_{3,k}=(0,2,1)$ for $k=0,1,2$. This matches the identity.2011-11-16
  • 0
    @DavidBevan Thanks, I see my error now.2011-11-16

1 Answers 1

3

For the first part, note that the parity of $|x-y|$ equals the parity of $x-y$, so the parity of disp$(\pi)$ equals the parity of $\sum(\pi(i)-i)=\sum\pi(i)-\sum i=0$, and $0$ is even.