Number of n-element permutations with exactly k inversions

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
tytus
New poster
Posts: 4
Joined: Wed Nov 17, 2004 9:09 pm

Number of n-element permutations with exactly k inversions

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
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

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
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

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

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

Post Reply

Return to “Algorithms”