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 → .
Read more about this topic: Composition (number Theory)
Famous quotes containing the words number of and/or number:
“That country is the richest which nourishes the greatest number of noble and happy human beings.”
—John Ruskin (18191900)
“Civilization is maintained by a very few people in a small number of places and we need only some bombs and a few prisons to blot it out altogether.”
—Cyril Connolly (19031974)