Pascal's rule should not be confused with Pascal's law.
In mathematics, 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
\tbinom{n}{k}
Pascal's rule can also be viewed as a statement that the formulasolves the linear two-dimensional difference equationover the natural numbers. Thus, Pascal's rule is also a statement about a formula for the numbers appearing in Pascal's triangle.
Pascal's rule can also be generalized to apply to multinomial coefficients.
Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.
Proof. Recall that
\tbinom{n}{k}
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
\tbinom{n-1}{k-1}
To construct a subset of k elements not containing X, choose k elements from the remaining n − 1 elements in the set. There are
\tbinom{n-1}{k}
Every subset of k elements either contains X or not. The total number of subsets with k elements in a set of n elements is the sum of the number of subsets containing X and the number of subsets that do not contain X,
\tbinom{n-1}{k-1}+\tbinom{n-1}{k}
This equals
\tbinom{n}{k}
\tbinom{n}{k}=\tbinom{n-1}{k-1}+\tbinom{n-1}{k}
Alternatively, the algebraic derivation of the binomial case follows.
Pascal's rule can be generalized to multinomial coefficients. For any integer p such that
p\ge2
k1,k2,k3,...,kp\inN+,
n=k1+k2+k3+ … +kp\ge1
{n\choosek1,k2,k3,...,kp}
k1 | |
x | |
1 |
k2 | |
x | |
2 |
…
kp | |
x | |
p |
(x1+x2+...+
n | |
x | |
p) |
The algebraic derivation for this general case is as follows. Let p be an integer such that
p\ge2
k1,k2,k3,...,kp\inN+,
n=k1+k2+k3+ … +kp\ge1