Composition (number Theory) - Number of Compositions

Number of Compositions

Conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers. There are 2n−1 compositions of n ≥ 1; here is a proof:

Placing either a plus sign or a comma in each of the n − 1 boxes of the array

produces a unique composition of n. Conversely, every composition of n determines an assignment of pluses and commas. Since there are n − 1 binary choices, the result follows. The same argument shows that the number of compositions of n into exactly k parts is given by the binomial coefficient . Note that by summing over all possible number of parts we recover 2n−1 as the total number of compositions of n:

For weak compositions, the number is, since each k-composition of n + k corresponds to a weak one of n by the rule → .