Pascal's rule

From Wikipedia, the free encyclopedia

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 < n and {n\choose k} is a binomial coefficient.

Contents

[edit] Combinatorial proof

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}.

[edit] Algebraic proof

We need to show

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

Let us begin by writing the left-hand side as

\frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!}

Getting a common denominator and simplifying, we have

\frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}
= \frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+\frac{kn!}{k(k-1)!(n-k+1)!}
= \frac{(n-k+1)n!+kn!}{k!(n-k+1)!}
= \frac{(n+1)n!}{k!((n+1)-k)!}
= \frac{(n+1)!}{k!((n+1)-k)!}
= { n+1 \choose k }

[edit] See also

[edit] Sources

[edit] External links

Retrieved from "http://en.wikipedia.org../../../p/a/s/Pascal%27s_rule.html"
In other languages