How to Count

Previously, we informally introduced some key ideas in probability that we will revisit when exploring the meat of the root—measure theory. Therein, we talked about the counting measure, which we will revisit for simplicity.

Theorem 1. Let $\Omega$ be a finite set and for any $K \subseteq \Omega$ , let $|K|$ denote the number of elements in $K$ . Then for any $K_1,\dots, K_n$ that do not share elements pair-wise (i.e. for $i \neq j$ , $K_i \cap K_j = \emptyset$ ),

$\displaystyle \left| \bigcup_{i = 1}^n K_i \right| = \sum_{i = 1}^n |K_i|.$

This is the first counting principle: the addition principle. Now we raise a seemingly obvious question: how do we count? When I read this I laughed. Shouldn’t we be beyond baby counting? Except that it’s not so obvious, and I’ll try to convince you why that’s the case in a moment.

Let’s analyse this peculiar expression: $(1+x)^n$ . For $n = 0$ and $n = 1$ , we get trivial results:

$(1+x)^0 = 1,\quad (1+x)^1 = 1+x.$

For $n = 2$ , we need to use the basic rules of expansion:

$\begin{aligned} (1+x)^2 &= (1+x)(1+x) \\ &= 1 \cdot (1+x) + x \cdot (1+x) \\ &= (1+x) + (x + x^2) \\ &= 1 + 2x + x^2. \end{aligned}$

For $n = 3$ , we need to do it again, but using the $n = 2$ case:

$\begin{aligned} (1+x)^3 &= (1+x)(1+x)^2 \\ &= (1+x)(1+ 2x + x^2) \\ &= 1 \cdot (1+ 2x + x^2) + x \cdot (1+ 2x + x^2) \\ &= (1+ 2x + x^2) + (x + 2x^2 + x^3) \\ &= 1+ (2 + 1)x + (1 + 2)x^2 + x^3 \\ &= 1 + 3x + 3x^2 + x^3. \end{aligned}$

You may have seen the sequence of these sequences $(1)$ , $(1, 1)$ , $(1, 2, 1)$ , $(1, 3, 3, 1)$ in the first four rows of Pascal’s triangle:

$\begin{aligned} &1,\\ & 1 \quad 1, \\ & 1 \quad 2 \quad 1, \\ & 1 \quad 3 \quad 3 \quad 1. \end{aligned}$

This connection is no coincidence, and we might revisit this idea later on.

Now, here is my question: how do you expand $(1+x)^{100}$ ? By observing the pattern, we can guess that this expansion will require $100 + 1 = 101$ terms, which will take…a long time. Indeed, we can formalise these patterns and more using the principle of mathematical induction and obtain the binomial theorem.

Theorem 2 (Binomial Theorem). For any $n \in \mathbb N_0$ ,

$\displaystyle (1 + x)^n = \sum_{k = 0}^n {n \choose k} x^k,$

where $\displaystyle {n \choose k}$ is the integer recursively defined by

$\displaystyle {n \choose 0} := 1, \quad {n \choose n} := 1,\quad {n+1 \choose k+1} := {n \choose k} + {n \choose k+1}.$

Proof. We have established the base case $n = 0$ . For the inductive step,

$\begin{aligned} (1 + x)^{k+1} &= (1+x)(1+x)^k \\ &= (1+x) \left( \sum_{j = 0}^k {k \choose j} x^j \right) \\ &= \sum_{j = 0}^k {k \choose j} (1+x)x^j \\ &= \sum_{j = 0}^k {k \choose j} (x^j + x^{j+1}) \\ &= \sum_{j = 0}^k {k \choose j} x^j + \sum_{j = 0}^k {k \choose j} x^{j+1} \\ &= \sum_{j = 0}^k {k \choose j} x^j + \sum_{j = 1}^{k+1} {k \choose j-1} x^{j} \\ &= {k \choose 0} x^0 + \sum_{j = 1}^k {k \choose j} x^j + \sum_{j = 1}^{k} {k \choose j-1} x^{j} + {k \choose k} x^k \\ &= {k \choose 0} x^0 + \sum_{j = 1}^k \left( {k \choose j} + {k \choose j-1} \right) x^{j} + {k \choose k} x^k \\ &= {k+1 \choose 0} x^0 + \sum_{j = 1}^k {k+1 \choose j} x^j + {k+1 \choose k+1} x^k \\ &= \sum_{j = 0}^{k+1} {k+1 \choose j} x^j. \end{aligned}$

