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<j$ 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.

  • $\begingroup$ How are permutations being written? Is $p_i$ the image of $i$ under the permutation $p$? $\endgroup$ – Arturo Magidin Mar 8 '11 at 4:04
  • $\begingroup$ It's always interesting to see cross-posting from reddit =P $\endgroup$ – Bey Mar 8 '11 at 6:26
  • if the permutation consists of one cycle, (this doesn't seem to have anything to do with inversions), how many repetitions of the cycle will it take to return to identity if $k$ is even? if $k$ is odd?

  • for $I(n,k)$, how many total possible inversions are there? How many inversions are there of the reverse of a given permutation?

  • for $I(n,3)$, what is $I(n,1)$? $I(n,2)$? Look at some values, guess a formula, and use induction to quickly prove. Or think combinatorially: you have 3 inversions; if they don't interact then it's straightforward; if they do interact then a little more thought on counting them.


Your Answer

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