Pascal's rule

From Exampleproblems

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have

${n-1\choose k} + {n-1\choose k-1} = {n\choose k}$

where $1 \leq k \leq n$ and ${n\choose k}$ is a binomial coefficient.

Pascal's rule has an intuitive combinatorial meaning. Recall that ${a\choose b}$ counts in how many ways can we pick a subset with b elements out from a set with a elements. Therefore, the right side of the identity ${n\choose k}$ is counting how many ways can we get a k-subset out from a set with n elements.

Now, suppose you distinguish a particular element 'X' from the set with n elements. Thus, every time you choose k elements to form a subset there are two possibilities: X belongs to the chosen subset or not.

If X is in the subset, you only really need to choose k-1 more objects (since it is known that X will be in the subset) out from the remaining n-1 objects. This can be accomplished in $n-1\choose k-1$ ways.

When X is not in the subset, you need to choose all the k elements in the subset from the n-1 objects that are not X. This can be done in $n-1\choose k$ .

We conclude that the numbers of ways to get a k-subset from the n-set, which we know is ${n\choose k}$ , is also the number ${n-1\choose k-1} + {n-1\choose k}$ .