Number of n-element permutations with exactly k inversions
 

:question: :question: :question:

How to find the number of n-element 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.

:help: :help: :help:

Not to be abnoxious, but is this a homework problem?

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 n-element permutations with k inversions with given n,k...

This is problem 3.20 in "Combinatorial Problems and Exercises" by L. Lovász:

Let a[sub]n,k[/sub] denote the number of those permutations [font=symbol]p[/font] of {1, ..., n} which have k inversions (pairs i < j with [font=symbol]p[/font](i) > [font=symbol]p[/font](j)). Prove that [font=symbol]S[/font][sub]k=1[/sub] a[sub]n,k[/sub] x[sup]k[/sup] = (1+x)(1+x+x[sup]2[/sup]) ... (1+x+...+x[sup]n-1[/sup]).

(The upper limit of the summation is n choose 2, I don't know how to code that here.)