(→Proof(Counting Arguement)) |
m (your argument didn't match up with the statement proved) |
||
| Line 3: | Line 3: | ||
==Combinations== | ==Combinations== | ||
===Claim=== | ===Claim=== | ||
| − | <math> {n \choose r} = {n \choose | + | <math> {n \choose r} = {n \choose n-r} </math> |
===Proof(Counting Arguement)=== | ===Proof(Counting Arguement)=== | ||
| Line 13: | Line 13: | ||
<math>=</math> # ways of CHOOSING 'n-r' things from n | <math>=</math> # ways of CHOOSING 'n-r' things from n | ||
| − | <math> = {n \choose | + | <math> = {n \choose n-r} </math>. |
QED | QED | ||
Revision as of 16:08, 6 September 2008
Contents
Permutations
Combinations
Claim
$ {n \choose r} = {n \choose n-r} $
Proof(Counting Arguement)
$ {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
Binomial Coefficients
Pascal's Triangle
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}. $
