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 think, for the rest of my life, I shall refrain from looking up things. It is the most ravenous time-snatcher I know. You pull one book from the shelf, which carries a hint or a reference that sends you posthaste to another book, and that to successive others. It is incredible, the number of books you hopefully open and disappointedly close, only to take down another with the same result.”
—Carolyn Wells (1862–1942)
“Without claiming superiority of intellectual over visual understanding, one is nevertheless bound to admit that the cinema allows a number of æsthetic-intellectual means of perception to remain unexercised which cannot but lead to a weakening of judgment.”
—Johan Huizinga (1872–1945)