Journal of Integer Sequences, Vol. 23 (2020), Article 20.4.1

Inversions and Parity in Compositions of Integers

M. Archibald, A. Blecher, and A. Knopfmacher
The John Knopfmacher Centre for Applicable Analysis and Number Theory University of the Witwatersrand
South Africa

M. E. Mays
West Virginia University
Morgantown, WV 26506-6310


A composition of a positive integer n is a representation of n as an ordered sum of positive integers a1 + a2 + · · · + am = n. There are 2n−1 unrestricted compositions of n, which can be classified 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. We consider compositions of n counted according to whether they contain an even number or an odd number of inversions, and include results on compositions where the first part occurs with odd multiplicity. The following statistics are also computed for compositions of n: total number of inversions, total sum of inversion sizes, and number of inversions of size d or more.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A005418 A006516 A007582 A020522 A032085 A045623 A045883 A058884 A063376 A102841 A189052 A331606 A331609.)

Received May 10 2019; revised versions received January 22 2020; March 2 2020. Published in Journal of Integer Sequences, March 18 2020.

Return to Journal of Integer Sequences home page