Integer compositions

This article page is a stub, please help by expanding it.

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)=\{\mathrm{\varnothing }\}=\{\{\}\},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)=\mathrm{\varnothing }=\{\},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\ge 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\ge 0$)

$c(n)=\{\begin{array}{ll}1& \text{if }n=0,\\ 2^{n-1}& \text{if }n\ge 1,\end{array}$

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\ge 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, ...}

Formulae

(...)

Sequences

{ , ...}

See also

• Signature permutations for bijections of compositions

• Unordered partitions
  • Partitions and restricted partitions
  • Partition function and restricted partition functions
  • Partition identities
  • Orderings of partitions
  • Multidimensional partitions
    • Partitions (one-dimensional partitions)
    • Plane partitions (two-dimensional partitions)
    • Solid partitions (three-dimensional partitions)

• Ordered partitions
  • Compositions and restricted compositions
  • Composition function and restricted composition functions
  • Composition identities
  • Orderings of compositions
  • Multidimensional compositions
    • Compositions (one-dimensional ordered partitions)
    • Plane compositions (two-dimensional ordered partitions)
    • Solid compositions (three-dimensional ordered partitions)

• Multiplicative partitions (unordered factorizations)
  • Factorizations and restricted factorizations
  • Factorization function and restricted factorization functions

• Multiplicative compositions (ordered factorizations)
  • Ordered factorizations and restricted ordered factorizations
  • Ordered factorization function and restricted ordered factorization functions

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

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

• Sets
  • Set partitions
  • Restricted set partitions
  • Set compositions
  • Restricted set compositions

• Multisets
  • Multiset partitions
  • Restricted multiset partitions
  • Multiset compositions
  • Restricted multiset compositions

External links

• Integer Partitions: Compositions, DLMF
• http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.pdf
• http://www.fq.math.ca/Scanned/39-5/kimberling.pdf