Counting
Table of Contents
1. First Rule of Counting
Suppose an ordered object is formed by a succession of \(k\) choices where there are \(n_1\) possibilities for the first choice, \(n_2\) possibilities for the second choice, and so on such that there are \(n_k\) possibilities for the kth choice. Then, the number of distinct such objects is given by:
\begin{align} \boxed{n_1 \cdot n_2 \cdot n_3 \cdot \cdots \cdot n_k} \end{align}2. Second Rule of Counting
Suppose objects are formed by a succession of \(k\) choices, but the order does not matter. If there exists an \(m\) to \(1\) surjective map from the set of ordered objects \(U'\) to the set of unordered objects \(U\), then:
\begin{align} \boxed{|U| = \frac{|U'|}{m}} \end{align}So, we can count as if order matters and then divide by \(m\). \(m\) is often easily determined by considering the unordered case, and figuring out how many ordered “variations” there are of that case.
Example: Octopus socks and shoes
Suppose we want to find the total number of ways we can put 8 distinct socks and 8 distinct shoes on an octopus, such that we must put on the sock before the shoe.
By the First Rule of Counting, the number of total ways to order all 16 objects is \(16!\). But, some sequences are not valid. Since each invalid sequence can be mapped to a valid sequence by swapping the sock and the shoe, we have a total of \(2^8\) variations on each valid sequence. Therefore, by the Second Rule of Counting, or solution is:
\begin{align} \boxed{\frac{16!}{2^8}} \notag \end{align}3. Sampling
Oftentimes, we sample from some population (a set). Sampled objects are either ordered or unordered, and can be done either with or without replacement.
It is often helpful to represent counting problems in terms of the representative problem of counting functions between two finite sets. More specifically, we want to find the number of functions \(f: X \rightarrow S\), where \(|X| = k\) and \(|S|=n\).
To fit this problem to the different cases (ordering and replacement), we can apply various conditions on \(f\):
- Restrictions on \(f\) (e.g. arbitrary, injective, surjective)
- Whether the elements of \(X\) and \(S\) are distinguishable or indistinguishable
Oftentimes, it is useful to intuitively think of \(X\) as a collection of balls, and \(S\) as a collection of bins. The function \(f\) is then the way we distribute the balls among the bins, and counting the number of functions \(f\) amounts to counting the number of ways we can distribute the balls.
3.1. Ordered Objects Sampled With Replacement
This is equivalent to counting the number of arbitrary functions such that \(X\) and \(S\) are distinguishable. If \(n\) is the total number of choices, and \(k\) is the amount of objects we want to sample, this problem is equivalent to finding the number of ways we can put \(k\) balls in \(n\) bins arbitrarily.
Here, we just use the First Rule of Counting:
\begin{align} \boxed{n^k} \end{align}3.2. Ordered Objects Sampled Without Replacement
This is equivalent to counting the number of injective functions such that \(X\) and \(S\) are distinguishable. If \(n\) is the total number of choices, and \(k\) is the amount of objects we want to sample, this problem is equivalent to finding the number of ways we can put \(k\) balls in \(n\) bins such that there is at most one ball per bin.
Here, we just use the First Rule of Counting:
\begin{align} \boxed{n(n-1)(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!}} \end{align}3.3. Unordered Objects Sampled Without Replacement
This is equivalent to counting the number of injective functions such that \(X\) (balls) are indistinguishable and \(S\) (bins) are distinguishable. If \(n\) is the total number of choices, and \(k\) is the amount of objects we want to sample, this problem is equivalent to finding the number of ways we can put \(k\) indistinguishable balls in \(n\) bins such that there is at most one ball per bin.
For such a problem, we introduce the choose notation:
\begin{align} \boxed{{n \choose k} = {n \choose n-k} = \frac{n!}{k!(n-k)!}} \end{align}3.4. Unordered Objects Sampled With Replacement
This is equivalent to counting the number of arbitrary functions such that \(X\) (balls) are indistinguishable and \(S\) (bins) are distinguishable. If \(n\) is the total number of choices, and \(k\) is the amount of objects we want to sample, this problem is equivalent to finding the number of ways we can put \(k\) indistinguishable balls in \(n\) bins arbitrarily:
However, we can use an alternative representation. Each bin is expanded into multiple consecutive bins with 1 ball per bin, and an empty bin separating each consecutive sequence:
This representation is also referred to as stars and bars, where stars are balls and bars are empty bins. This turns the problem into choosing an unordered set of \(k\) bins (to put balls in) out of a total of \(n+k-1\) bins, which is just:
\begin{align} \boxed{{n+k-1 \choose k}} \end{align}4. Combinatorial Proofs
Binomial Theorem: For all \(n \in \mathbb{N}\), we have:
\begin{align} (a+b)^n = \sum_{k=0}^n {n \choose k} a^kb^{n-k} \end{align}Proof: When we expand \((a+b)^n = (a+b)(a+b)\cdots(a+b)\), each factor contributes either \(a\) or \(b\) in each expanded term. We know that each term is of the form \(a^kb^{n-k}\). Then, the number of ways to choose exactly \(k\) factors so that they contribute \(a\) instead of \(b\) is \({n \choose k}\). \(\square\)
Lemma: For all \(n \in \mathbb{N}\), we have:
\begin{align} \sum_{k=0}^n (-1)^k {n \choose k} = 0 \end{align}Proof: By the binomial theorem when \(a=-1\) and \(b=1\). \(\square\)
Example: Proof by counting
Theorem: For all \(n, m, k \in \mathbb{Z}^+\), we have:
\begin{align} \sum_{j=0}^k {m \choose j} {n \choose k-j} = {m+n \choose k} \notag \end{align}Proof: The right hand side represents choosing \(k\) objects from \(m+n\) objects. Realize that we can divide \(m+n\) objects into two sets of \(m\) and \(n\) objects. Then, for \(j\) choices in the first set, there are \(k-j\) choices in the second set. Summing all the possibilities up, we get \(\sum_{j=0}^k {m \choose j} {n \choose k-j}\). \(\square\)
4.1. Pascal’s Triangle
Pascal’s triangle can be represented as follows:
\begin{array}{c} \binom{0}{0} \\[6pt] \binom{1}{0} \quad \binom{1}{1} \\[6pt] \binom{2}{0} \quad \binom{2}{1} \quad \binom{2}{2} \\[6pt] \binom{3}{0} \quad \binom{3}{1} \quad \binom{3}{2} \quad \binom{3}{3} \\[6pt] \binom{4}{0} \quad \binom{4}{1} \quad \binom{4}{2} \quad \binom{4}{3} \quad \binom{4}{4} \\[6pt] \binom{5}{0} \quad \binom{5}{1} \quad \binom{5}{2} \quad \binom{5}{3} \quad \binom{5}{4} \quad \binom{5}{5} \end{array}By definition, \(\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}\).
Hockey Stick Identity: For all \(n, k \in \mathbb{N}\), we have:
\begin{align} \binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{n-1}{k} = \binom{n}{k+1} \end{align}Proof: The right hand side is the number of ways to choose \(k+1\) elements from a set of \(n\) elements \(S = \{1, \dots , n\}\). Say \(j+1\) is the largest element in our sample from \(S=\{1, 2, \dots , j, j+1, \dots, n-1, n\}\). Then, we have to choose \(k\) elements from \(\{1, 2, \dots, j\}\), so it is \(\binom{j}{k}\). Since \(j\) can be from \(k\) to \(n-1\), we have \(\binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{n-1}{k}\). \(\square\)
5. Principle of Inclusion-Exclusion
Theorem: Let \(A_1, \dots , A_n\) be arbitrary subsets of the same set \(\Omega\). Then,
\begin{align} |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{k=1}^n(-1)^{k-1}\sum_{S\subseteq\{1,\dots,n\}:|S|=k} \left|\bigcap_{i\in S}A_i\right| \end{align}5.1. Permutations and Derangements
A permutation is a sample without replacement for an n-element ordered object from a set of n objects. This generates some permutation of \(\{1, 2, 3, \dots, n\}\). After permuting the set, if an element appears in the same spot, that spot is called a fixed point (e.g. \(\{1, 2, 3\} \rightarrow \{3, 2, 1\}\) has a fixed point at the element \(2\)).
A derangement is a permutation with no fixed points. Let \(D_n\) denote the number of derangements of \(\{1, 2, \dots, n\}\).
Theorem: For \(n \geq 3\), we have:
\begin{align} D_n = (n-1)(D_{n-1}+D_{n-2}) \end{align}Proof: Let \(\pi\) be a derangement for \(\{1, 2, \dots, n\}\). So, \(\pi_i \neq i\) for all \(i=1, \dots, n\).
Suppose \(\pi_n = 1\). Then, we have \(n-1\) choices to put \(n\):
\begin{matrix} \pi_1 & \pi_2 & \pi_3 & \cdots & \pi_{n-1} & \pi_n \\ n & * & * & \cdots & * & 1 \\ * & n & * & \cdots & * & 1 \\ * & * & n & \cdots & * & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ * & * & * & \cdots & n & 1 \end{matrix}In the first row, the remaining spots is just the derangement \(D_{n-2}\). Then, in the remaining rows, realize that if we treat the \(n\) as \(1\), then the remaining spots are just the derangements \(D_{n-1}\). Since we have \(n-1\) choices for \(\pi_n\), we have \(D_n = (n-1)(D_{n-1} + D_{n-2})\). \(\square\)