Binomial coefficients

Now let us modify Benjawan's example a bit. She wants to buy four distinct chocolates for the best performing student in class.¹ How many possibilities are there? Notice that now the answer would be different from giving four chocolates to four students: What only matters now is the combination but not the order, so the answer should be much less than $10\cdot 9 \cdot 8 \cdot 7$. Here the answer is exactly the same as the number of four-element subsets of $\{c_1,\ldots, c_{10}\}$.

For any finite set $X$, denote by ${X \choose k}$ the set of all $k$-element subsets of $X$, e.g., ${\{1,2,3,4\} \choose 2} = \{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}\}$. Define the binomial coefficient ${n \choose k}$ as

${n \choose k} = \frac{n!}{(n-k)! k!} = \frac{\prod_{i=0}^{k-1} (n-i)}{k!}$

The following theorem formally proves a basic fact in counting that everyone has used.

Theorem 26

For any finite set $X$, the number of $k$-element subset of $X$ equals to ${|X| \choose k}$.

Proof:

Denote $n = |X|$. We use the accounting method. For each $Y \subseteq X: |Y| = k$, we create a ``bin'' $b_Y$. Let $M$ be the total number of bins. We will show that $M = {|X| \choose k}$. Each one-to-one mapping $f: [k] \rightarrow X$ can be viewed as an ordered $k$-tuple $(f(1),f(2),\ldots, f(k))$ where all elements $f(i)$ are distinct. For each such $f$, we pay a coin into the bin $\{f(1),\ldots, f(k)\}$. The total number of coins in the system is $n(n-1)\cdots (n-k+1) = n!/(n-k)!$. Notice that the number of coins a bin receives is exactly the number of permutations of a $k$-element set, and thus each bin receives exactly $k!$ coins (e.g., when $k=2$ the bin $\{1,2\}$ receives coins from $(1,2)$ and $(2,1)$), so in total we have $M\cdot k! = n!/(n-k)!$ which implies that $M = {n \choose k}$.

The number ${n \choose k}$ has led to many interesting, surprising, and beautiful results. For instance, an immediate corollary is the following:

Example 24

For all non-negative integer $k$, we have that $k!$ divides the product of $k$ consecutive integers.

Proof:

If the $k$ consecutive integers involve zero, the product is always zero, so the claim is trivial. So let us represent the product of $k$ consecutive integers as $n (n-1) \cdots (n-k+1)$ and (without loss of generality) all these numbers are positive. Do you notice something? We need to argue that the ratio $\frac{n (n-1) \cdots (n-k+1)}{k!}$ is an integer. But this is exactly ${n \choose k}$, which is always an integer 😊

Without using the binomial coefficient, proving the above fact is much more complicated.

Exercise 67

Let $p$ be a prime and $k<p$ be a natural number. Prove: $p \mid {p \choose k}$.

📄️ Partition

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

📄️ Binomial theorem

In mathematics (and computer science), we often encounter multiple proofs for the same result. The proofs we have seen so far are classified as "combinatorial" proofs (e.g. relying on counting, bijections, etc). Another famous proof technique is called algebraic proofs which rely on algebraic properties of objects. We will see the first set of examples here (and some more later in these notes).

📄️ Application: Analyzing recursion

Counting can sometimes be used to analyze the running time of recursive algorithms. For instance, look at the following recursion. Let $d$ be some positive integer.

Footnotes

1. This does not sound fair, we know, but aren't we all living in a 🐶-eat-🐶 world? ↩