# Intro

- When we counted the number of possible poker hands, we came up with a number that was too big.
- The problem was that we counted every
**order**of the cards, but hands of cards are unordered. - We over-counted by… some amount.

- The problem was that we counted every
- These questions should get different answers: Eight people are running a race…
- … how many ways are there to choose the ones that place in the top three?
- … how many ways are there for the gold, silver, and bronze medals to be given out?
- For the second question, A wins, then B, then C is a different outcome than B then C then A. For the first, they are the same.

# Permutations

- A permutation is a selection of objects in a particular order.
- An \(r\)-permutation is a selection of \(r\) objects.
- e.g. these are different 3-permutations of the 26 lowercase letters: “ate”, “fog”, “ear”, “wqx”.
- “too” is
**not**a permutation of those values, since one element is included twice. - If we don't specify an \(r\), then we mean all of the elements. (“How many permutations are there of these 6 things?” is asking about 6-permutations.)

- We will write \(P(n,r)\) for the number of \(r\)-permutations of \(n\) elements.
- Obviously these are integers with \(0\le r \le n\).
- We found the number of 5-permutations of the 52 cards earlier: \(52\cdot 51\cdot 50\cdot 49\cdot 48\).
- The pattern holds for any \(n\) and \(r\): there are \(n\) ways to choose the first item, \(n-1\) for the second, and so on. \[\begin{align*} P(n,r) &= n\cdot(n-1)\cdot(n-2)\cdot\cdots\cdot(n-r+1)\\ &= n!/(n-r)!\end{align*}\]

*Example:*If there are eight people running a race, there are \(P(8,3)=8!/5!=336\) ways to give out the gold, silver, and bronze medals.- How many permutations of the letters ABCDEFGH contain the string ABC?
- If we have to include ABC in the permutations, then we are essentially permuting these items: ABC, D, E, F, G, H.
- There are six things there: \(6!/0!=6!=720\).

# Combinations

- A combination is a selection of objects where order doesn't matter.
- Similarly, an \(r\)-combination is a combination of \(r\) objects.
- e.g. these are
**the same**3-combination of the 26 lowercase letters: “ate”, “tea”, “eat”, “eta”. - A combination is essentially a subset of the elements.

- We will write \(C(n,r)\) for the number of \(r\)-combinations of \(n\) elements.
- We will also write \(\binom{n}{r}\) sometimes. They mean the same thing: \(C(n,r)=\binom{n}{r}\).
- The actual number of five card hands chosen from 52 cards was actually \(C(52,5)\), not \(P(52,5)\) that we answered.

- To get a value for \(C(n,r)\), we can start with the value we know, \(P(n,r)=n!/(n-r)!\), and fix it.
- If we count the number of \(r\)-permutations, we have counted something similar to the \(r\)-combinations.
- … but order mattered.
- How many ways were there to order those \(r\) elements? \(P(r,r)=r!\).
- So, we counted every combination \(r!\) times. Easy to fix: \[C(n,r)=\frac{n!}{r!(n-r)!}\,.\]

*Example:*If there are eight people running a race, there are \(C(8,3)=8!/(5!3!)=56\) ways to select the three that will be on the podium.*Example:*How many poker hands are there really? \[C(52,5)=\frac{52!}{5!47!} = \frac{52\cdot 51\cdot 50\cdot 49\cdot 48 }{5\cdot 4\cdot 3\cdot 2\cdot 1 } =2598960\,, \] Not 311875200 as we said earlier.*Theorem:*For any integers \(0\le r\le n\), we have \(C(n,r)=C(n,n-r)\).*Proof:*For any \(r\) and \(n\), \[ C(n,n-r) = \frac{n!}{(n-r)!(n-(n-r))!} = \frac{n!}{(n-r)!r!}\,.\quad∎ \]- That theorem basically says: you can either choose the \(r\) things to take, or the \(n-r\) things to leave behind and get the same answer.
*Example:*How many bytes (bit strings of length 8) contain the same number of ones and zeros?- To form a bit string with four ones, we just need to choose where the ones will be placed: in which positions? The other four positions will be the zeros.
- Out of the 8 places, choose the 4 places for the 1s in \(C(8,4)=70\) ways.
- Note: even though the question sounds like ordering matters, we had to turn this one into a combination question to get something we could count.

