20050131, 14:53  #1 
Jan 2005
2^{2} Posts 
Number of nelement permutations with exactly k inversions
How to find the number of nelement permutations with exactly k inversions? A pair of indices (i,j), 1<=i<=j<=n, is an inversion of the permutation A if ai>aj. 
20050131, 19:47  #2 
Mar 2004
3×167 Posts 
Not to be abnoxious, but is this a homework problem?

20050131, 19:55  #3 
Jan 2005
2^{2} Posts 
No, it's not a homework problem... I just would like to know (maybe I should say I have to know) the formula to get the number of nelement permutations with k inversions with given n,k...

20050204, 10:10  #4 
Mar 2003
New Zealand
13×89 Posts 
This is problem 3.20 in "Combinatorial Problems and Exercises" by L. Lovász:
Let a_{n,k} denote the number of those permutations p of {1, ..., n} which have k inversions (pairs i < j with p(i) > p(j)). Prove that S_{k=1} a_{n,k} x^{k} = (1+x)(1+x+x^{2}) ... (1+x+...+x^{n1}). (The upper limit of the summation is n choose 2, I don't know how to code that here.) Last fiddled with by geoff on 20050204 at 10:11 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Name That Element  Flatlander  Lounge  24  20090821 16:53 
How To Find The Formula of This Permutations?  dini  Puzzles  0  20090322 03:39 
Permutations Yielding Primes  davar55  Puzzles  7  20081108 04:40 
checking cyclic group belongingness of an element  vector  Math  9  20071202 10:26 
permutations  davieddy  Puzzles  27  20070715 22:06 