to count the {1, 2}-restricted compositions of
n, the number of ways one can ascend a staircase of length
n, taking one or two steps at a time Conventionally the empty composition is counted as the sole composition of 0, and there are no compositions of negative integers. There are 2
n−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 (a '''
k-composition'
) is given by the binomial coefficient {n-1\choose k-1}. Note that by summing over all possible numbers of parts we recover 2n
−1 as the total number of compositions of n'': : \sum_{k=1}^n {n-1 \choose k-1} = 2^{n-1}. For weak compositions, the number is {n+k-1\choose k-1} = {n+k-1 \choose n}, since each
k-composition of
n +
k corresponds to a weak one of
n by the rule : a_1+a_2+ \ldots + a_k = n +k \quad \mapsto \quad (a_1 -1) + (a_2-1) + \ldots + (a_k - 1) = n It follows from this formula that the number of weak compositions of
n into exactly
k parts equals the number of weak compositions of
k − 1 into exactly
n + 1 parts. For
A-restricted compositions, the number of compositions of
n into exactly
k parts is given by the extended binomial (or polynomial) coefficient \binom{k}{n}_{(1)_{a\in A}}=[x^n]\left(\sum_{a\in A} x^a\right)^k, where the square brackets indicate the extraction of the
coefficient of x^n in the polynomial that follows it. ==Homogeneous polynomials==