eBook › Chapter 1 · Mathematical Background

Section 1.5

Basic Combinatorics

The last topic we review in this chapter is combinatorics. Combinatorics concerns the number of configurations that can be obtained from certain discrete experiments. It is useful because it provides a systematic way of enumerating cases. Combinatorics often becomes very challenging as the complexity of the event grows. However, you may rest assured that in this book, we will not tackle the more difficult problems of combinatorics; we will confine our discussion to two of the most basic principles: permutation and combination.

1.5.1Birthday paradox

To motivate the discussion of combinatorics, let us start with the following problem. Suppose there are 50 people in a room. What is the probability that at least one pair of people have the same birthday (month and day)? (We exclude Feb. 29 in this problem.)

The first thing you might be thinking is that since there are 365 days, we need at least 366 people to ensure that one pair has the same birthday. Therefore, the chance that 2 of 50 people have the same birthday is low. This seems reasonable, but let's do a simulated experiment. In Figure 1.16 we plot the probability as a function of the number of people. For a room containing 50 people, the probability is 97%. To get a 50% probability, we just need 23 people! How is this possible?

**Figure 1.16.** The probability for two people in a group to have the same birthday as a function of the number of people in the group.

If you think about this problem more deeply, you will probably realize that to solve the problem, we must carefully enumerate all the possible configurations. How can we do this? Well, suppose you walk into the room and sequentially pick two people. The probability that they have different birthdays is

\begin{aligned} \Pb[\text{The first 2 people have different birthdays}] = \frac{365}{365} \times \frac{364}{365}. \end{aligned}

When you ask the first person to tell you their birthday, he or she can occupy any of the 365 slots. This gives us $\frac{365}{365}$. The second person has one fewer slot because the first person has taken it, and so the probability that he or she has a different birthday from the first person is $\frac{364}{365}$. Note that this calculation is independent of how many people you have in the room because you are picking them sequentially.

If you now choose a third person, the probability that they have different birthdays is

\begin{aligned} \Pb[\text{The first 3 people have different birthdays}] = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365}. \end{aligned}

This process can be visualized in Figure 1.17.

So imagine that you keep going down the list to the 50th person. The probability that none of these 50 people will have the same birthday is

\begin{aligned} &\Pb[\text{The first 50 people have different birthdays}] \\ &= \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{316}{365} \approx 0.03. \end{aligned}

That means the probability for 50 people to have different birthdays is as little as 3%. If you take the complement, you can show that with 97% probability, there is at least one pair of people having the same birthday.

The general equation for this problem is now easy to see:

\begin{aligned} \Pb[\text{The first $k$ people have different birthdays}] &= \frac{365 \times 364 \times \cdots \times (365-k+1)}{365 \times 365 \times \cdots \times 365} \\ &= \frac{365!}{(365-k)!} \times \frac{1}{365^k}. \end{aligned}

The first term in our equation, $\frac{365!}{(365-k)!}$, is called the permutation of picking $k$ days from 365 options. We shall discuss this operation shortly.

Why is the probability so high with only 50 people while it seems that we need 366 people to ensure two identical birthdays? The difference is the notion of probabilistic and deterministic. The 366-people argument is deterministic. If you have 366 people, you are certain that two people will have the same birthday. This has no conflict with the probabilistic argument because the probabilistic argument says that with 50 people, we have a 97% chance of getting two identical birthdays. With a 97% success rate, you still have a 3% chance of failing. It is unlikely to happen, but it can still happen. The more people you put into the room, the stronger guarantee you will have. However, even if you have 364 people and the probability is almost 100%, there is still no guarantee. So there is no conflict between the two arguments since they are answering two different questions.

Now, let's discuss the two combinatorics questions.

1.5.2Permutation

Permutation concerns the following question:

Consider a set of $n$ distinct balls. Suppose we want to pick $k$ balls from the set without replacement. How many ordered configurations can we obtain?

Note that in the above question, the word “ordered” is crucial. For example, the set $A = \{a,b,c\}$ can lead to 6 different ordered configurations

