• The problem was that we counted every order of the cards, but hands of cards are unordered.
• We over-counted by… some amount.

• … 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.

• 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.)

• 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*}\]

• 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\).

• 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 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.

• 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)!}\,.\]

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∎ \]

• 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.

• 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.

• 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\]

• … 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\).∎

• 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: 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.∎

• 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.

• Row \(n\) is the coefficients of the expansion of \((x+y)^n\).