However, how do we compute $\displaystyle {n \choose k}$ ? We will use $(1+x)^3$ as our case-study, and in doing so, derive a more meaningful interpretation of $\displaystyle {n \choose k}$ and a relatively effective method to compute it.

Let’s expand $(1+x)^3$ again. Intuitively, $(1+x)^3 = (1+x)(1+x)(1+x)$ , and when expanded, yields the sum of the following products:

$\begin{aligned} &1 \cdot 1 \cdot 1, \\ & x \cdot 1 \cdot 1,\quad 1 \cdot x \cdot 1,\quad 1 \cdot 1 \cdot x, \\ & x \cdot x \cdot 1,\quad x \cdot 1 \cdot x,\quad 1 \cdot x \cdot x, \\ &x \cdot x \cdot x. \end{aligned}$

For each $k$ , notice that the coefficient of $x^k$ is exactly the number of arrangements of $k$ copies of $x$ and $(3-k)$ copies of $1$ . We have particularised to $n = 3$ here, but there is no reason to stop at $3$ , unlike Singapore’s population planning post-WWII.

Let’s now discuss the idea of arrangements.

Theorem 2. Given finite sets $K_1,\dots,K_n$ , an $n$ –arrangement is a finite sequence $(x_1,\dots,x_n)$ , where $x_i \in K_i$ for each $i$ . Thus, the set of arrangements is defined by

$\displaystyle \prod_{i = 1}^n K_i \equiv \{(x_1,\dots,x_n) : x_i \in K_i\},$

and the number of elements it has is given by

$\displaystyle \left| \prod_{i = 1}^n K_i \right| = \prod_{i = 1}^n |K_i|.$

This is called the multiplication principle. In the special case $K_1 = \cdots = K_n = K$ , we have $|K^n| = |K|^n$ . An element of $K^n$ is called an $n$ –arrangement of objects in $K$ .

So what we are interested in the $(1+x)^n$ question is the collection of $n$ -arrangements of objects in $\{1, x\}$ . Indeed, our suspicions are confirmed, since for the $n = 3$ case, we did list out $2^3 = 8$ arrangements. But how do we “weed” out the coefficients of $x^k$ ? We need to find the arrangements of the objects

$\underbrace{ x,\dots,x }_k, \underbrace{ 1,\dots, 1 }_{n-k}.$

If we call this number $\displaystyle {n \choose k}$ and are able to compute this number, then immediately we recover the binomial theorem:

$\displaystyle (1 + x)^n = \sum_{k = 0}^n {n \choose k} x^k.$

However, how do we actually compute $\displaystyle {n \choose k}$ ? For some nontrivial insight, let’s analyse the case ${5 \choose 3}$ , so that we find the arrangements of the objects

$x, x, x, 1, 1.$

If we treated all of these object as different from one another, we aim to find arrangements of the objects

$x_1, x_2, x_3, x_4, x_5.$

Crucially, we want to arrange these objects without repetitions. We call such arrangements permutations.

Let $K = \{x_1,\dots, x_n\}$ be a finite set with $n$ distinct elements.

Theorem 3. An arrangement $(x_1,\dots,x_n)$ of objects in a set $K$ is called a permutation of $K$ if for any $i \neq j$ , $x_i \neq x_j$ . Then the number of permutations is given by $n!$ , called $n$ –factorial, defined by

$n! := n \times (n - 1) \times \cdots \times 2 \times 1.$

Proof. For convenience, define $0! := 1$ and for any $n \in \mathbb N^+$ ,

$n! := n \cdot (n-1)!.$

Then it is clear that

$n! = n \times (n - 1) \times \cdots \times 2 \times 1.$

We will prove the claim inductively on $n$ . For the base case, the one and only permutation of $\{x_1\}$ is $x_1$ . Therefore, the number of permutations is $1 = 1!$ .

Now for the inductive step, consider a set $K = \{x_1,\dots,x_k, x_{k+1} \}$ of $k+1$ distinct elements. There are $k+1$ possible choices for the last term $x_{k+1}'$ in the sequence. Now the set $K \backslash \{x_{k+1}'\}$ has $k$ elements. By the induction hypothesis, there are $k!$ permutations of the elements in the first $k$ slots. By the multiplication principle, the total number of permutations is

$k! \times (k+1) = (k+1)!,$

as required.

