2
$\begingroup$

For a permutation $a_1 a_2 \ldots a_n$ of $\{1,\ldots, n \}$, an inversion is a pair $a_i, a_j$ with $i < j$ but $a_i > a_j$. Example $1~4~3~5~2$ has the inversions $4,3; 4,2; 3,2;5,2$. Let $I_{n,k}$ be the number of $n$-permutations with exactly $k$ inversions. Show that $$ \sum_{k=0}^{\binom{n}{2}} (-1)^k I_{n,k} = 0. $$

This problem is taken from M. Aigner, Discrete Mathematics, ex. 1.31. Do you know an elementary proof for it? By elementary I mean just using counting arguments introduced in the first chapter of this book (some basic enumerative combinatorics stuff).

I know that this must be true by some basic abstract algebra as the signum of a permutation is given by $(-1)^{\textrm{number of inversion}}$ and $|A_n : S_n| = 2$, and as the above sum counts exactly all permutations it must vanish. But this argument I think is to advanced, so I am looking for an more elemetary one.

For example, if $n$ is odd, then $\binom{n}{2}$ is odd too, and with $I_{n,k} = I_{n, \binom{n}{2}-k}$ (which is also part of the exercise) it easy to see that this sum cancels, but this does not work if $n$ is even.

$\endgroup$
1
$\begingroup$

As stated, this is not true. You've lost the qualification $n \ge 2$ from the source: with $n = 1$ the sum is just $(-1)^0 I_{1,0} = 1$.

With $n \ge 2$ you can partition the $n!$ permutations into pairs by matching $\pi$ with $(2 1)\pi$. The numbers of inversions of the two elements of each pair differ by exactly $1$, so they cancel.

$\endgroup$
2
$\begingroup$

Try induction on $n$. Insert $n+1$ at position $i$ of an n-permutation, so it contributes $n+1-i$ inversions. All permutations on $n+1$ objects can be uniquely constructed this way, so $$\sum_{k=0}^{\binom {n+1}2}(-1)^kI_{n+1,k}=\sum_{k=0}^{\binom n2}(\sum_{i=1}^{n+1}(-1)^{n+1-i+k} I_{n,k})$$ $$=\sum_{i=1}^{n+1}(-1)^{n+1-i}\sum_{k=0}^{\binom n2}(-1)^kI_{n,k}$$ $$=0$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.