Compositions with a fixed number of inversions

Abstract

A composition of the positive integer n is a representation of n as an ordered sum of positive integers n = a1 + a2 + ··· + am. There are 2n−1 unrestricted compositions of n, which can be sorted according to the number of inversions they contain. (An inversion in a composition is a pair of summands {ai, aj} for which i<j and ai > aj .) The number of inversions of a composition is an indication of how far the composition is from a partition of n, which by convention uses a sequence of nondecreasing summands and thus has no inversions. We count compositions of n with exactly r inversions in several ways to derive generating function identities, and also consider asymptotic results.