This site is supported by donations to The OEIS Foundation.

# Integer compositions

(Redirected from Compositions)

A composition of an integer ${\displaystyle \scriptstyle n\,}$, is a tuple (ordered list) of positive integers whose elements sum to ${\displaystyle \scriptstyle n\,}$ (sometimes also called integer composition, ordered partition or ordered integer partition). This is an additive representation of ${\displaystyle \scriptstyle n\,}$. A part in a composition is sometimes also called a summand. The set of compositions of ${\displaystyle \scriptstyle n\,}$ is denoted by ${\displaystyle \scriptstyle C(n)\,}$. The composition function ${\displaystyle \scriptstyle c(n)\,}$ gives the number of compositions of ${\displaystyle \scriptstyle n\,}$, that is ${\displaystyle \scriptstyle c(n)\,}$ is the cardinality of ${\displaystyle \scriptstyle C(n)\,}$.

The set of compositions of 0 is a set containing the empty set (the sum of elements of an empty set being the empty sum, defined as the additive identity, i.e. 0)

${\displaystyle C(0)=\{\emptyset \}=\{\{\}\},\,c(0)=1.\,}$

Without the concept of empty sum, we would have to make the convention that ${\displaystyle \scriptstyle p(0)\,}$ is set to 1.

The set of compositions of a negative integer is the empty set, since negative integers are not the sum of positive integers

${\displaystyle C(n)=\emptyset =\{\},\,c(n)=0,\,n<0,\,}$

where the composition function of negative integers is useful in some recursive formulae for the composition function (e.g. the intermediate composition function formula.)

## Definition

An ordinary or line composition of ${\displaystyle \scriptstyle n\,}$ is a one-dimensional arrangement of positive integers

${\displaystyle n_{0}\,}$ ${\displaystyle n_{1}\,}$ ${\displaystyle n_{2}\,}$ ${\displaystyle n_{3}\,}$ ${\displaystyle \cdots }$

which constitute a tuple of

${\displaystyle n_{i}\geq 1\,}$

which sum to ${\displaystyle \scriptstyle n\,}$

${\displaystyle n=\sum _{i}n_{i}.\,}$

A related concept is a partition of ${\displaystyle \scriptstyle n\,}$.

## Number of compositions

The number of compositions[1] [into positive integer parts] is given by (Cf. A011782${\displaystyle \scriptstyle (n)\,}$ for ${\displaystyle \scriptstyle n\,\geq \,0\,}$)

${\displaystyle c(n)={\begin{cases}1&{\text{if }}n=0,\\2^{n-1}&{\text{if }}n\geq 1,\end{cases}}}$

where for ${\displaystyle \scriptstyle n\,=\,0\,}$ we have the empty composition, giving the empty sum, i.e. 0. (Obviously, for negative integers, we have 0 compositions [into positive integer parts].)

This is easy to see, since if we have ${\displaystyle \scriptstyle n\,}$ stones in a single row, we have ${\displaystyle \scriptstyle n-1\,}$ spaces between the stones were we can put a separator. Now, if we use binary digits 0 or 1 to indicate the absence or presence of a separator, there are ${\displaystyle \scriptstyle 2^{n-1}\,}$ numbers (some with leading 0's) with up to ${\displaystyle \scriptstyle n-1\,}$ binary digits.

The 16 integer compositions of 5
Binary representation
(in lexicographic order)
Composition
(in reverse lexicographic order)
0000 5
0001 4+1
0010 3+2
0011 3+1+1
0100 2+3
0101 2+2+1
0110 2+1+2
0111 2+1+1+1
1000 1+4
1001 1+3+1
1010 1+2+2
1011 1+2+1+1
1100 1+1+3
1101 1+1+2+1
1110 1+1+1+2
1111 1+1+1+1+1.

An alternative way to encode integer compositions of ${\displaystyle \scriptstyle n\,}$ in a binary representation is based on run-length encoding of integer compositions, which results in a different ordering from the one presented above.

A011782 ${\displaystyle \scriptstyle a(0)\,=\,1;\;a(n)\,=\,2^{n-1},\,n\,\geq \,1.\,}$

{1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, ...}

(...)

{ , ...}