This site is supported by donations to The OEIS Foundation.
Integer compositions
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.)
Contents
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.
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.
- {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
- Ordered partitions
- Prime signature (which may be viewed as a given partition of , the number of prime factors (with repetition) of .)
- Ordered prime signature (which may be viewed as a given composition of , the number of prime factors (with repetition) of .)
Notes
- ↑ The analogy "composition function" corresponding to "partition function" is tempting, but the accepted terminology is number of compositions.