Contents
MA375: Lecture Notes
Fall 2008, Prof. Walther
Permutations
The number of ways you can change the order of a set of things is called the number of PERMUTATIONS of that set of things.
For example, how many different ways can you arrange the letters in the word
WHO
Answer: WHO WOH HWO HOW OHW OWH = 6 ways
Each different letter arrangement is called a permutation of the word "WHO".
So if we want to arrange r elements out of n elements, the general case is given by the formula;
$ {P(n,r)} = \frac{n!}{(n-r)!} $
- n is the number of elements available for selection.
- r is the number of elements to be selected (0 ≤ r ≤ n).
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}. $
