Common counting techniques

Before we go too far with proving various clever binomial coefficient identities, let's try counting some things with them.

Stars and bars

We know that there are "n choose k" ways to pick k children out of a group of n children (assuming we can tell the children apart). But what if we add an indistinguishable element to the story? Unlike our distinguishable children, let's say we have some identical candies to hand out. One natural question is:

• How many ways are there to hand out k indistinguishable candies to n distinguishable children?

Here's where the stars and bars come in. Let's say we have 3 children and 8 candies. We can think of the candies as the "stars." The 3 children can be thought of as candy receptacles (sorry, kids), distinguished only by their order from left to right. So here's one way we could distribute the candy:

***|****|*

In this case, the first child/candy receptacle gets 3 candies, the second gets 4, and the third gets 1. Here's another option: 

|********|

In this case, the first kid gets no candy, the second gets all 8 candies, and the third gets no candy. Sucks to be those guys. 

So hopefully you are seeing how this works: k candies means k stars, and n children means n-1 bars. All in all, how many ways can we hand out the candies? Well, there are k+n-1 spaces, k of which are filled with stars. There are $${k+n-1 \choose k} $$ ways to pick those spaces (and once we do, the other n-1 spaces are automatically filled with bars, so there are no more choices to make).

"Stars and bars" is going to be a very handy technique for problems we'll run into in the future, so keep it in mind!

• Practice: Use stars & bars to determine how many sets of nonnegative integers a, b, c, d there are such that a+b+c+d =10.

Rules of sum and product

Rules of sum and product are pretty simple in counting: generally, "and" means product, "or" means sum. For example: poker hands!

Combinatorialists love poker hands, because they're a natural way to think about counting stuff. We start with a standard deck of 52 cards (a 2, 3, 4, 5, 6, 7, 8, 10, J, Q, K, A of each of the four suits), and just deal with the basic 5-card poker hands; here are the 8 most valuable kinds of hands, in order of how valuable they are: 

Source: https://www.cardplayer.com/rules-of-poker/hand-rankings

Figuring out the relative values of the hands all comes down to counting, using the product rule. How many ways can you get three of a kind? Well, we have to choose 1 rank out of the 13 available for the three of a kind *and* choose 3 out of the 4 suits *and* choose 2 more ranks out of the 12 available *and* choose a suit for each of those 2 cards. Every and becomes multiplication, so we get: $${13 \choose 1}{4 \choose 3} {12 \choose 2}{4 \choose 1}{4 \choose 1}=54,912 $$

• Practice: using binomial coefficients, compute how many different ways you can get a royal flush, a straight flush, four of a kind, a full house, a flush, and a straight.

On the other hand, here's an example where we'll use sums; 

• How many ways are there to get a 5-card poker hand that contains a K or A (or both)? 

To answer this question, we can figure out how many hands contain a K (which means we have to choose a suit for the K, as well as 4 other cards) and how many hands contain an A (which means we have to choose a suit for the A, as well as 4 other cards). However, the situation in which we have both a single K *and* a single A gets counted in both scenarios, so we have to subtract that. This gives us: 

$${4 \choose 1}{48 \choose 4} + {4 \choose 1}{48 \choose 4} - {4 \choose 1}^2 {44 \choose 3}\approx 1,344,786$$

---

Discrete Probability Basics

We won't go into the depths of probability, because that is a class (or several) in itself, but let's talk basics. The beautiful truth is that discrete probability is counting---we just have to do it twice, and then divide. For example: 

• What is the probability that a random 5-card hand will be a three of a kind? 

To figure out the answer to this question, we just have to figure out how many 5-card hands are possible to begin with (so, how many ways can we choose 5 cards out of a set of 52 distinguishable cards), and divide: 

$$ \frac{{13 \choose 1}{4 \choose 3} {12 \choose 2}{4 \choose 1}{4 \choose 1}}{{52 \choose 5}} \approx 0.021$$

Highly important note: In order for this to work, it's very important that every hand is equally likely!

Compare this to the probability of a royal flush to see how much rarer and more valuable that hand is:
$$\frac{{4 \choose 1}}{52 \choose 5} \approx 0.0000015$$