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.^[1] 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}$.

📄️ PartitionSingle Page

📄️ Binomial theoremSingle Page

📄️ Application: Analyzing recursionSingle Page

---

Footnotes

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