Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients.
It states that for positive natural numbers n and k,
where
is a binomial coefficient;
one interpretation of which is the coefficient of the x^k term in the expansion of (1 + x)ⁿ.
There is no restriction on the relative sizes of n and k, since if n < k the value of the binomial coefficient is zero and the identity remains valid.
Combinatorial proof
Pascal's rule has an intuitive combinatorial meaning, which is clearly expressed in this counting proof.
equals the number of subsets with k elements from a set with n elements.
Suppose one particular element is uniquely labelled X in a set with n elements.
To construct a subset of k elements containing X, include X and choose k - 1 elements from the remaining n - 1 elements in the set. There are
such subsets.
To construct a subset of k elements not containing X, choose k elements from the remaining n - 1 elements in the set. There are
such subsets.
The total number of subsets with k elements in a set of n elements is
the number of subsets containing X (1) + the number of subsets that do not contain X (2)
