(→Combinatorial identities) |
|||
| Line 21: | Line 21: | ||
This identity is the base for a simple algorithm to compute combinations, graphical interpretation of this algorithm is the famous Pascal's Triangle. | This identity is the base for a simple algorithm to compute combinations, graphical interpretation of this algorithm is the famous Pascal's Triangle. | ||
| − | Combinatorial proof | + | <b>Combinatorial proof</b><br> |
On the left hand side of the equation we choose k elements from n at once. On the right hand side we single out one element, let's call it y. We either don't choose y (in this case we choose k elements out of n-1) or we choose y (in this case we pick k-1 elements out of remaining n-1). As we can see, in both lhs and rhs we are counting the same thing. Q.E.D. | On the left hand side of the equation we choose k elements from n at once. On the right hand side we single out one element, let's call it y. We either don't choose y (in this case we choose k elements out of n-1) or we choose y (in this case we pick k-1 elements out of remaining n-1). As we can see, in both lhs and rhs we are counting the same thing. Q.E.D. | ||
Revision as of 10:57, 7 September 2008
Contents
Permutations
Combinations
Claim
$ {n \choose r} = {n \choose n-r} $
Proof(Counting Argument)
$ {n \choose r} = $
$ = $ # ways to CHOOSE r things from n
$ = $ # ways of LEAVING 'n-r' things from n
$ = $ # ways of CHOOSING 'n-r' things from n $ = {n \choose n-r} $. QED
Combinatorial identities
$ {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1} $, where k and n are positive integers, such that k<n
This identity is the base for a simple algorithm to compute combinations, graphical interpretation of this algorithm is the famous Pascal's Triangle.
Combinatorial proof
On the left hand side of the equation we choose k elements from n at once. On the right hand side we single out one element, let's call it y. We either don't choose y (in this case we choose k elements out of n-1) or we choose y (in this case we pick k-1 elements out of remaining n-1). As we can see, in both lhs and rhs we are counting the same thing. Q.E.D.
Binomial Coefficients
Pascal's Triangle
Here are the first five rows of Pascal's Triangle $ \begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&1&&3&&3&&1\\ &1&&4&&6&&4&&1 \end{matrix} $
Binomial Theorem
Definition
$ (x+y)^n = \sum_{i=0}^n {n \choose k}x^i y^{n-i}, $
$ \text{where } {n \choose k} = \frac{n!}{n!(n-r)!}. $
Example
- What is $ \sum_{i=0}^n {n \choose k} = {n \choose 0} + {n \choose 1} + .. + {n \choose n} ? $
Solution: Using the Binomial Theorem, let x = y = 1. Then, $ \sum_{i=0}^n {n \choose k} (1)^i (1)^{n-i} = \underline{\sum_{i=0}^n {n \choose k}} = (1+1)^n = \underline{2^n}. $