Corollary 1. The number of permutations of $\{ x_4,x_5 \}$ is $2! = 2$ and the number of permutations of $\{x_1,x_2,x_3\}$ is $3! = 6$ .

Proof. We have $2! = 2 \times 1! = 2 \times 1 = 2$ and $3! = 3 \times 2! = 3 \times 2 = 6$ .

We are almost there. We observe that given these labels, the permutations

$(x_1,x_2,x_3,x_4,x_5),\quad (x_1,x_2,x_3,x_5,x_4)$

are distinct. However, if we recall that $x_1,x_2,x_3$ are placeholders for $x$ and $x_4,x_5$ are placeholders for $1$ , then we obtain the identical permutations

$(x, x ,x , 1, 1),\quad (x, x, x , 1, 1).$

In fact, we can flip the question: how many permutations correspond to the overarching arrangement $(x, x, x, 1, 1)$ ? It would be the contribution of all permutations of $\{x_1,x_2,x_3\}$ and all permutations of $\{x_4,x_5\}$ . If there are $\displaystyle {5 \choose 3}$ overarching arrangements of $3$ copies of $x$ and $2$ copies of $1$ , then the multiplication principle yields

$\displaystyle {5 \choose 3} \times 3! \times 2! = 5!\quad \Rightarrow \quad {5 \choose 3} = \frac{5!}{3! \times 2!}.$

Extending this reasoning to $k$ copies of $x$ and $n$ copies of $1$ yields the computation of the binomial coefficient.

Theorem 4. For any $n \in \mathbb N^+$ and $k \in \mathbb N_0$ with $k \leq n$ , the $k$ -th binomial coefficient is given by $\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}$ .

Intriguingly, these two quantities, the factorial $n!$ and binomial coefficient $\displaystyle {n \choose k}$ help us discuss more about permutations and combinations.

Definition 1. Let $K = \{x_1,\dots,x_n\}$ be a set of $n$ elements. For integers $0 \leq k \leq n$ , a $k$ –combination of $K$ is a subset of $K$ (so that the collection of combinations of $K$ is $\mathcal P(K)$ ) and a $k$ –permutation is a permutation of some $k$ -combination of $K$ .

Given $k$ , how many $k$ -combinations are there? Furthermore, how many $k$ -permutations are there? We have seen that the number of $n$ -permutations is $n!$ , and clearly the number of $n$ -combinations is $1$ . More concretely, given $0 \leq k \leq n$ , we want to count

$\mathcal S_k := \{S \in \mathcal P(K) : |S| = k\}.$

Our key idea is as follows: fix $S \subseteq K$ such that $|S| = k$ . Form a sequence of $x$ and $1$ as follows: declare the $i$ -th term to be $x$ if $x_i \in S$ and $1$ otherwise. We formalise this construction in Lemma 1 below:

Lemma 1. For any $S \subseteq K$ , define $f_S \in \{1, x \}^n$ by

$f_S(i) = \begin{cases} x, & x_i \in S, \\ 1, & x_i \notin S. \end{cases}$

Then the map $f : \mathcal P(K) \to \{1, x\}^n$ defined by $f(S) := f_S$ is bijective.

In particular, $f(\mathcal S_k)$ corresponds to the number of arrangements of $k$ copies of $x$ and $(n-k)$ copies of $1$ . But we have computed this number already—it is $\displaystyle {n \choose k}$ . Hence, we have the following result.

Theorem 5. The number of $k$ -combinations of a set of $n$ distinct elements is $\displaystyle {n \choose k}$ . The number of $k$ -permutations of the same set of elements is $\displaystyle {n \choose k} \times k!$ .

Proof. The first claim follows from

$\displaystyle |\mathcal S_k| = |f(\mathcal S_k)| = {n \choose k}.$

For the second claim, we first have $\displaystyle {n \choose k}$ choices of $k$ -combinations, followed by $k!$ permutations of the elements in each $k$ -combination. The result follows from the multiplication principle.

There is a lot more that can be said about counting, studied in a much broader field called combinatorics. For now, we have convinced ourselves (somewhat) that we are able to compute $|K|$ for various kinds of sets $K$ , be it collections of permutations or combinations, with repetitions or otherwise.

—Joel Kindiak, 24 Jun 25, 1810H

KindiakMath

How to Count

Response

Leave a comment Cancel reply

How to Count

Share this:

Response

Leave a comment Cancel reply