mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-01-31, 14:53   #1
tytus
 
Jan 2005

22 Posts
Default 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.

tytus is offline   Reply With Quote
Old 2005-01-31, 19:47   #2
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

3×167 Posts
Default

Not to be abnoxious, but is this a homework problem?
JuanTutors is offline   Reply With Quote
Old 2005-01-31, 19:55   #3
tytus
 
Jan 2005

22 Posts
Default

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...
tytus is offline   Reply With Quote
Old 2005-02-04, 10:10   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

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

Let an,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 Sk=1 an,k xk = (1+x)(1+x+x2) ... (1+x+...+xn-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
geoff is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 06:53.

Fri Mar 5 06:53:04 UTC 2021 up 92 days, 3:04, 0 users, load averages: 1.13, 1.13, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.