Number of n-element permutations with exactly k inversions

tytus · 2005-01-31, 14:53

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.

JuanTutors · 2005-01-31, 19:47

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

tytus · 2005-01-31, 19:55

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

geoff · 2005-02-04, 10:10

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²) ... (1+x+...+x^n-1).

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

2005-01-31, 14:53	#1
tytus Jan 2005 2² Posts	Number of n-element permutations with exactly k inversions 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.

2005-02-04, 10:10	#4
geoff 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²) ... (1+x+...+x^n-1). (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 2005-02-04 at 10:11

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Name That Element	Flatlander	Lounge	24	2009-08-21 16:53
How To Find The Formula of This Permutations?	dini	Puzzles	0	2009-03-22 03:39
Permutations Yielding Primes	davar55	Puzzles	7	2008-11-08 04:40
checking cyclic group belongingness of an element	vector	Math	9	2007-12-02 10:26
permutations	davieddy	Puzzles	27	2007-07-15 22:06

2005-01-31, 19:47	#2
JuanTutors Mar 2004 3×167 Posts	Not to be abnoxious, but is this a homework problem?

2005-01-31, 19:55	#3
tytus Jan 2005 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 n-element permutations with k inversions with given n,k...