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
- <math>{n-1\choose k} + {n-1\choose k-1} = {n\choose k} </math>
where <math>1 \leq k \leq n</math> and <math>{n\choose k}</math> is a binomial coefficient.
Contents |
[edit] Combinatorial proof
Pascal's rule has an intuitive combinatorial meaning. Recall that <math>{a\choose b}</math> 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 <math>{n\choose k}</math> 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 <math>n-1\choose k-1</math> 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 <math>n-1\choose k</math>.
We conclude that the numbers of ways to get a k-subset from the n-set, which we know is <math>{n\choose k}</math>, is also the number <math>{n-1\choose k-1} + {n-1\choose k}</math>.
[edit] Algebraic proof
We need to show
- <math> { n \choose k } + { n \choose k-1 }</math> <math> =</math> <math> { n+1 \choose k }</math>
Let us begin by writing the left-hand side as
- <math> \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!}</math>
Getting a common denominator and simplifying, we have
- <math> \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!}</math>
- <math> =</math> <math> \frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+\frac{kn!}{k(k-1)!(n-k+1)!}</math>
- <math> =</math> <math> \frac{(n-k+1)n!+kn!}{k!(n-k+1)!}</math>
- <math> =</math> <math> \frac{(n+1)n!}{k!((n+1)-k)!}</math>
- <math> =</math> <math> \frac{(n+1)!}{k!((n+1)-k)!}</math>
- <math> =</math> <math> { n+1 \choose k }</math>
[edit] See also
[edit] Sources
- This article incorporates material from Pascal's rule on PlanetMath, which is licensed under the GFDL.
- This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the GFDL.
