Permutations

Combinations

Claim

$ {n \choose r} = {n \choose r-1} $

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 r-1} $

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