Probability/Combinatorics

Template:Nav We all know how to count. However, counting can actually be quite complicated, and there are many sophisticated techniques related to counting. In this chapter, we will introduce some basic techniques, which are the basis for calculating Template:Colored em (discussed in next chapter). Those techniques make use of the Template:Colored em heavily, discussed in the following section.

Fundamental counting principles

Just as there are four kinds of basic operations in mathematics: addition, subtraction, multiplication, division, there are four corresponding fundamental principles in counting: addition, subtraction, multiplication, division counting principles.

Addition and subtraction counting principles

Template:Colored proposition Template:Colored remark More generally, we have the Template:Colored em counting principle: Template:Colored proposition Template:Colored remark Actually, the previous two principles of counting are just special cases of a more general principle: Template:Colored em. Template:Colored theorem Template:Colored remark Template:Colored example Template:Colored example

Multiplication counting principle

Proof. We prove it by mathematical induction. Let $P(n)$ be the statement

"If there are $m_1,m_2,\dots ,m_n$ ways to do the task $1,2,\dots ,n$ respectively, then there are $m_1\times m_2\times \cdots \times m_n$ ways to do the $n$ tasks."

Basis Step: Assume there is $m_1$ ways to do the task 1. Then clearly there is $m_1$ ways to do this one task. So, $P(1)$ is clearly true.

Inductive Hypothesis: Let $k$ be an arbitrary positive integer. Assume that $P(k)$ is true. That is, assume that

"If there are $m_1,m_2,\dots ,m_k$ ways to do the task $1,2,\dots ,k$ respectively, then there are $m_1\times m_2\times \cdots \times m_k$ ways to do the $k$ tasks."

is true.

Inductive Step: We want to show that $P(k+1)$ is true. So, we now assume that there are $m_1,m_2,\dots ,m_k,m_{k+1}$ ways to do the task $1,2,\dots ,k,k+1$ respectively. By the inductive hypothesis, there are $m_1\times m_2\times \cdots \times m_k$ ways to do the first $k$ tasks (task $1,2,\dots ,k$). Now, for Template:Colored em of the $m_1\times m_2\times \cdots m_k$ ways of doing the first $k$ tasks, there are $m_{k+1}$ ways to do the task $k+1$. Expressing it using a table, we have $$\begin{array}{cc}\text{ways of doing the first }k\text{ tasks}& \text{number of ways to do task }k+1\\ \text{way 1}& m_{k+1}\\ \text{way 2}& m_{k+1}\\ ⋮& ⋮\\ \text{way }{m}_1\times m_2\times \cdots m_k& m_{k+1}\end{array}$$ Hence, the number of ways of doing the $k+1$ tasks (the first $k$ tasks, and the task $k+1$) is $$\underset{m_1\times m_2\times \cdots m_k\text{ times}}{\underbrace{m_{k+1}+m_{k+1}+\cdots +m_{k+1}}}=(m_1\times m_2\times \cdots \times m_k)m_{k+1}=m_1\times m_2\times \cdots \times m_{k+1}.$$ So, $P(k+1)$ is true.

Thus, by the principle of mathematical induction, $P(n)$ is true for every positive integer $n$.

$◻$

Template:Colored remark When we are using the multiplication counting principle to solve some counting problems, we need to be careful about the following:

• We need to ensure that the number ways of doing each task are Template:Colored em, and should not depend on the way of doing the other tasks. (See the following example.)
• After using the multiplication counting principle to count the number of ways to do the $n$ tasks, it is possible that some of the ways (or "decision paths", i.e., the paths that we "go through" the tree diagram) actually correspond to the Template:Colored em under the situation in a problem, so the those ways should only be counted as one outcome in that context. (See the following example.)

Division counting principle

