Combinatorics

The parallelogram identity in Pascal's triangle states that, given an entry \({n \choose k}\) in Pascal's triangle, \({n \choose k}-1 = \) the sum of the entries included in the rectangle that is straight above entry \({n \choose k}\) and also includes the apex of Pascal's triangle. This equality can be expressed as a double sum as follows, $${n+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{n-k}{n-i-j \choose k-i}$$.  We can prove this by using the stars and bars technique that we are familiar with. For easier explanation, let's first rewrite the double sum expression above in another form (but mathematically equivalent). Set \(r = n-k\), we have  $${r+k+1 \choose k+1}-1=\sum_{i=0}^{k}\sum_{j=1}^{r}{(k-i)+(r-j) \choose k-i}$$.  Let's assume we have \((k+1)\) stars and \(r\) bars. As we have already known, \({r+k+1 \choose k+1}\) counts the number of different star-bar sequences. This implies that maybe we can try to interpret the RHS as another way to c...

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

One good way to think about combinatorial proofs in general is something like this: Goal: Prove that quantity  A  and quantity  B  are equal. Step 1: Think of some question to which either  A  is obviously the answer.  Step 2: Show that  B  also gives the answer to the question. Or perhaps like this: Goal: Prove that quantity  A  and quantity  B  are equal. Step 1: Think of some set of size  A . Think of some different set of size  B . Step 2: Find a bijective (one-to-one) correspondence between the two sets. In both set-ups, most of the creativity is in that second step. That's the hard part, but it's also the part that gives us all the insight. Coming up with an explanation of why  B  counts the same thing  A  does is exactly what helps us understand why the two quantities are the same. Let' s spend a little more time with binomial coefficients to gain some more practice wit...

Combinatorics is an extremely broad field, applications of which appear all over the place. Some fields, like discrete probability and computer science, simply *could not even exist* without combinatorics. In putting together a single-semester combinatorics course, I wanted to have some kind of narrative throughout so that we weren't just talking about random selections of cute problems in the field. As a result, what we'll be focusing on is what is called "combinatorial proof," also known as "proof by two way counting," "counting proof," and a variety of other aliases. The idea of a counting proof is that it counts something. This might sound silly, so here's an example of the difference between a combinatorial proof and a non-combinatorial proof of the same thing. Binomial coefficients You might have seen binomial coefficients before. They look like this: $${n \choose k}$$ (read " n choose k ") and they represent the number o...