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 heartily wish you, in the plain home-spun style, a great number of happy new years, well employed in forming both your mind and your manners, to be useful and agreeable to yourself, your country, and your friends.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (16941773)
“In the end we beat them with Levi 501 jeans. Seventy-two years of Communist indoctrination and propaganda was drowned out by a three-ounce Sony Walkman. A huge totalitarian system ... has been brought to its knees because nobody wants to wear Bulgarian shoes.... Now theyre lunch, and were number one on the planet.”
—P.J. (Patrick Jake)
