This site is supported by donations to The OEIS Foundation.

Integer compositions

From OeisWiki
(Redirected from Compositions)
Jump to: navigation, search

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



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

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)

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

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

which constitute a tuple of

which sum to

A related concept is a partition of .

Number of compositions

The number of compositions[1] [into positive integer parts] is given by (Cf. A011782 for )

where for 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 stones in a single row, we have 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 numbers (some with leading 0's) with up to 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 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

{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





Notes

  1. The analogy "composition function" corresponding to "partition function" is tempting, but the accepted terminology is number of compositions.

External links