Number of n-element permutations with exactly k inversions

tytus · Post by **tytus** » Sun Jan 30, 2005 9:08 pm

How to find number of n-element permutations with exactly k inversions?? (n,k are given)

cypressx · Post by **cypressx** » Thu Feb 03, 2005 2:46 pm

I know some solutions:
1.) Using Merge Sort ( the complexity is O(n log n) )
2.) Using DP ( this is the fastest algorithm for this problem that I have heard of )

Probably there exist a formula ?

nnahas · Post by **nnahas** » Sun Feb 06, 2005 10:39 pm

tytus wrote:How to find number of n-element permutations with exactly k inversions?? (n,k are given)

http://academic.csuohio.edu/bmargolius/ ... invers.htm

OJ Board

Number of n-element permutations with exactly k inversions

Number of n-element permutations with exactly k inversions

Re: Number of n-element permutations with exactly k inversio