Inversions in compositions of integers

Abstract

A composition of the positive integer n is a representation of n as an ordered sum of positive integers n = a₁ + a₂ + … + a_m. It is well known that there are 2 ^{n −1} compositions of n. An inversion in a composition is a pair of summands {a_i,a_j } for which i < j and a _i > a_j . 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 has no inversions. We consider counting techniques for determining both the number of inversions in the set of compositions of n and the number of compositions of n with a given number of inversions. We provide explicit bijections to resolve several conjectures, and also consider asymptotic results.