Integer compositions

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

---

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

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

Without the concept of empty sum, we would have to make the convention that $\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

$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 $\scriptstyle 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 $\scriptstyle n\,$

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

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

Number of compositions

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

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

where for $\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 $\scriptstyle n\,$ stones in a single row, we have $\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 $\scriptstyle 2^{n-1}\,$ numbers (some with leading 0's) with up to $\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 $\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 $\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, ...}

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 $\scriptstyle \Omega (n)\,$, the number of prime factors (with repetition) of $\scriptstyle n\,$.)

• Ordered prime signature (which may be viewed as a given composition of $\scriptstyle \Omega (n)\,$, the number of prime factors (with repetition) of $\scriptstyle 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