Partition

Another situation where the binomial coefficient shows up naturally is the following setting. We have $n$ non-negative integer variables $x_1,\ldots, x_n$. How many possible solutions satisfy

$x_1 + x_2 + \ldots + x_n = m$

The answer is ${m+n-1 \choose n-1}$. To see this, imagine the situation where Ariel is distributing $m$ identical chocolates to $n$ students in this class. He arranges chocolates on the line and his goal is to use $n-1$ "sticks" to split them into $n$ parts, each being given to a student (the first part to the first student and so on). We can, equivalently, imagine having $m+n-1$ objects and then choosing $n-1$ of these objects to be sticks (the rest would be chocolates). This immediately gives the number ${m+n -1 \choose n-1}$. This informal counting can be turned into a formal counting by defining a bijection. (Since we already did many formal proofs, this is left as an exercise.)

Exercise 68

Define a bijection between solutions to the equation and the possible occurrences of sticks.

A simple property of binomial coefficient is the following:

${n \choose k} = {n \choose n-k}$

This can be easily verified. The left-hand-side is the number of subsets of size $k$ (choosing $k$ out of $n$ elements to be in the set). Another way to choose a subset of size $k$ is to choose $n-k$ elements and throw them away (the remaining elements is our set) 😊

Example 25 (Pascal)

Let $k < n$. Then

${n \choose k} = {n -1 \choose k} + {n-1 \choose k-1}$

Proof:

We use a combinatorial interpretation of the term ${n \choose k}$ as the number of subsets of size $k$. Let $\mathcal{S}$ be the set containing all subsets of $[n]$ of size $k$. We partition $\mathcal{S}$ into $\mathcal{S}' \cup \mathcal{S}''$ where the first set contains all $k$-subsets that do not involve $n$, and $\mathcal{S}''$ are all the $k$-subsets that involve $n$. Notice that $|\mathcal{S}'| = {n-1 \choose k}$ (the number of $k$-subsets of $[n-1]$). Moreover, $\mathcal{S}''$ has a bijection with ${[n-1] \choose k-1}$ (try to formally prove this). This concludes the proof.

Notice that one can also give a purely algebraic proof for the above theorem using the definition of the binomial coefficients. But the proof would be somewhat tasteless and less fun 😊

Let us look at another example where the equation looks much more complicated.

Example 26 (Vandermonde's Identity)

$\sum_{i=0}^n {n \choose i}^2 = {2n \choose n}$

Proof:

On the right-hand-side, the number is exactly the number of $n$-subsets of $[2n]$. Denote $\mathcal{F}= \{S \subseteq [2n]: |S| =n \}$. Now we imagine partitioning $[2n]$ into $E$ and $O$ containing even and odd numbers respectively. So we have $|E| = |O| = n$. We partition $\mathcal{F}$ into $\mathcal{F}_0, \mathcal{F}_1,\ldots, \mathcal{F}_n$ where $\mathcal{F}_i = \{S \in \mathcal{F}: |S \cap E| = i\}$ (these are the subsets $S$ that contain exactly $i$ even numbers and $n-i$ odd numbers). Therefore, we have that $\mathcal{F} = \bigcup_i \mathcal{F}_i$ and

${2n \choose n} = |\mathcal{F}| = \sum_i |\mathcal{F}_i|$

Notice that $|\mathcal{F}_i| = {n \choose i} \cdot {n \choose n-i}$ (choose $i$ even numbers and $n-i$ odd numbers). The identity ${n \choose i} = {n \choose n-i}$ implies the desired result.

Exercise 69

Consider the formula:

${r \choose r} + {r+1 \choose r} + \cdots + {n \choose r} = {n+1 \choose r+1}$

• Prove this formula by induction on $n$ (for any fixed $r$).
• Prove this formula by assigning each term a natural combinatorial interpretation and argue that they are equal.

Exercise 70

Consider an $n$-by-$n$ grid graph where two opposing vertices are denoted by coordinates $(0,0)$ and $(n,n)$. In all the questions below, justify your answers by a formal proof.

• Count the number of shortest paths from $(0,0)$ to $(n,n)$.
• Count the number of shortest paths from $(0,0)$ to $(n-1,n-2)$.
• (difficult) Let $F_k$ denote the number of paths from $(0,0)$ to $(k,k)$ that do not cross the line $x =y$. Prove: $F_n = \sum_{k=0}^{n-1} F_k \cdot F_{n-k-1}$.