\begin{aligned} (a,b,c), \; (a,c,b), \; (b,a,c), \; (b,c,a), \; (c,a,b), \; (c,b,a). \end{aligned}

As a simple illustration of how to compute the permutation, we can consider a set of 5 colored balls as shown in Figure 1.18.

If you start with the base, which contains five balls, you will have five choices. At one level up, since one ball has already been taken, you have only four choices. You continue the process until you reach the number of balls you want to collect. The number of configurations you have generated is the permutation. Here is the formula:

Theorem 1.6

The number of permutations of choosing $k$ out of $n$ is

\frac{n!}{(n-k)!}

where $n! = n(n-1)(n-2)\cdots 3 \cdot 2 \cdot 1$.

Proof. Let's list all possible ways:

Which ball to pick	Number of choices	Why?
The 1st ball	$n$	None has been picked, so we have $n$ choices
The 2nd ball	$n-1$	The first ball has been picked
The 3rd ball	$n-2$	The first two balls have been picked
$\vdots$	$\vdots$	$\vdots$
The $k$th ball	$n-k+1$	The first $k-1$ balls have been picked
Total:	$n(n-1)\cdots(n-k+1)$

The total number of ordered configurations is $n(n-1)\cdots {(n-k+1)}$. This simplifies to

\begin{aligned} &n(n-1)(n-2)\cdots(n-k+1) \\ &= n(n-1)(n-2)\cdots(n-k+1) \cdot \frac{(n-k)(n-k-1)\cdots 3 \cdot 2 \cdot 1}{(n-k)(n-k-1)\cdots 3 \cdot 2 \cdot 1} \\ &= \frac{n!}{(n-k)!}. \end{aligned}

■

Practice Exercise 1.8

Consider a set of $4$ balls $\{1,2,3,4\}$. We want to pick two balls at random without replacement. The ordering matters. How many permutations can we obtain?

Solution

The possible configurations are (1,2), (2,1), (1,3), (3,1), (1,4), (4,1), (2,3), (3,2), (2,4), (4,2), (3,4), (4,3). So totally there are 12 configurations. We can also verify this number by noting that there are 4 balls altogether and so the number of choices for picking the first ball is 4 and the number of choices for picking the second ball is $(4-1)=3$. Thus, the total is $4 \cdot 3 = 12$. Referring to the formula, this result coincides with the theorem, which states that the number of permutations is $\frac{4!}{(4-2)!}=\frac{4 \cdot 3 \cdot 2 \cdot 1}{ 2 \cdot 1} = 12$.

1.5.3Combination

Another operation in combinatorics is combination. Combination concerns the following question:

Consider a set of $n$ distinct balls. Suppose we want to pick $k$ balls from the set without replacement. How many unordered configurations can we obtain?

Unlike permutation, combination treats a subset of balls with whatever ordering as one single configuration. For example, the subset $(a,b,c)$ is considered the same as $(a,c,b)$ or $(b,c,a)$, etc.

Let's go back to the 5-ball exercise. Suppose you have picked orange, green, and light blue. This is the same combination as if you have picked $\{$green, orange, and light blue$\}$, or $\{\text{green, light blue, and orange}\}$. Figure 1.19 lists all the six possible configurations for these three balls. So what is combination? Combination needs to take these repeated cases into account.

**Figure 1.19.** Combination. In this problem, we are interested in picking 3 colored balls out of 5. This will give us $5 \times 4 \times 3 = 60$ permutations. However, since we are not interested in the ordering, some of the permutations are repeated. For example, there are 6 combos of (green, light blue, orange), which is computed from $3 \times 2 \times 1$. Dividing 60 permutations by these 6 choices of the orderings will give us 10 distinct combinations of the colors.

Theorem 1.7

The number of combinations of choosing $k$ out of $n$ is

\frac{n!}{k!(n-k)!}

where $n! = n(n-1)(n-2)\cdots 3 \cdot 2 \cdot 1$.

