Composition (number Theory) - Number of Compositions

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

 \big(\, \overbrace{1\, \square\, 1\, \square\, \ldots\, \square\, 1\, \square\, 1}^n\, \big)

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:

    Even in ordinary speech we call a person unreasonable whose outlook is narrow, who is conscious of one thing only at a time, and who is consequently the prey of his own caprice, whilst we describe a person as reasonable whose outlook is comprehensive, who is capable of looking at more than one side of a question and of grasping a number of details as parts of a whole.
    G. Dawes Hicks (1862–1941)

    That country is the richest which nourishes the greatest number of noble and happy human beings.
    John Ruskin (1819–1900)