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:
“I who have been involved with all styles of painting can assure you that the only things that fluctuate are the waves of fashion which carry the snobs and speculators; the number of true connoisseurs remains more or less the same.”
—Pablo Picasso (1881–1973)
“While I do not suggest that humanity will ever be able to dispense with its martyrs, I cannot avoid the suspicion that with a little more thought and a little less belief their number may be substantially reduced.”
—J.B.S. (John Burdon Sanderson)