PERMUTATIONS WITH A GIVEN NUMBER OF INVERSIONS

Abstract

In this paper a kind of generalized Pascal triangle is coustructed whose k'th entry in its n'th row equals the number of permutations of degree n having exactly k inversions. Let p~ be the number of the n-degree permutations having: exactly le inversions. Then pk J1 (n) , 1 > ') T • O. if k - <0 so it is presented an algorithm which needs polynomial time only: P k-J1-;-l 11-1 • Finally it is given a method that the n'th row of our GPT contains 1 -'- (~) (non-zero) entries and the computation of the n'th row requires roughly n4 operations.