where is a binomial coefficient. This is also commonly written
Pascal's rule has an intuitive combinatorial meaning. Recall that 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 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 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 ways.
We conclude that the numbers of ways to get a k-subset from the n-set, which we know is , is also the number
See also Bijective proof.
We need to show
Let us begin by writing the left-hand side as
Getting a common denominator and simplifying, we have
Let and . Then
- This article incorporates material from Pascal's rule on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
- This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
- Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1