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
Picture
- $ \begin{matrix} &&&&&1\\ &&&&1&&1\\ &&&1&&2&&1\\ &&1&&3&&3&&1\\ &1&&4&&6&&4&&1 \end{matrix} $
- The first five rows of Pascal's triangle
Meaning of Pascal's Triangle
- Each row, except the first, of Pascal's triangle is generated by the row above it. Imagine adding a zero to each end of the previous row. Then the new row is generated by adding each adjacent pair of of numbers and appending it to the current row. The method of generating Pascal's triangle is equivalent to the relation
- $ { n \choose r } = { n-1 \choose r-1 } + { n-1 \choose r } $
- This statement can be proved either through logical argument or through mathematical manipulation of the definition of $ {n \choose r } $.
- The logical argument says that $ {n \choose r} $ represents the way of picking r things from a group of n things. Imagine simulating this. Either the first thing will go into your choice of $ r $ things, in which case you must choose $ r-1 $ things from the remaining $ n-1 $ things - or $ {n-1 \choose r-1} $ - or it will not, in which case you must choose r things from the remaining $ n-1 $ things - or $ {n-1 \choose r } $. All of the possible $ {n \choose r} $ groups fall into these two cases - either a group has thing 1 in it, or it does not - and none of the groups is in both case - because all groups in the first case have 1 in them, and all groups in the second case do not. Therefore, we have $ { n \choose r } = { n-1 \choose r-1 } + { n-1 \choose r } $
- The mathematical proof:
- $ \begin{align} & {n \choose r} = {n-1 \choose r-1} + {n-1 \choose r} \\ & \frac{n!}{(n-r)!r!} = \frac{(n-1)!}{(n-r)!(r-1)!} + \frac{(n-1)!}{(n-r-1)!(r)!} \\ & \frac{n!}{r!} = \frac{(n-1)!}{(r-1)!} + (n-r)\frac{(n-1)!}{(r)!} \\ & n! = r*(n-1)! + (n-r)*(n-1)! \\ & n = r + n-r \\ & n = n \\ \end{align} $
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!}{k!(n-k)!}. $
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}. $
