10.15 Counting Formula

Counting Permutations

Suppose four friends go to a restaurant, and each checks his or her coat. At the end of the meal, the four coats are randomly returned to the four people. What is the probability that each of the four people gets his or her own coat? Here the total number of different ways the coats can be returned is equal to \(4!\). Only one of these assignments is correct. Hence, the probability that each of the four people gets his or her own coat is equal to \(\frac{1}{4!}\)

Here we are counting permutations, or sequences of elements from a set where no element appears more than once. We can use the multiplication principle to count permutations more generally.
For example, suppose that we have the set \(S\) with \(n\) different objects and we want to count the number of permutations of length \(k \leq n\) obtained from \(S\), i.e., we want to count the number of elements of the set

\[ \{s_{1}, \dots, s_{k} : s_{i} \in S, s_{i} \neq s_{j} \text{ when }i \neq j\} \]

Then we have \(n\) choices for the first element \(s_1\), \(n-1\) choices for the second element, and finally \(n-k+1\) choices for the last element. So there are \(n(n-1)\dots(n-k+1)\) permutations of length \(k\) from a set of \(n\) elements.

This can also be written as \(\frac{n!}{(n-k)!}\). Notice that when \(k=n\) there are \(n!\)

Counting Subsets

Suppose 10 fair coins are flipped. What is the probability that exactly seven of them are heads? Here each possible sequence of 10 heads or tails (e.g., H H H T T T H T T T, T H T T T T H H H T, etc.) is equally likely, and by the multiplication principle the total number of possible outcomes is equal to 2 multiplied by itself 10 times, or \(2^{10} = 1024\). Hence, the probability of any particular sequence occurring is \(\frac{1}{1024}\). But of these sequences, how many have exactly seven heads?

To answer this, notice that we may specify such a sequence by giving the positions of the seven heads, which involves choosing a subset of size 7 from the set of possible indices \(\{1, \dots, 10\}\). There are \(\frac{10!}{3!} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4\) different permutations of length 7 from \(\{1, \dots, 10\}\), and each such permutation specifies a sequence of seven heads and three tails.
But we can permute the indices specifying where the heads go in 7! different ways without changing the sequence of heads and tails. So the total number of outcomes with exactly seven heads is equal to \(\frac{10!}{3!7!} = 120\)
The probability that exactly seven of the 10 coins are heads is therefore equal to \(\frac{120}{1024}\), or just under \(12\%\).

In general, if we have a set \(S\) of \(n\) elements, then the number of different subsets of size \(k\) that we can construct by choosing elements from \(S\) is

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

which is called the binomial coefficient.
This follows by the same argument, namely, there are \(\frac{n!}{(n-k)!}\) permutations of length \(k\) obtained from the set; each such permutation, and the \(k!\) permutations obtained by permuting it, specify a unique subset of \(S\).

Counting Sequences of Subsets and Partitions

When we want to divide a larger set into several smaller, non-overlapping subsets, we can use a powerful counting method based on the multiplication principle. For example, how many different ways can a deck of 52 cards be divided up into four hands of 13 cards each, with the hands labelled North, East, South, and West, respectively?

North Hand (\(\mathit{N}\) ) : Choose 13 cards from 52: \(\binom{52}{13}\)
East Hand (\(\mathit{E}\) ) : 39 cards remain. Choose 13 from 39: \(\binom{39}{13}\)
South Hand (\(\mathit{S}\) ) : 26 cards remain. Choose 13 from 26: \(\binom{26}{13}\)
West Hand (\(\mathit{W}\) ) : 13 cards remain. Choose 13 from 13: \(\binom{13}{13} = 1\)

The total number of ways is the product of these combinations:

\[ \text{Total Ways }=\binom{52}{13}\cdot \binom{39}{13}\cdot \binom{26}{13}\cdot \binom {13}{13} \]

This equals \(\binom{52}{13,13,13,13}= \frac{52!}{13!13!13!13!}\approx 5.364 \times 10^{28}\) which is a very large number.

In general, suppose we have a set \(S\) of \(n\) elements and we want to count the number of elements of

\[ \{S_1, S_2, \dots, S_l : S_i \subset S, |S_i| = k_i, S_i \cap S_j = \emptyset \text{ when } i \neq j\} \]

namely, we want to count the number of sequences of \(l\) subsets of a set where no two subsets have any elements in common and the \(i\)-th subset has \(k_i\) elements.

By the multiplication principle, this equals

\[ \binom{n}{k_1}\binom{n-k_1}{k_2}\dots \binom{n-k_1-\dots-k_{l-1}}{k_l}= \frac{n!}{k_{1}! \dots k_{l-1}! (n-k_{1}-\dots-k_{l-1})!} \]

