Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
What have you tried? –  Soarer Mar 8 '11 at 3:54
    
How are permutations being written? Is $p_i$ the image of $i$ under the permutation $p$? –  Arturo Magidin Mar 8 '11 at 4:04
    
It's always interesting to see cross-posting from reddit =P –  Bey Mar 8 '11 at 6:26
add comment

1 Answer

  • 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.