# 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.
• 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:
• 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$$.