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:
“In a number of other cultures, fathers are not relegated to babysitter status, nor is their ability to be primary nurturers so readily dismissed.... We have evidence that in our own society men can rear and nurture their children competently and that men’s methods, although different from those of women, are imaginative and constructive.”
—Kyle D. Pruett (20th century)
“My idea is that the world outside—the so-called modern world—can only pervert and degrade the conceptions of the primitive instinct of art and feeling, and that our only chance is to accept the limited number of survivors—the one- in-a-thousand of born artists and poets—and to intensify the energy of feeling within that radiant centre.”
—Henry Brooks Adams (1838–1918)