Template:Colored theorem Graphically, it looks like $$\begin{array}{cc}\text{Task }& \text{ Procedure}\\ \text{HLINE TBD}\text{way 1}\leftrightarrow & \{\begin{array}{c}\text{way 1}\\ \text{way 2}\\ ⋮\\ \text{way }d\end{array}\\ \text{way 2}\leftrightarrow & \{\begin{array}{c}\text{way 1}\\ \text{way 2}\\ ⋮\\ \text{way }d\end{array}\\ ⋮\\ \text{way }\frac{n}{d}\leftrightarrow & \{\begin{array}{c}\text{way 1}\\ \text{way 2}\\ ⋮\\ \text{way }d\end{array}\\ \text{HLINE TBD}& \text{Total}:\frac{n}{d}\times d=n\text{ ways for the procedure}\end{array}$$ Template:Colored example Template:Colored example Template:Colored example We should be aware that the division counting principle does not apply if different ways of doing task correspond to Template:Colored em number of ways in the procedure. Consider the following examples: Template:Colored example Template:Colored example

Number of ways for placing r balls into n cells

In this section, we will discuss how to count the number of ways for placing $r$ balls into $n$ cells. From here, one may then ask why do we consider this particular situation, and it may seem that we rarely encounter this situation in practice. Often, we want to count the number of ways for doing things other than placing balls into cells.

Although many situations encountered may seem to be quite different from this situation, particularly, the background is usually not about placing balls into cells, we may Template:Colored em them as if we are placing balls into cells. Indeed, many situations are so-called "abstractly equivalent", in the sense that the underlying process of "generating" the outcomes is the same, but we just have different verbal descriptions.

Let us consider some situations that are abstractly equivalent to "placing $r$ balls into $n$ cells" (for some $n$ and $r$):

1. Number of possible birthdays for 10 people: placing 10 "people" (balls) into 365 "birthday dates" (cells). (Here, we assume one year has only 365 days.) Notice that we are Template:Colored em placing 365 "birthday dates" into 10 "people". (If this is this case, some people have more than one birthday!) Notice also that we can place more than one person into the same "birthday date". (Multiple people can share the same birthday!)
2. Setting a 6-digit numeric password: placing 6 "password positions" (balls) into 10 "numbers" (cells) (0,1,...,9). (Likewise, we are Template:Colored em placing "numbers" into "password positions". If this is the case, then some password position contains Template:Colored em number, which is impossible.)
3. Classification of 1000 people into ages 0-10, 11-20, ..., 91-100, 101 or above: placing 1000 "people" (balls) into 11 "age groups" (cells).
4. Elevator with 20 passengers and stopping at 10 floors: placing 20 "passengers" (balls) into 10 "floors" (cells).
5. 3 pigeons flying into 2 pigeonholes: placing 3 "pigeons" (balls) into 2 "pigeonholes" (cells).
6. Rolling 10 dice: placing 10 "dice" (balls) into 6 "outcomes" (cells).
7. Drawing 3 cards from a poker deck: placing 3 "draws" (balls) into 52 "cards" (cells).
8. Tossing 2 coins: placing 2 "coin tosses" (balls) into 2 "outcomes" (cells).
9. Select 5 people from 20 people to form a committee: placing 5 "committee positions" (balls) into 20 "people" (cells).

In this section, we will mainly develop some formulas for calculating the number of ways to select some objects from distinguishable objects, Template:Colored em, classified by whether the selection is Template:Colored em, and whether the selection is Template:Colored em. We can apply the above notion of "abstract equivalence" to convert such selection as a problem of placing some distinguishable or indistinguishable balls into some distinguishable cells with certain capacity, so that we can develop the formula more easily and conveniently. (As we will see, the distinguishability of balls corresponds to whether the selection is ordered or not, and the capacity of the cells correspond to whether the selection is with or without replacement.)

Before discussing these four types of selection, we need to introduce a preliminary mathematical concept which will be used frequently in the following: Template:Colored definition

Placing r distinguishable balls into n distinguishable cells with capacity one (ordered selection without replacement)

Let us first discuss ordered selection of $r$ objects from $n$ objects without replacement. We can regard this to be abstractly equivalent to placing $r$ distinguishable balls (choice 1,2,...,$r$) into $n$ distinguishable cells (object 1,2,...,$n$) with capacity one.

• The capacity is one, since Template:Colored em, we are unable to choose the same object multiple times (unable to put two or more balls (choices) into the same cell (object))

After that, we develop the following formula. Template:Colored theorem

Proof. We consider the placement as a $r$-step process:

• for the 1st ball, there are $n$ vacant cells left. So, there are $n$ ways of placing the ball into a cell.
• for the 2nd ball, there are $n-1$ vacant cells left. So, there are $n-1$ ways of placing the ball into a cell.
• ...
• for the $r$th ball, there are $n-(r+1)$ vacant cells left. So, there are $n-(r+1)$ ways of placing the ball into a cell.

Thus, by multiplication principle of counting, the desired number of ways is $$\underset{\text{ball 1}}{\underbrace{n}}\times \underset{\text{ball 2}}{\underbrace{(n-1)}}\times \cdots \times \underset{\text{ball }r}{\underbrace{(n-r+1)}}=\frac{n\times (n-1)\times \cdots \times (n-r+1)\times (n-r)\times \cdots \times 1}{(n-r)\times \cdots \times 1}=\frac{n!}{(n-r)!}.$$

$◻$

Template:Colored example Template:Colored example Template:Colored example Template:Colored example Template:Colored example Template:Colored example The situation in the example above can actually be interpreted as a special case of Template:Colored em.

Partition

For permutating the string "APPLE", we can regard the situation as partitioning 5 (distinguishable and ordered) Template:Colored em into 4 groups: "A", "P", "L", and "E", where we require the group "A", "P", "L", "E" to contain 1,2,1,1 letter positions respectively. Similarly, for permutating the string "PEPPER", we can regard the situation as partitioning 5 (distinguishable and ordered) Template:Colored em into 3 groups: "P", "E" and "R" where we require the group "P", "E", "R" to contain 3,2,1 letter positions respectively.

Such situation is actually abstractly equivalent to placing distinguishable balls into distinguishable cells, with some restrictions on the number of balls each cell Template:Colored em contain. Generally, "partitioning $n$ distinguishable objects into $k$ groups, where group 1,2,...,$k$ must contain $n_1,n_2,\dots ,n_k$ objects respectively" (Merely changing the order of placing the objects into a certain group do not affect the partition, since the group still contains the same thing at the end.) is abstractly equivalent to "placing $n$ distinguishable balls into cell 1,2,...,$k$, where cell 1,2,...,$k$ must contain $n_1,n_2,\dots ,n_k$ balls respectively". Template:Colored theorem

Proof. First, we consider a procedure where we regard cell 1,2,...,$k$ contains $n_1,n_2,\dots ,n_k$ Template:Colored em for placing one ball each (e.g., there are $n_1,n_2,\dots ,n_k$ "subcells" in cell 1,2,...,$k$). In this case, we can just regard the placement as a permutation of the $n$ distinguishable balls, since the $k$ cells altogether contain $n$ "ordered positions" ("subcells"). After having such consideration, the number of ways of placement is $n!$.

But of course we do not have such "subcells" actually. So, we will use the division counting principle. Given a particular partition in the "task", there are $n_1!,n_2!,\dots ,n_k!$ ways to permutate the distinguishable balls in the subcells of cell 1,2,...,$k$ respectively, so there are altogether $n_1!n_2!\dots n_k!$ ways in the procedure that correspond to one way in the "task". Hence, by the division counting principle, there are $\frac{n!}{n_1!n_2!\dots n_k!}$ ways for the partition.

$◻$

Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored exercise Template:Colored example Template:Colored example In the following, we will discuss unordered selection without replacement, which can be regarded as a special case of partition.

Placing r indistinguishable balls into n distinguishable cells with capacity one (unordered selection without replacement)

Previously, we have discussed placing $r$ Template:Colored em balls into $n$ distinguishable cells with capacity one. Now, we will consider the case where the $r$ balls are Template:Colored em. (One may conceive the balls to be Template:Colored em (say same color and size), and hence indistinguishalble.) Similarly, such placement is equivalent to selection without replacement (the $r$ balls represent the choices, and every cell can still contain at most one ball). However, in this case, the $r$ balls (choices) are indistinguishable. So, we only know that which $r$ of the $n$ cells contain one ball (are selected), but do not know in Template:Colored em do they contain one ball, since the balls are indistinguishable. Hence, the order for which the cells contain one ball (are selected) is not important in this case, since we cannot identify the different orders of selection anyways. Hence, we consider the selection process as Template:Colored em. Such selection process is quite common since we are often more interested in knowing Template:Colored em are selected, and are not quite interested in in Template:Colored em the things are selected.

In this case, we can actually regard this as a special case of partition:

• For the cells with one ball ($r$ of them), they are put into the group "selected" (they are selected to place one ball).
• For the cells with zero ball ($n-r$ of them), they are put into the group "not selected" (they are not selected to place one ball).

So, this means such placement is equivalent to the partition of $n$ distinguishable cells into two groups with $r$ distinguishable cells and $n-r$ distinguishable cells respectively. With such consideration, the following result is transparent: Template:Colored theorem Here, we give an alternative proof to this theorem which uses the previous result for distinguishable balls and the division counting principle:

Proof. From the previous result for distinguishable balls, there are $\frac{n!}{(n-r)!}$ ways for placing $r$ distinguishable balls into $n$ distinguishable cells with capacity one. But here we want the number of ways where the balls are indistinguishable. So, we consider the division counting principle: every placement where the balls are indistinguishable corresponds to $r!$ placements (obtained by permutating the $r$ distinguishable balls) where the balls are distinguishable. It follows that the desired number of ways is $$\frac{n!}{(n-r)!}/r!=\frac{n!}{r!(n-r)!}.$$

$◻$

Placing r distinguishable balls into n distinguishable cells with unlimited capacity (ordered selection with replacement)

So far, we have only considered the selection Template:Colored em replacement, or equivalently, cells with Template:Colored em. From this section onward, we will discuss the selection Template:Colored em replacement, or equivalently, cells with Template:Colored em (same thing can be chosen unlimited times). In this section, let us consider the simpler one: placing $r$ distinguishable balls into $n$ distinguishable cells with unlimited capacity. This is equivalent to ordered selection of $r$ objects from $n$ distinguishable objects with replacement, by regarding the ball 1,2,...,$r$ as choice 1,2,...,$r$, cell 1,2,...,$n$ as object 1,2,...,$n$. In particular, since every object can be chosen unlimited times, every cell has unlimited capacity. But counting the number of ways of such placement is actually quite simple, since we can just use the multiplication counting principle. Template:Colored proposition

Proof. We consider the placement as a $r$-step process:

• Step 1: choose one of the $n$ cells to place ball 1. ($n$ ways)
• Step 2: choose one of the $n$ cells to place ball 2. ($n$ ways)
• ...
• Step $r$: choose one of the $n$ cells to place ball $r$. ($n$ ways)

Altogether, by the multiplication counting principle, the number of ways is $$\underset{r\text{ times}}{\underbrace{n\times n\times \cdots \times n}}=n^r.$$

$◻$

Placing r indistinguishable balls into n distinguishable cells with unlimited capacity (unordered selection with replacement)

In the previous section, the balls are distinguishable. Now, we will discuss a more complicated situation where the balls are indistinguishable.

The challenging part of this situation is that we cannot apply the division counting principle to count the number of ways, as in the previous situation about placing $r$ indistinguishable balls into $n$ distinguishable cells with capacity one ("task"). In that previous situation, we know that every way in the task corresponds to $r!$ ways in the procedure (where we are placing $r$ distinguishable balls), by considering the number of ways of permutating the $r$ cells occupied by Template:Colored em.

However, in this case, every cell can contain more than one ball. This means the number of occupied cells can range from 1 (all $r$ balls in one cell) to $r$ (one ball each for the $r$ cells), depending on how we put the balls into the cells in the task. Hence, different ways in the task correspond to different number of ways in the procedure. Thus, we cannot apply the division counting principle.

Because of this, the method for developing the number of ways in this situation is quite different from the methods discussed previously, and we need some tricks. Template:Colored theorem

Proof. To prove this, we introduce the stars and bars notation, to represent the placement of balls into cells. In particular, $r$ (identical) stars are used to represent the $r$ indistinguishable balls, and $n$ (ordered) spaces created by $n-1$ bars are used to represent the $n$ distinguishable cells. For instance,

       *********     9 indistinguishable balls

           |
           |          placement
           v

  **|*| |***|*| |**   
   1 2 3  4  5 6  7  Cell

is used to represent

• 2 balls in cell 1
• 1 ball in cell 2
• 0 ball in cell 3
• 3 balls in cell 4
• 1 ball in cell 5
• 0 ball in cell 6
• 2 balls in cell 7.

Also, in this case, we are placing $r=9$ indistinguishable balls into $n=7$ cells.

After introducing this notation, we are going to count the number of ways of arranging such stars and bars, since Template:Colored em arrangement of stars and bars correspond to Template:Colored em placement of the $r$ indistinguishable balls into $n$ distinguishable cells. So, that number of ways of the arrangement is exactly the number of ways for such placement of balls into cells.

The $n-1$ bars and $r$ stars can be arbitrarily arranged, to represent different placements. Altogether, there are $n-1+r$ (ordered and distinguishable) positions for placing a star or a bar. Here, we focus ok the placement of stars. We can interpret this as an unordered selection of $r$ positions from these $n-1+r$ positions to place stars, without replacement (when a star is placed at a position, we cannot place another one at the same position). Hence, the number of ways is $(\genfrac{}{}{0ex}{}{n-1+r}{r})$. Once we place the $r$ stars, there is only 1 way to place the bars: place them into the remaining positions.

It then follows that there are $(\genfrac{}{}{0ex}{}{n-1+r}{r})$ ways to arrange the $n-1$ bars and $r$ stars, and hence the result follows.

$◻$

Summary

Placing $r$ balls into $n$ distinguishable cells

	cells with capacity one	cells with unlimited capacity
distinguishable balls	$$n^r$$	$$\frac{n!}{(n-r)!}$$
indistinguishable balls	$$(\genfrac{}{}{0ex}{}{n-1+r}{r})$$	$$(\genfrac{}{}{0ex}{}{n}{r})$$

Template:Colored exercise Alternatively and equivalently,

Selecting $r$ objects from $n$ distinguishable objects

	with replacement	without replacement
ordered	$$n^r$$	$$\frac{n!}{(n-r)!}$$
unordered	$$(\genfrac{}{}{0ex}{}{n-1+r}{r})$$	$$(\genfrac{}{}{0ex}{}{n}{r})$$

Indistinguishable cells

When the Template:Colored em are indistinguishable, there are no simple and nice formulas for counting the number of ways generally. Also, in this case, it may be more difficult to imagine what "indistinguishable cells" look like, since even the cells are identical, their positions should be different so that the balls can be placed in different cells. Then, the cells are still distinguishable. To visualize indistinguishable cells, one may conceive that after the balls are placed into the cells, the cells are "sorted", based on the number of balls they contain, with the cell with least balls placed at leftmost, and the cell with most balls placed at rightmost. (The cells with the same number of balls can just be put together, in any order.) Then, after "throwing" the balls into the cells Template:Colored em the cells are sorted, we can look at the cells to observe the results. In this case, the cells can be regarded as indistinguishable, since we only know how many cells contain zero, one, etc. balls, but not precisely which of the original cell 1,2,.. contains how many balls (we cannot tell which cell is the original "cell 1,2,..." after sorting).

When we encounter indistinguishable cells, we may need to consider the ways one by one. Template:Colored example

A powerful tool for counting problems: generating functions

Template:Colored definition Template:Colored remark The following theorem gives some common generating functions. Template:Colored theorem Template:Colored remark Template:Colored example Template:Colored example Template:Colored example Template:Colored example Template:Colored remark Template:Colored example Template:Colored example Template:Colored exercise