because we can choose the elements of \(S_1\) in \(\binom{n}{k_1}\) ways, choose the elements of \(S_2\) in \(\binom{n-k_1}{k_2}\) ways, etc.
When we have that \(S = S_1 \cup S_2 \cup \dots \cup S_l\), in addition to the individual sets being mutually disjoint, then we are counting the number of ordered partitions of a set of \(n\) elements with \(k_1\) elements in the first set, \(k_2\) elements in the second set, etc. In this case, the previous expression equals

\[ \binom{n}{k_1, k_2, \dots, k_l} = \frac{n!}{k_1! k_2! \dots k_l!} \]

which is called the multinomial coefficient.

Borel \(\sigma\)-algebra

Fact: Any open set \(A \subset \mathbb{R}\) is a countable union of open intervals.

Proof

Let \(A\) be a non-empty open set in \(\mathbb{R}\). For each point \(x \in A\), there exists an open interval \((a,b)\) such that \(x \in (a,b) \subset A\).
Consider the set of all open intervals with rational endpoints that are subsets of \(A\):

\[ S = \{(p, q) \mid p, q \in \mathbb{Q} \text{ and } (p, q) \subset A\} \]

The set \(S\) is countable because the set of all pairs of rational numbers \(\mathbb{Q} \times \mathbb{Q}\) is countable.
We now show that \(A = \bigcup_{(p,q) \in S} (p, q)\).

(\(\subseteq\)) Let \(x \in A\). Since \(A\) is an open set, there exists an open interval \((a, b)\) such that \(x \in (a, b) \subset A\). Because the rational numbers are dense in \(\mathbb{R}\), we can choose rational numbers \(p\) and \(q\) such that \(a < p < x < q < b\). This implies that \(x \in (p, q)\) and \((p, q) \subset (a, b) \subset A\). Therefore, the interval \((p, q)\) is in the set \(S\), and thus \(x\) is in the union \(\bigcup_{(p,q) \in S} (p, q)\).

(\(\supseteq\)) This direction is straightforward. Every interval \((p, q)\) in the union is a subset of \(A\) by the definition of the set \(S\). Therefore, their union must also be a subset of \(A\).

Since both inclusions hold, we have \(A = \bigcup_{(p,q) \in S} (p, q)\). As the set \(S\) is countable, \(A\) is a countable union of open intervals.

Definition

We say that \(\sigma\)-algebra \(\mathcal{F}\) is generated by a set \(\mathcal{S} \subset \mathcal{F}\) if \(\mathcal{F}\) is the smallest \(\sigma\)-algebra that contains \(\mathcal{S}\). We write \(\mathcal{F}=\sigma(\mathcal{S})\).

Recall that we have defined the Borel \(\sigma\)-algebra, \(\mathcal{B}(\mathbb{R})\), as the one generated by open intervals on the real line. Also, we know for set \(A,B\), \(\sigma(A)=\{\empty,A,A^{c},\Omega\}\) and \(\sigma(A,B)=\{\empty,A,B,A^{c},B^{c},A\cup B,...\}\)
However, a fundamental result is that this definition is equivalent to considering the \(\sigma\)-algebra generated by semi-infinite intervals of the form \((-\infty, a]\). Below, we will formally demonstrate this equivalence.

Theorem

The Borel \(\sigma\)-algebra \(\mathcal{B}(\mathbb{R})\) is generated by intervals of the form \((-\infty, a]\), \(a \in \mathbb{R}\)

Proof

Let \(\mathcal{D}\) denote the collection of intervals of the form \((-\infty, a]\), \(a \in \mathbb{R}\). In the example we prove that \(\mathcal{D} \subset \mathcal{B}(\mathbb{R})\), therefore \(\sigma(\mathcal{D}) \subset \mathcal{B}(\mathbb{R})\).
Now in order to prove the other inclusion, let us denote by \(\mathcal{O}\) the collection of all open intervals.
Of course \(\mathcal{B}(\mathbb{R}) = \sigma(\mathcal{O})\).
One easily sees that any open interval \((a, b) \in \sigma(\mathcal{D})\):

\[ (a, b) = \bigcup_{n=1}^{\infty}(-\infty, b + \frac{1}{n}] \setminus (-\infty, a] = \bigcup_{n=1}^{\infty}((-\infty, b + \frac{1}{n}] \cap (-\infty, a]^{c}). \]

Thus \(\mathcal{O} \subset \sigma(\mathcal{D})\) which means \(\mathcal{B}(\mathbb{R}) = \sigma(\mathcal{O}) \subset \sigma(\mathcal{D})\).

Remark

Analogous statements are true for \(\mathbb{R}^d, d>1\), that is

any open set in \(\mathbb{R}^d\) is a countable union of \((a_1,b_1)\times\cdots\times(a_d,b_d)\).
sets \(\{(-\infty, a_1]\times\cdots\times(-\infty, a_d] \mid (a_1,\ldots,a_d)\in\mathbb{R}^d\}\) generate \(\mathcal{B}(\mathbb{R}^d)\).