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:

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

    Civilization is maintained by a very few people in a small number of places and we need only some bombs and a few prisons to blot it out altogether.
    Cyril Connolly (1903–1974)