4
$\begingroup$

Working my way through a combinatorics text and I'm hung up on a couple of questions:

1.) Let $p=p_1 p_2\cdots p_n$ be a permutation. An inversion of $p$ is a pair of entries $(p_i,p_j)$ so that $i but $p_i>p_j$. Let us a call a permutation even (resp. odd) if it has an even (resp. odd) number of inversion. Prove that the permuation consisting of the one cycle $(a_1a_2\cdots a_k)$ is even if $k$ is odd, and is odd if $k$ is even.

2.) Let $I(n,k)$ be the number of $n$-permutations that have $k$ inversions. Prove that $I(n,k)=I(n,\binom{n}{2}-k)$.

3.) Find an explicit formula for $I(n,3)$.

These are from a combinatorics text, but I vaguely remember this topic popping up in undergrad abstract algebra and possibly in an algorithm design course as well.

  • 0
    How are permutations being written? Is $p_i$ the image of $i$ under the permutation $p$?2011-03-08
  • 0
    It's always interesting to see cross-posting from reddit =P2011-03-08

1 Answers 1