Proof. We start with the permutation result, which gives us $\frac{n!}{(n-k)!}$ permutations. Note that every permutation has exactly $k$ balls. However, while these $k$ balls can be arranged in any order, in combination, we treat them as one single configuration. Therefore, the task is to count the number of possible orderings for these $k$ balls.

To this end, we note that for a set of $k$ balls, there are in total $k!$ possible ways of ordering them. The number $k!$ comes from the following table.

Which ball to pick	Number of choices
The 1st ball	$k$
The 2nd ball	$k-1$
$\vdots$	$\vdots$
The $k$th ball	1
Total:	$k(k-1)\cdots 3\cdot 2\cdot 1$

Therefore, the total number of orderings for a set of $k$ balls is $k!$. Since permutation gives us $\frac{n!}{(n-k)!}$ and every permutation has $k!$ repetitions due to ordering, we divide the number by $k!$. Thus, the number of combinations is

\frac{n!}{k!(n-k)!}.

■

Practice Exercise 1.9

Consider a set of $4$ balls $\{1,2,3,4\}$. We want to pick two balls at random without replacement. The ordering does not matter. How many combinations can we obtain?

Solution

The permutation result gives us 12 permutations. However, among all these 12 permutations, there are only 6 distinct pairs of numbers. We can confirm this by noting that since we picked $2$ balls, there are exactly 2 possible orderings for these 2 balls. Therefore, we have $\frac{12}{2} = 6$ combinations. Using the formula of the theorem, we check that the number of combinations is $$\frac{4!}{2!(4-2)!} = \frac{4\cdot 3 \cdot 2 \cdot 1}{(2 \cdot 1)(2 \cdot 1)} = 6.$$

Example 1.10

(Ross, 8th edition, Section 1.6) Consider the equation

x_1 + x_2 + \cdots + x_K = N,

where $\{x_k\}$ are positive integers. How many combinations of solutions of this equation are there?

Solution

We can determine the number of combinations by considering the figure below. The integer $N$ can be modeled as $N$ balls in an urn. The number of variables $K$ is equivalent to the number of colors of these balls. Since all variables are positive, the problem can be translated to partitioning the $N$ balls into $K$ buckets. This, in turn, is the same as inserting $K-1$ dividers among $N-1$ holes. Therefore, the number of combinations is

{N-1 \choose K-1} = \frac{(N-1)!}{(K-1)!(N-K)!}.

For example, if $N = 16$ and $K = 4$, then the number of solutions is

{16-1 \choose 4-1} = \frac{15!}{3!12!} = 455.

**Figure 1.20.** One possible solution for $N = 16$ and $K = 4$. In general, the problem is equivalent to inserting $K-1$ dividers among $N-1$ balls.

Closing remark. Permutations and combinations are two ways to enumerate all the possible cases. While the conclusions are probabilistic, as the birthday paradox shows, permutation and combination are deterministic. We do not need to worry about the distribution of the samples, and we are not taking averages of anything. Thus, modern data analysis seldom uses the concepts of permutation and combination. Accordingly, combinatorics does not play a large role in this book.

Does this mean that combinatorics is not useful? Not quite, because it still provides us with powerful tools for theoretical analysis. For example, in binomial random variables, we need the concept of combination to calculate the repeated cases. The Poisson random variable can be regarded as a limiting case of the binomial random variable, and so combination is also used. Therefore, while we do not use the concepts of permutation per se, we use them to define random variables.

Which ball to pick	Number of choices	Why?
The 1st ball	\(n\)	None has been picked, so we have \(n\) choices
The 2nd ball	\(n-1\)	The first ball has been picked
The 3rd ball	\(n-2\)	The first two balls have been picked
\(\vdots\)	\(\vdots\)	\(\vdots\)
The \(k\)th ball	\(n-k+1\)	The first \(k-1\) balls have been picked
Total:	\(n(n-1)\cdots(n-k+1)\)

Which ball to pick	Number of choices
The 1st ball	\(k\)
The 2nd ball	\(k-1\)
\(\vdots\)	\(\vdots\)
The \(k\)th ball	1
Total:	\(k(k-1)\cdots 3\cdot 2\cdot 1\)