This site is supported by donations to The OEIS Foundation.

# Integer compositions

(Redirected from Compositions)

A composition of an integer $n\,$ , is a tuple (ordered list) of positive integers whose elements sum to $n\,$ (sometimes also called integer composition, ordered partition or ordered integer partition). This is an additive representation of $n\,$ . A part in a composition is sometimes also called a summand. The set of compositions of $n\,$ is denoted by $C(n)\,$ . The composition function $c(n)\,$ gives the number of compositions of $n\,$ , that is $c(n)\,$ is the cardinality of $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)

$C(0)=\{\emptyset \}=\{\{\}\},\,c(0)=1.\,$ Without the concept of empty sum, we would have to make the convention that $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

$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 $n\,$ is a one-dimensional arrangement of positive integers

$n_{0}\,$ $n_{1}\,$ $n_{2}\,$ $n_{3}\,$ $\cdots$ which constitute a tuple of

$n_{i}\geq 1\,$ which sum to $n\,$ $n=\sum _{i}n_{i}.\,$ A related concept is a partition of $n\,$ .

## Number of compositions

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

$c(n)={\begin{cases}1&{\text{if }}n=0,\\2^{n-1}&{\text{if }}n\geq 1,\end{cases}}$ where for $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 $n\,$ stones in a single row, we have $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 $2^{n-1}\,$ numbers (some with leading 0's) with up to $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 $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 $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, ...}

(...)

## Sequences

{ , ...}

• Prime signature (which may be viewed as a given partition of $\Omega (n)\,$ , the number of prime factors (with repetition) of $n\,$ .)
• Ordered prime signature (which may be viewed as a given composition of $\Omega (n)\,$ , the number of prime factors (with repetition) of $n\,$ .)