*Example:*In a class with 30 people, how many ways are there to split the class into three groups of ten?- First attempt: Choose the first team, then the second, then the third: \[C(30,10)\cdot C(20,10)\cdot C(10,10)= 30045015\cdot 184756\cdot 1\,.\]
- This isn't right: it doesn't matter which team is picked first. If you have the same teammates, it shouldn't matter for this question if you're in group 1, 2, or 3.
- Actual answer: \[C(30,10)\cdot C(20,10)\cdot C(10,10)/3!\,.\]
- Same trick as when we got the formula for \(C(n,r)\) originally, but we had to do it again to get right of the over-counted order in our solution.

*Example:*How many poker hands contain two pairs?- First attempt: Select the first card, then another to form a pair, then the other pair, and a final card. \[C(52,1)\cdot C(3,1)\cdot C(50,1)\cdot C(3,1)\cdot C(48,1)=1123200\]
- We have demanded that the pairs be the first cards received: that shouldn't matter.
- We have included the same pairs received in either order.
- We have counted the four-of-a-kind hands, but they shouldn't be included.
- Harder to fix this answer: no obvious way to gt around all problems.
- Second attempt: First select the rank for both pairs (e.g. a pair of Ks and a pair of 3s), then the cards from those ranks, then a final card that isn't from those ranks. \[C(13,2)\cdot C(4,2)\cdot C(4,2)\cdot C(44,1) = 123552\]

- The lesson: be very careful about exactly what you're counting. If it's not exactly the right thing, you'll get the wrong answer.

# Binomial Theorem

- You have often has to expand polynomials like this:
\[\begin{align*}
(x+y)^4
&= (x+y)(x+y)(x+y)(x+y) \\
&= (x^2+2xy+y^2)(x+y)(x+y) \\
&= (x^3+3x^2y+3xy^2+y^3)(x+y) \\
&= x^4+4x^3y+6x^2y^2+4xy^3+y^4
\end{align*}\]
- … and it was a little painful.

*Theorem:*For a non-negative integer \(n\), \[ (x+y)^n = \sum_{i=0}^{n} \binom{n}{i}x^{n-i}y^i\,. \] Recall that \(\binom{n}{i}\) is another notation for \(C(n,i)\).*Proof idea:*The coefficient of the \(x^{n-i}y^i\) term comes from the number ways that it is possible to choose the first term \(n-i\) time and the second term \(i\) times while doing the expansion. We have \(n\) terms to work with, and must select \(i\) of them to multiply the \(y\). There are \(\binom{n}{i}\) ways to do this.*Corollary:*For a non-negative integer \(n\), \[ \sum_{i=0}^{n} \binom{n}{i}=2^n \,. \]*Proof:*Apply the binomial theorem with \(x=y=1\).∎- Another way to look at that corollary:
- The left side of the equation is the number of bit strings of length \(n\) with 0 ones, plus bit strings with 1 one, with 2 ones, …, \(n\) ones.
- The right side is the number of bit strings of length \(n\).
- Those count the same thing, so they must be equal.

# Pascal's Identity and Triangle

Pascal's Identity:

*Theorem:*For a positive integers \(n\) and \(k\) with \(k\le n\), \[ \binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k}\,. \]*Proof:*The left side of this equation is the number of ways to choose \(k\) items from \(n+1\).If we are choosing \(k\) items, we can break our choices into two categories. First, we can include the first item in our choice. Then we must select another \(k-1\) items from the remaining \(n\), in one of \(\binom{n}{k-1}\) ways.

Second, we do not include the first item. Then we select \(k\) items from the remaining \(n\), in one of \(\binom{n}{k}\) ways.

These cover all possibilities of choosing \(k\) from \(n+1\). Thus the two sides are equal.∎

- The binomial theorem and Pascal's identity proofs are examples of combinatorial proofs.
- To prove two values are equal, we show that they are two different ways to look at counting the same thing.
- Another proof technique, particularly useful when you have values you find a way to view as combinatorial results.
- Like any other counting: you have to be sure you're actually counting the same thing twice, not two slightly different things.

- If we draw a triangle, formed by adding the two values above to get the next row, we get:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 - By Pascal's Identity, the value in row \(n\) at \(r\) from the left is \(\binom{n}{r}\).
- Row \(n\) is the coefficients of the expansion of \((x+y)^n\).