# Probability/Combinatorics

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 combinatorial probability (discussed in next chapter). Those techniques make use of the fundamental counting principles 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

Proposition. (Addition counting principle) If there are ${\displaystyle n_{1}}$ ways to do task 1 and ${\displaystyle n_{2}}$ ways to do task 2, but we cannot do both tasks together, then we have ${\displaystyle n_{1}+n_{2}}$ ways to do task 1 or task 2.

Remark.

• In set theoretic terms, this means if ${\displaystyle A}$ and ${\displaystyle B}$ are disjoint finite sets (containing the ways to do task 1 and 2 respectively), then ${\displaystyle |A\cup B|=|A|+|B|}$.

More generally, we have the subtraction counting principle:

Proposition. (Subtraction counting principle) If there are ${\displaystyle n_{1}}$ ways to do task 1 and ${\displaystyle n_{2}}$ ways to do task 2, and there are ${\displaystyle n_{3}}$ ways to do both tasks together, then we have ${\displaystyle n_{1}+n_{2}-n_{3}}$ ways to do task 1 or task 2.

Remark.

• An interpretation: since ${\displaystyle n_{1}+n_{2}}$ includes too many ways (some are double counted), we need to exclude the double counted ways (${\displaystyle n_{3}}$ of them).
• Setting ${\displaystyle n_{3}=0}$ gives the addition principle of counting.
• In set theoretic terms, this means if ${\displaystyle A}$ and ${\displaystyle B}$ are finite sets (containing the ways to do task 1 and 2 respectively), then ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$.
• Notice that doing task 1 or task 2 includes the possibility to do both tasks together. That is, the "or" is inclusive. In mathematics, "or" is generally taken to be inclusive.

Actually, the previous two principles of counting are just special cases of a more general principle: inclusion-exclusion principle.

Theorem. (Inclusion-exclusion principle) Let ${\displaystyle n}$ be a positive integer, and ${\displaystyle S_{1},S_{2},\dotsc ,S_{n}}$ be finite sets. Then, the cardinality of their union is

{\displaystyle {\begin{aligned}|S_{1}\cup \dotsb \cup S_{n}|&=|S_{1}|+|S_{2}|+\dotsb +|S_{n}|\\&\quad -{\big (}|S_{1}\cap S_{2}|+|S_{1}\cap S_{3}|+\dotsb +|S_{n-1}\cap S_{n}|{\big )}\\&\quad +{\big (}|S_{1}\cap S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{4}|+\dotsb +|S_{n-2}\cap S_{n-1}\cap S_{n}|{\big )}\\&\quad -\dotsb \\&\quad +(-1)^{n+1}|S_{1}\cap S_{2}\cap \dotsb \cap S_{n}|\\\end{aligned}}}

Remark.

• The name 'inclusion-exclusion principle' comes from the idea that the principle is based on over-generous inclusion, and then followed by compensating exclusion. We repeat the inclusion and exclusion process again and again, until the inclusion is perfectly accurate.
• We can regard the set ${\displaystyle S_{1},S_{2},\dotsc ,S_{n}}$ contains the ways to do task 1,2,...,${\displaystyle n}$. Then, the union ${\displaystyle S_{1}\cup S_{2}\cup \dotsb \cup S_{n}}$ contains the ways to do task 1,2,... or ${\displaystyle n}$.

Example. (Special cases of inclusion-exclusion principle) When ${\displaystyle n=2}$, the inclusion-exclusion principle gives

${\displaystyle |S_{1}\cup S_{2}|=|S_{1}|+|S_{2}|-|S_{1}\cap S_{2}|.}$
When ${\displaystyle n=3}$, the inclusion-exclusion principle gives
${\displaystyle |S_{1}\cup S_{2}\cup S_{3}|=|S_{1}|+|S_{2}|+|S_{3}|-|S_{1}\cap S_{2}|-|S_{1}\cap S_{3}|-|S_{2}\cap S_{3}|+|S_{1}\cap S_{2}\cap S_{3}|.}$

Example. Among 140 people, 110 of them speak at least one of English, French and German. Given that

• 90, 30, 42 of them speak English, French, German respectively;
• 23 speak English and French;
• 25 speak English and German;
• 16 speak French and German.

Calculate the number of people that speak English, French, and German.

Solution. Let ${\displaystyle E}$, ${\displaystyle F}$, ${\displaystyle G}$ be the set containing the people speaking English, French and German respectively. Then, by inclusion-exclusion principle,

${\displaystyle |E\cup F\cup G|=|E|+|F|+|G|-|E\cap F|-|F\cap G|-|E\cap G|+|E\cap F\cap G|\implies 110=90+30+42-23-29-16+|E\cap F\cap G|\implies |E\cap F\cap G|=12.}$
Hence, the number of people that speak English, French and German is ${\displaystyle 110-90-30-42+23+25+16=12}$.

Venn diagram

*----------------*
|90-13-12-11=54  | <---- E
|      *---------*--------------*
|      |25-12=13 |42-13-12-4=13 | <--- G
*------*---------*--------------*-----*
|      |   12    |16-12=4       |     |
|      *---------*--------------*     | <--- F
|  23-12=11      |  30-11-12-4=3      |
*----------------*--------------------*
140-110=30


Exercise.

1 Calculate the number of people that speak (a) English only; (b) French only; (c) German only.

 (a) 90; (b) 30; (c) 42 (a) 54; (b) 13; (c) 3 (a) 54; (b) 11; (c) 3 (a) 54; (b) 3; (c) 11 None of the above.

2 Suppose ${\displaystyle k}$ people among the 140 people now learn to speak English. Calculate ${\displaystyle k}$ such that 123 of them speak at least one of English, French and German, and 20 people speak English, French and German now.

 20 21 22 23 None of the above.

3 Continue from previous question. Calculate the number of people who speak English and French now.

 23 31 36 44 None of the above.

### Multiplication counting principle

Theorem. (Multiplication counting principle)

Let ${\displaystyle n}$ be a positive integer. If there are ${\displaystyle m_{1},m_{2},\dotsc ,m_{n}}$ ways to do the task ${\displaystyle 1,2,\dotsc ,n}$ respectively, then there are ${\displaystyle m_{1}\times m_{2}\times \dotsb \times m_{n}}$ ways to do the ${\displaystyle n}$ tasks.

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

"If there are ${\displaystyle m_{1},m_{2},\dotsc ,m_{n}}$ ways to do the task ${\displaystyle 1,2,\dotsc ,n}$ respectively, then there are ${\displaystyle m_{1}\times m_{2}\times \dotsb \times m_{n}}$ ways to do the ${\displaystyle n}$ tasks."

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

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

"If there are ${\displaystyle m_{1},m_{2},\dotsc ,m_{k}}$ ways to do the task ${\displaystyle 1,2,\dotsc ,k}$ respectively, then there are ${\displaystyle m_{1}\times m_{2}\times \dotsb \times m_{k}}$ ways to do the ${\displaystyle k}$ tasks."

is true.

Inductive Step: We want to show that ${\displaystyle P(k+1)}$ is true. So, we now assume that there are ${\displaystyle m_{1},m_{2},\dotsc ,m_{k},{\color {darkgreen}m_{k+1}}}$ ways to do the task ${\displaystyle 1,2,\dotsc ,k,{\color {darkgreen}k+1}}$ respectively. By the inductive hypothesis, there are ${\displaystyle m_{1}\times m_{2}\times \dotsb \times m_{k}}$ ways to do the first ${\displaystyle k}$ tasks (task ${\displaystyle 1,2,\dotsc ,k}$). Now, for each of the ${\displaystyle m_{1}\times m_{2}\times \dotsb m_{k}}$ ways of doing the first ${\displaystyle k}$ tasks, there are ${\displaystyle {\color {darkgreen}m_{k+1}}}$ ways to do the task ${\displaystyle k+1}$. Expressing it using a table, we have

${\displaystyle {\begin{array}{cc}{\text{ways of doing the first }}k{\text{ tasks}}&{\text{number of ways to do task }}k+1\\\hline {\text{way 1}}&m_{k+1}\\{\text{way 2}}&m_{k+1}\\\vdots &\vdots \\{\text{way }}m_{1}\times m_{2}\times \dotsb m_{k}&m_{k+1}\\\end{array}}}$
Hence, the number of ways of doing the ${\displaystyle k+1}$ tasks (the first ${\displaystyle k}$ tasks, and the task ${\displaystyle k+1}$) is
${\displaystyle \underbrace {m_{k+1}+m_{k+1}+\dotsb +m_{k+1}} _{m_{1}\times m_{2}\times \dotsb m_{k}{\text{ times}}}=(m_{1}\times m_{2}\times \dotsb \times m_{k})m_{k+1}=m_{1}\times m_{2}\times \dotsb \times m_{k+1}.}$
So, ${\displaystyle P(k+1)}$ is true.

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

${\displaystyle \Box }$

Remark.

• Sometimes, replacing "ways to do" by "outcomes from" may be more natural, particularly in the case where the tasks have random outcomes where one cannot control which outcome happens (e.g., lucky draw).
• Similarly, replacing "tasks" by "trials" may be more natural sometimes.

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 fixed, 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 ${\displaystyle 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 same outcome under the situation in a problem, so the those ways should only be counted as one outcome in that context. (See the following example.)

Example. (Number of outcomes of a trial is not fixed) Consider a box containing one red ball and one blue ball. Suppose the trial 1 and 2 are drawing a ball from the box first and second time respectively. We further assume that when red ball is drawn, we put it back into the box. Otherwise, we don't. Then, if we draw red ball in trial 1, then there are two outcomes from trial 2. Otherwise, there is only one outcome from trial 2. In this case, the multiplication counting principle does not apply, since the number of outcomes from trial 2 is not fixed (it varies between 1 and 2, depending on the outcome from trial 1).

Using a digram, the situation looks like:

  Trial 1         Trial 2

---- red
/
red  ----*
/           \
*             ---  blue
\
blue  ----*--- red


We can see that we only have 3 ways of doing the two tasks. (Here, the number of ways of doing task 2 is neither 1 nor 2. Indeed, we cannot determine such number since the number is not fixed at all.)

Example. (Two decision paths lead to same outcome)

Suppose we toss two identical and indistinguishable coins at the same time. We also regard the outcome of one coin as the outcome of "trial 1" and the outcome of another coin as the outcome of "trial 2". In this case, we can illustrate the situation using a diagram:

Trial 1              Trial 2
---- H
/
H -------------*
/                 \---- T
/
*
\                   ----- H
\                 /
T -------------*
\
----- T


In this case, having "H in trial 1 and T in trial 2" is the same as "T in trial 1 and H in trial 2", since both mean the same thing in this context:

We get "heads" from one coin, "tails" from another one.

So, there are indeed only three (distinct) outcomes from the two trials:

3. "two tails",

instead of ${\displaystyle 2\times 2=4}$ outcomes, because of the indistinguishable trials, causing two decision paths to lead the same outcome.

Exercise. Suppose you have a drawer that contains 50 identical red socks and 50 identical blue socks, Suppose you draw two socks from the drawer. How many different color combinations of the two socks are possible?

Solution

We have two draws from the drawer. Let us regard the "draw 1" as task 1 and "draw 2" as task 2.

Task 1              Task 2
---- R
/
R -------------*
/                 \---- B
/
*
\                   ----- R
\                 /
B -------------*
\
----- B
R: red sock
B: blue sock


Similarly, the color pattern in "R in task 1 and B in task 2" is essentially the same as that in "B in task 1 and R in task 2", since in both ways, the color combination is "1 Red 1 Blue". In this case, there are similarly three distinct color combinations only:

1. 2 Red
2. 1 Red 1 Blue
3. 2 Blue

Example.

In a country, there are three towns: town A, B and C. The routes between each town is illustrated by the following diagram:

  /*------*\          *------------*
/          \        /             |
A---*\       /B ----*--------------C
\ /*--*  \                  /
*        \                /
*--------------*


Calculate the number of ways to go from town A to town C.

Solution. First, we have 2 routes from town A to town B, 3 routes from town B to town C. So, there are ${\displaystyle 2\times 3=6}$ ways to go from town A to town C.

Exercise. Suppose part of a route is broken in the following way: (xxx indicates broken route)

  /*------*\          *------------*
/          \        /             |
A---*\       /B xxx *--------------C
\ /*--*  \                  /
*        \                /
*--------------*


Calculate the number of ways to go from town A to C now.

Solution

The number of ways is ${\displaystyle 2\times 1=2}$.

Exercise.

A chemist has three unknown chemicals: chemical A, B and C. To test these three chemicals, the chemist decides to conduct all the following experiments:

1. mixing A and B
2. mixing B and C
3. mixing A and C

Suppose the chemical A is known to be more reactive than the other two chemicals, such that

• after mixing two chemicals where chemical A is not involved, there are two possible outcomes: (i) no reaction; (ii) weak reaction;
• after mixing two chemicals where chemical A is involved, there are three possible outcomes: (i) no reaction; (ii) weak reaction; (iii) explosion.

What are the number of possible outcomes from these three experiments?

Solution

The number of possible outcomes for experiment 1,2,3 is 3,2,3 respectively. So, the number of possible outcomes from these three experiments is ${\displaystyle 3\times 2\times 3=18}$.

Example. (Number of elements in a power set) The number of elements in a power set of set ${\displaystyle S}$ with ${\displaystyle n}$ elements is ${\displaystyle 2^{n}}$.

Proof. Consider the ${\displaystyle n}$ elements in ${\displaystyle S}$ one by one. For each of them, we can either include or do not include it in a subset of ${\displaystyle S}$. Then, there are ${\displaystyle n}$ steps involved to construct a subset of ${\displaystyle S}$, and each step has two outcomes. It follows from the multiplication counting principle that the ${\displaystyle n}$ steps have ${\displaystyle \underbrace {2\times 2\times \dotsb \times 2} _{n{\text{ times}}}=2^{n}}$ outcomes. That is, there are ${\displaystyle 2^{n}}$ possible (distinct) subsets of ${\displaystyle S}$. Since power set contains all subsets of ${\displaystyle S}$ by definition, it follows that the power set has ${\displaystyle 2^{n}}$ elements.

${\displaystyle \Box }$

Example. Suppose we throw two (six-faced) dice, with colors red and blue respectively. Show that the number of possible distinct pairs of number facing up is ${\displaystyle 6\cdot 6=36}$.

Proof. Since the dice are distinguishable, we can use multiplication principle of counting. To be more precise, we can let the possible numbers facing up of red dice to be the possible outcomes in "trial 1", and that of blue dice to be the possible outcomes in "trial 2". Since each trial has six outcomes, it follows that the number of outcomes (i.e. possible distinct pairs) is ${\displaystyle 6\cdot 6=36}$.

${\displaystyle \Box }$

Exercise. Suppose the red dice becomes a blue dice, such that the two dices are not distinguishable anymore. Show that the number of possible distinct pairs of number facing up is 21. (Hint: subtract some pairs from the above 36 pairs.)

Proof

Proof. From the 36 outcomes in the example, some pair become the same as another pair after the change (that is, we cannot identify them as two pairs). So, we need to remove one of the repeated pairs from the 36 pairs. Using ${\displaystyle (a,b)}$ to denote number ${\displaystyle a}$ and ${\displaystyle b}$ facing up in original red and blue dice respectively, we have

{\displaystyle {\begin{aligned}&(1,2),{\cancel {(2,1)}},(1,3),{\cancel {(3,1)}},(1,4),{\cancel {(4,1)}},(1,5),{\cancel {(5,1)}},(1,6),{\cancel {(6,1)}},&\leftarrow {\text{5 pairs removed}}\\&(2,3),{\cancel {(3,2)}},(2,4),{\cancel {(4,2)}},(2,5),{\cancel {(5,2)}},(2,6),{\cancel {(6,2)}},&\leftarrow {\text{4 pairs removed}}\\&(3,4),{\cancel {(4,3)}},(3,5),{\cancel {(5,3)}},(3,6),{\cancel {(6,3)}},&\leftarrow {\text{3 pairs removed}}\\&(4,5),{\cancel {(5,4)}},(4,6),{\cancel {(6,4)}},&\leftarrow {\text{2 pairs removed}}\\&(5,6),{\cancel {(6,5)}}.&\leftarrow {\text{1 pair removed}}\end{aligned}}}
In total, there are ${\displaystyle 5+4+3+2+1=15}$ pairs removed, so the desired number is ${\displaystyle 36-15=21}$.

${\displaystyle \Box }$

### Division counting principle

Theorem. (Division counting principle) There are ${\displaystyle {\frac {n}{d}}}$ ways to do a task if it can be done using a procedure that can be carried out in ${\displaystyle n}$ ways, and for every way ${\displaystyle w}$ for doing the task, exactly ${\displaystyle d}$ of the ${\displaystyle n}$ ways in the procedure correspond to the way ${\displaystyle w}$. (${\displaystyle {\frac {n}{d}}}$ is a positive integer.)

Graphically, it looks like

{\displaystyle {\begin{aligned}{\text{Task }}\quad &{\text{ Procedure}}\\\hline {\text{way 1}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\{\text{way 2}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\\vdots \\{\text{way }}{\frac {n}{d}}\leftrightarrow &{\begin{cases}{\text{way 1}}\\{\text{way 2}}\\\quad \vdots \\{\text{way }}d\end{cases}}\\\hline \qquad \qquad &{\text{Total}}:{\frac {n}{d}}\times d=n{\text{ ways for the procedure}}\end{aligned}}}

Example. (Counting cows) Suppose we want to count the number of cows in a field. We first count that there are 1000 legs in total. Since every cow has four legs, the number of cows is given by ${\displaystyle {\frac {1000}{4}}=250}$. (Here, the "task" may be interpreted as choosing a cow, and the "procedure" may be interpreted as choosing a leg. Then, 4 ways of choosing a leg correspond to 1 way of choosing a cow.)

Example. (Arranging seats in a circular table)

Count the number of ways to seat four people around a circular table, where two seatings are considered the same if every person has the same left neighbour and same right neighbour. For example, the following two seatings are considered the same:

   1               4
4     2         3     1
3               2


But the following two seatings are not considered the same:

   1               4
4     2         1     3
3               2


since, for the person 1, for the left seating, his left and right neighbours are 2 and 4 respectively, while for the right seating, his left and right neighbours are 4 and 2 respectively.

Solution.

Procedure: First, we count the number of ways to seat four people around a circular table, without considering whether the seatings are considered the same or not. We regard the arrangment of seating as a four-step process:

1. assign a seat to first person (there are 4 vacant seats, so 4 ways)
2. assign a seat to second person (there are 3 vacant seats, so 3 ways)
3. assign a seat to third person (there are 2 vacant seats, so 2 ways)
4. assign a seat to fourth person (there is 1 vacant seat, so 1 way)

The number of ways is given by

${\displaystyle \underbrace {4} _{4{\text{ vacant seats}}}\times \underbrace {3} _{3{\text{ vacant seats}}}\times \underbrace {2} _{2{\text{ vacant seats}}}\times \underbrace {1} _{1{\text{ vacant seat}}}=24.}$
Task: Given an arrangement in the procedure, we can rotate it clockwise by 90, 180, or 270 degrees (rotating 360 degrees is the same as not rotating), to generate three more different arrangements in the procedure. However, these four arrangements are considered the same in the task. This means that these four arrangements in the procedure correspond to one arrangement in the task. It then follows by division counting principle that the desired number of ways is
${\displaystyle {\frac {24}{4}}=6.}$

Exercise. Count the number of ways if there are five, instead of four people.

Solution

Procedure: First, the number of ways to seat five people around a circular table (without considering whether the seatings are considered the same or not) is

${\displaystyle \underbrace {5} _{5{\text{ vacant seats}}}\times \underbrace {4} _{4{\text{ vacant seats}}}\times \underbrace {3} _{3{\text{ vacant seats}}}\times \underbrace {2} _{2{\text{ vacant seats}}}\times \underbrace {1} _{1{\text{ vacant seat}}}=120.}$
similarly.

Task: Given an arrangement in the procedure, we can rotate it clockwise by 72, 144, 216, or 288 degrees, to generate four more different arrangements in the procedure. But these five arrangements are considered the same in the task. So the five arrangements in the procedure correspond to one arrangement in the task. Hence, the desired number of ways is

${\displaystyle {\frac {120}{5}}=24.}$

Example.

Suppose 10 people decide to play basketball together. So, they need to divide among themselves into two indistinguishable teams, consisting 5 people each. In each team, there are five positions:

1. Point guard
2. Shooting guard
3. Small forward
4. Power forward
5. Center

How many ways for forming the two teams are there?

Solution.

Procedure: First we suppose the two teams are distinguishable, say one is blue team and another is red team. In this case, we can consider the teams forming process as a 10-step process:

• Step 1: Choose one from the 10 people to be blue team point guard. (10 ways)
• Step 2: Choose one from the 9 people to be blue team shooting guard. (9 ways)
• Step 3: Choose one from the 8 people to be blue team small forward. (8 ways)
• ...
• Step 10: Choose one from the 1 person to be red team center. (1 way)

So, there are altogether ${\displaystyle 10\times 9\times 8\times \dotsb \times 1=3628800}$ ways for forming the two distinguishable teams.

Task: Given a way for forming two teams in the procedure, we can swap the team members in blue and red teams to generate one more different way for forming two teams in the procedure. That is, by assigning all team members in blue team originally to be in red team, and all team members in red team originally to be in blue team, we can create another way for forming two teams in the procedure. But these two ways correspond to one way in the task (in each of these two ways, the two indistinguishable teams contain the same members, and so these two ways are considered the same). It follows by the division counting principle that the number of ways is

${\displaystyle {\frac {3628800}{2}}=1814400.}$

Exercise. Suppose there are no positions in each team. That is, the five people in a team are all considered as members of the team only, with no specific role or position. Show that there are only 126 ways for forming the two teams. (Hint: Determine the number ways to arrange the positions among the 5 people in a team originally. Then, apply the division counting principle (divide 1814400 by something).)

Proof

Proof. Procedure: Suppose there are still positions in each team. Then, by the above example, there are 1814400 ways for forming the two teams.

Task: Given a way in the procedure, we can arrange the positions among the 5 people in each of the two teams. Now, let us consider how many ways of arrangements are there. For each of the teams, it is a five-step process:

1. Choose one from the 5 team members to be point guard (5 ways)
2. Choose one from the 4 team members to be shooting guard (4 ways)
3. Choose one from the 3 team members to be small forward (3 ways)
4. Choose one from the 2 team members to be power forward (2 ways)
5. Choose one from the 1 team member to be center (1 way)

So, the number of arrangements for each of the teams is ${\displaystyle 5\times 4\times 3\times 2\times 1=120}$. Then, arranging the two teams is a two-step process:

1. Arrange one of the teams (120 ways)
2. Arrange another team (120 ways)

So, there are in total ${\displaystyle 120\times 120=14400}$ ways for the arrangement, which includes the given way.

Hence, this means given a way in the procedure, we can generate ${\displaystyle 14400-1=14399}$ more ways. But these 14400 ways are considered the same without any positions (both teams consist of the same members). It follows by the division counting principle that the number of ways is

${\displaystyle {\frac {1814400}{14400}}=126.}$

${\displaystyle \Box }$

We should be aware that the division counting principle does not apply if different ways of doing task correspond to different number of ways in the procedure. Consider the following examples:

Example. (Chickens and rabbits in the same cage)

Suppose there are some chickens and rabbits in the same cage, but we do not know how many chickens and rabbits are there. Suppose we know that there are 120 legs in the cage. Then, students A and B make the following arguments for counting the number of animals in the cage:

• Student A: Since every rabbit has four feet, there are ${\displaystyle {\frac {120}{4}}=30}$ animals in the cage.
• Student B: Since every chicken has two feet, there are ${\displaystyle {\frac {120}{2}}=60}$ animals in the cage.

Explain why both students are wrong.

Solution. Student A is wrong since not every animal in the cage has four feet (a chicken has two feet). Similarly, student B is wrong since not every animal in the cage has two feet (a rabbit has four feet). We can see that the division counting principle does not apply here.

Example. Suppose we toss a coin twice. Without any assumption, the distinct outcomes are HH, HT, TH, and TT. Suppose we regard the tosses as unordered, that is, the order of the outcomes is not important. In this case, the outcomes HT and TH are regarded as the same, say both are regarded as "1 head 1 tail", or in short "1H1T". But the outcomes HH and TT are still regarded as different.

With such consideration the outcomes become "2H", "1H1T", and "2T". But we see that "1H1T" corresponds to "HT" and "TH" (two ways in the "procedure"), while "2H" corresponds to "HH" (one way in the "procedure"). So, the division counting principle does not apply here, and the number of outcomes in this case is not given by ${\displaystyle {\frac {4}{2}}=2}$.

Exercise. Suppose we toss a coin twice, and we only concern with whether both tosses give the same outcome. Can we use the division counting principle here? Why?

Solution

In this case, both "HH" and "TT" correspond to "same outcome", while "HT" and "TH" correspond to "different outcomes". Thus, for every outcome for the "task", there are two outcomes in the "procedure" corresponding to it, and hence the desired number of outcomes can be obtained by the division counting principle:

${\displaystyle {\frac {4}{2}}=2.}$

## 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 ${\displaystyle r}$ balls into ${\displaystyle 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 think 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 ${\displaystyle r}$ balls into ${\displaystyle n}$ cells" (for some ${\displaystyle n}$ and ${\displaystyle 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 not 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 not placing "numbers" into "password positions". If this is the case, then some password position contains more than one 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, in four types, classified by whether the selection is ordered, and whether the selection is with replacement. 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:

Definition. (Factorial) Let ${\displaystyle n}$ be a nonnegative integer. The factorial of ${\displaystyle n}$, denoted by ${\displaystyle n!}$, is

${\displaystyle n!={\begin{cases}1,&n=0;\\n(n-1)(n-2)\dotsb (1),&n\geq 1.\end{cases}}}$

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

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

• The capacity is one, since without replacement, 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.

Theorem. The number of ways for placing ${\displaystyle r}$ distinguishable balls into ${\displaystyle n}$ distinguishable cells with capacity one is ${\displaystyle _{n}P_{r}={\frac {n!}{(n-r)!}}}$.

Proof. We consider the placement as a ${\displaystyle r}$-step process:

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

Thus, by multiplication principle of counting, the desired number of ways is

${\displaystyle \underbrace {n} _{\text{ball 1}}\times \underbrace {(n-1)} _{\text{ball 2}}\times \dotsb \times \underbrace {(n-r+1)} _{{\text{ball }}r}={\frac {n\times (n-1)\times \dotsb \times (n-r+1)\times {\color {darkgreen}(n-r)\times \cdots \times 1}}{\color {darkgreen}(n-r)\times \cdots \times 1}}={\frac {n!}{(n-r)!}}.}$

${\displaystyle \Box }$

Example. In a row of a bookshelf, there are 5 places for placing books. Amy owns 11 books and wants to fill the row (order matters). How many possible ways are there?

Solution. We can regard the 5 book places as 5 balls, the 11 books owned as 11 cells, with capacity one (since every book can be placed at most once). So, the number of ways is

${\displaystyle _{11}P_{5}=11\times 10\times 9\times 8\times 7=55440.}$

Example.

In a certain place, there are 10 flag poles, placed in different positions. Suppose we have 7 distinct flags to be put at the flag poles, and every flag pole can only contain at most one flag. How many possible arrangements are there?

Solution. We can regard the 10 flag poles as 10 distinguishable cells (since the poles are at different positions), with capacity one (flag pole can only contain at most one flag), and 7 distinct flags as 7 distinguishable balls. So, the number of arrangements is

${\displaystyle _{10}P_{7}=10\times 9\times 8\times 7\times 6\times 5\times 4=604800.}$

Exercise. Suppose there are 7 flag poles and 10 distinct flags instead. Count the number of possible arrangement.

Solution

We can regard the 7 flag poles as 7 distinguishable balls, and 10 distinct flags as 10 distinguishable cells with capacity one (since every flag can be put at at most one flag pole). After having such interpretation, the situation is the same as above. Hence, the number of arrangements is the same (604800).

Example.

How many ways are there to draw 5 cards from a poker deck (with 52 cards), where the order of the cards drawn is important?

Solution. We can regard the 5 ordered draws as 5 distinguishable balls, and the 52 cards in a poker deck as 52 distinguishable cells. Then, the number of ways is

${\displaystyle _{52}P_{5}={\frac {52!}{47!}}=311875200.}$

Exercise. What is the number of ways if the order of the cards drawn is unimportant? (Hint: consider the division counting principle. To determine the number of ordered draws correspond to one unordered draw, consider the number of ways to order (or permutate) 5 draws.)

Solution

To order 5 draws, we can regard the 5 draws as 5 distinguishable balls, and 5 ordered positions as 5 distinguishable cells (with capacity one). Then, the number of ways for such ordering is ${\displaystyle _{5}P_{5}={\frac {5!}{0!}}=5!=120}$.

This in turn means that 120 ordered draws correspond to one unordered draw. That is, there are 120 ordered draws, where the 5 draws always include a group of 5 cards throughout. Hence, by the division counting principle, the number of ways is given by

${\displaystyle {\frac {311875200}{120}}=2598960.}$

Example. (Competition) There are 16 candidates for a competition.

(a) How many ways are there to award winner, 1st and 2nd runners-up?

(b) Amy and Bob are among the 16 candidates. Suppose Amy is awarded 1st runner-up, while Bob does not receive any award. How many ways are there to award winner, 1st and 2nd runners-up?

(a) The number of ways is

${\displaystyle _{16}P_{3}=\underbrace {16} _{\text{winner}}\times \underbrace {15} _{\text{1st runner-up}}\times \underbrace {14} _{\text{2nd runner-up}}=3360.}$

(b) The number is

${\displaystyle _{14}P_{2}\times 1=\underbrace {14} _{\text{winner}}\times \underbrace {1} _{\text{1st runner-up: Amy}}\times \underbrace {13} _{\text{2nd runner-up}}=182.}$

Exercise.

1 Suppose Chris is also among the 16 candidates. Given that Amy, Bob and Chris receive an award from the competition, calculate the number of ways to award winner, 1st and 2nd-runners up.

 1 3 6 32 96

2 Continue from previous question. Given that Amy, Bob and Chris do not receive any award from the competition, calculate the number of ways to award winner, 1st and 2nd-runners up.

 1716 2496 3354 3357 3359

Example. Show that the number of ways of ordering (or permutating) ${\displaystyle n}$ distinguishable objects is ${\displaystyle n!}$.

Proof. Ordering ${\displaystyle n}$ distinguishable objects is the same as putting the ${\displaystyle n}$ distinguishable objects (balls) into ${\displaystyle n}$ distinguishable (and ordered) "positions" (cells). (For example, when ball 1,2,3 are put into position 2,3,1 respectively, this means ordering the three balls in this order: 3,1,2.) So, the number of ways is ${\displaystyle _{n}P_{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!}$.

${\displaystyle \Box }$

Example. How many ways are there to permutate the string "APPLE"? (Hint: you may need to use the division counting principle.)

Solution. First, we permutate the string as if the two "P"s are distinguishable. Then, there are ${\displaystyle 5!}$ ways for the "procedure". But the two "P"s are actually indistinguishable, so some ways in the ${\displaystyle 5!}$ ways are actually considered the same. To be more precise, when we swap the position of the two "P"s for a given string, the resulting string should be the same as before in the "task", but we regard them as two different strings if we regard the two "P"s as distinguishable in the "procedure". So, we divide the number of ways by 2 to get the number of ways to perform the "task":

${\displaystyle {\frac {5!}{2}}=60,}$
which is what we want.

Exercise. How many ways are there to permutate the string "PEPPER"?

Solution

We use similar method as in above example. First, we premutate the string as if the three "P"s, two "E"s are distinguishable. So, there are ${\displaystyle 6!}$ ways for the "procedure".

Now, for the "task", given a string, ordering the 3 "P"s do not change the string. Also, ordering the 2 "E"s do not change the string as well. But, such ordering changes the string in the procedure. By the multiplication counting principle and the result about ordering, there are ${\displaystyle 3!\times 2!=12}$ such orderings, and hence 12 ways in the procedure corresponding to a given string. It follows that the number of ways is

${\displaystyle {\frac {6!}{12}}=60.}$

The situation in the example above can actually be interpreted as a special case of partition.

### Partition

For permutating the string "APPLE", we can regard the situation as partitioning 5 (distinguishable and ordered) letter positions 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) letter positions 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 must contain. Generally, "partitioning ${\displaystyle n}$ distinguishable objects into ${\displaystyle k}$ groups, where group 1,2,...,${\displaystyle k}$ must contain ${\displaystyle n_{1},n_{2},\dotsc ,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 ${\displaystyle n}$ distinguishable balls into cell 1,2,...,${\displaystyle k}$, where cell 1,2,...,${\displaystyle k}$ must contain ${\displaystyle n_{1},n_{2},\dotsc ,n_{k}}$ balls respectively".

Theorem. The number of ways for placing ${\displaystyle n}$ distinguishable balls into cell 1,2,...,${\displaystyle k}$, where cell 1,2,...,${\displaystyle k}$ must contain ${\displaystyle n_{1},n_{2},\dotsc ,n_{k}}$ balls respectively, is ${\displaystyle {\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}={\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}}$.

Proof. First, we consider a procedure where we regard cell 1,2,...,${\displaystyle k}$ contains ${\displaystyle n_{1},n_{2},\dotsc ,n_{k}}$ ordered positions for placing one ball each (e.g., there are ${\displaystyle n_{1},n_{2},\dotsc ,n_{k}}$ "subcells" in cell 1,2,...,${\displaystyle k}$). In this case, we can just regard the placement as a permutation of the ${\displaystyle n}$ distinguishable balls, since the ${\displaystyle k}$ cells altogether contain ${\displaystyle n}$ "ordered positions" ("subcells"). After having such consideration, the number of ways of placement is ${\displaystyle 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 ${\displaystyle n_{1}!,n_{2}!,\dotsc ,n_{k}!}$ ways to permutate the distinguishable balls in the subcells of cell 1,2,...,${\displaystyle k}$ respectively, so there are altogether ${\displaystyle n_{1}!n_{2}!\dotsc n_{k}!}$ ways in the procedure that correspond to one way in the "task". Hence, by the division counting principle, there are ${\displaystyle {\frac {n!}{n_{1}!n_{2}!\dotsc n_{k}!}}}$ ways for the partition.

${\displaystyle \Box }$

Remark.

• ${\displaystyle {\binom {n}{n_{1},n_{2},\dotsc ,n_{k}}}}$ is called the multinomial coefficient.

Exercise.

Calculate the number of ways to permutate the string "EXERCISE".

 28 56 3360 6720 20160

Example. Show that the number of ways to order the number 171237615 such that the number formed is an odd number is 23520.

Proof. We consider the number of arrangements for the opposite case, i.e. the number formed is an even number, since this number is easier to be calculated. We can notice that in order for the number formed to be even, the number must end with the number 2 or the number 6. Hence, we consider the number of ways of ordering in each of these two cases.

Case 1: end with 2. Then, we can only order the remaining 8 numbers, in the first eight number positions. The number of ordering is ${\displaystyle {\frac {8!}{3!2!}}=3360}$ (There are three "1"s and two "7"s. All other numbers occur exactly once.)

Case 2: end with 6. Then, we can only order the remaining 8 numbers, in the first eight number positions. The number of ordering is ${\displaystyle {\frac {8!}{3!2!}}=3360}$ (There are three "1"s and two "7"s. All other numbers occur exactly once.)

We can also see that a number cannot end with the number 2 and 6 simultaneously. Hence there is no common ordering in these two cases. It follows that the number of ordering such that the number formed is even is ${\displaystyle 3360+3360=6720}$.

Now, we consider the number of ordering without any restrictions. The number is given by ${\displaystyle {\frac {9!}{3!2!}}=30240}$. Since the number formed is either odd or even, we can subtract the number of ordering such that the number formed is even, from the number of ordering without any restrictions, to get the desired number. Hence, the desired number is ${\displaystyle 30240-6720=23520}$.

${\displaystyle \Box }$

Exercise. In the following, the poker deck has 52 cards, and every player gets the same number of cards (i.e., 13 cards). Also suppose the four players are called north, east, south, west players, seated at the north, east, south, west positions of a desk respectively.

(a) Show that the number of ways of distributing a poker deck to 4 players is approximately ${\displaystyle 5.364\times 10^{28}}$.

(b) Show that the number of ways of distributing a poker deck to 4 players such that every player has exactly one ace, is approximately ${\displaystyle 5.659\times 10^{27}}$.

(c) Show that the number of ways of distributing a poker deck to 4 players, such that one player gets all four ace, is approximately ${\displaystyle 5.667\times 10^{26}}$.

(d) Show that the number of ways of distributing a poker deck to 4 players, such that the north player gets all 13 cards of a kind, is approximately ${\displaystyle 3.379\times 10^{17}}$.

Proof

Generally, we can regard the 52 cards as 52 distinguishable balls, and the four players as four distinguishable cells. But the requirements on the number of balls for the cells differ for different parts.

(a)

Proof. Distributing the poker deck in such way can be regarded as partitioning 52 cards into four (distinguishable) groups, containing exactly 13 cards each. Hence, the number of ways is ${\displaystyle {\frac {52!}{(13!)^{4}}}\approx 5.364\times 10^{28}}$.

${\displaystyle \Box }$

(b)

Proof. We first consider the 48 cards in the deck without ace. There are ${\displaystyle {\frac {48!}{(12!)^{4}}}}$ ways to partition the 48 cards into four groups of 12 cards. Now, we consider the distribution of four aces. Since every player has exactly one ace, distributing the four aces is the same as permutating the four aces. Hence, the number is ${\displaystyle 4!}$. It follows that the number is ${\displaystyle 4!\times {\frac {48!}{(12!)^{4}}}\approx 5.659\times 10^{27}}$.

${\displaystyle \Box }$

(c)

Proof. We first consider the 48 cards in the deck without ace. There are ${\displaystyle {\frac {48!}{(13!)^{3}\times 9!}}}$ ways to partition the 48 cards into four groups, such that three of them contain 13 cards each (players who do not get all four aces), and one contains 9 cards (the player who get all four aces). Since one player gets all four ace, and that player is not specified, there are four possibilities of distributing the four aces, depending on which of the four players get them. It follows that the number is ${\displaystyle 4\times {\frac {48!}{(13!)^{3}\times 9!}}\approx 5.667\times 10^{26}}$.

${\displaystyle \Box }$

(d)

Proof. We first consider the 39 cards in the deck, with a certain kind of cards removed. There are ${\displaystyle {\frac {39!}{(13!)^{3}}}}$ to partition the 39 cards into three groups of 13 cards, for the east, south, and west players. Since the north player gets all 13 cards of a kind, and the kind is not specified. There are four possibilities for the kind. Hence, the number is ${\displaystyle 4\times {\frac {39!}{(13!)^{3}}}\approx 3.379\times 10^{17}}$.

${\displaystyle \Box }$

Example. (Sequence of dice outcomes) A six-faced dice is rolled nine times. Show that the number of distinct sequences of outcomes in which 1,3 and 5 each comes up three times is 1680.

Proof. Consider this situation as the partition of the nine (ordered) outcomes from the die to three groups, which represents 1,3 and 5 comes up in that outcome respectively. The three groups contains 3 outcomes each, since each of the numbers 1,3,5 comes up three times. It follows that the number of ways to partition the outcomes is ${\displaystyle {\frac {9!}{3!3!3!}}=1680}$.

For each partition of outcomes into different groups, we obtain a unique sequence of outcomes. (E.g. if we put 1st, 2nd and 4th outcomes to the group representing 1 coming up, 5th, 7th and 9th outcomes to the group representing 3 coming up, and the remaining outcomes are put to the group representing 5 coming up, then the sequence obtained is: (1st outcome) 1,1,5,1,3,5,3,5,3 (9th outcome) in this order.) So, the result follows.

${\displaystyle \Box }$

Exercise.

1 Calculate the number of distinct sequences in which 2,4 and 6 each comes up three times instead.

 840 1680 3360 6720 361200

2 Suppose we throw the die 12 times instead. Calculate the number of distinct sequences in which each number comes up two times.

 2520 5040 113400 369600 7484400

Example. (Walking path) Consider the following diagram.

${\displaystyle {\begin{array}{c|c|c|c|c}A&&&&B\\\hline &&E&&\\\hline C&&&&D\\\end{array}}}$
Suppose we are initially located at ${\displaystyle A}$, and that we can only walk either one cell rightward or one cell downward for each step. Show that the number of distinct sequence of steps such that we can walk from ${\displaystyle A}$ to ${\displaystyle D}$ is 15.

Proof. First, observe that we need exactly 6 steps to walk from ${\displaystyle A}$ to ${\displaystyle D}$, consisting 4 steps of walking rightward (${\displaystyle \rightarrow }$) and 2 steps of walking downward (${\displaystyle \downarrow }$). (This can be observed from the diagram, and the assumption that we can only walk one cell rightward or one cell downward is important)

Thus, the number of distinct sequence of steps is equivalent to the number of distinct sequence of 4 ${\displaystyle \rightarrow }$'s and 2 ${\displaystyle \downarrow }$'s.

Then consider this as a partition problem: partition the 6 step positions into 2 groups, one of them represents ${\displaystyle \rightarrow }$ (and contains 4 step positions), another represents ${\displaystyle \downarrow }$ (and contains 2 step positions).

Hence, the desired number is

${\displaystyle \underbrace {6!} _{\text{steps}}/(\underbrace {2!} _{\downarrow }\underbrace {4!} _{\rightarrow })=15.}$

${\displaystyle \Box }$

Exercise.

1 Calculate the number of distinct sequence again if we can also walk one cell leftward for each step.

 15 35 90 105 None of the above

2 Calculate the number of distinct sequence if we also need to walk through ${\displaystyle E}$ in the walking process from ${\displaystyle A}$ to ${\displaystyle D}$ (Hint: consider this as walking from ${\displaystyle A}$ to ${\displaystyle E}$, then from ${\displaystyle E}$ to ${\displaystyle D}$).

 9 10 11 12 13

3 Calculate the number of distinct sequence if we cannot walk through ${\displaystyle C}$ in the walking process.

 10 11 12 13 14

4 Suppose Amy and Bob is initially located at ${\displaystyle A}$ and ${\displaystyle B}$ respectively. Calculate the number of distinct sequence of steps for Amy such that Amy and Bob meet at ${\displaystyle E}$, given that Amy can only walk 1 cell rightward or 1 cell downward for each step, while Bob can only walk 1 cell leftward or 1 cell downward for each step.

 3 6 9 12 15

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 ${\displaystyle r}$ distinguishable balls into ${\displaystyle n}$ distinguishable cells with capacity one. Now, we will consider the case where the ${\displaystyle r}$ balls are indistinguishable. (One may conceive the balls to be identical (say same color and size), and hence indistinguishalble.) Similarly, such placement is equivalent to selection without replacement (the ${\displaystyle r}$ balls represent the choices, and every cell can still contain at most one ball). However, in this case, the ${\displaystyle r}$ balls (choices) are indistinguishable. So, we only know that which ${\displaystyle r}$ of the ${\displaystyle n}$ cells contain one ball (are selected), but do not know in what order 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 unordered. Such selection process is quite common since we are often more interested in knowing what are selected, and are not quite interested in in what order the things are selected.

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

• For the cells with one ball (${\displaystyle r}$ of them), they are put into the group "selected" (they are selected to place one ball).
• For the cells with zero ball (${\displaystyle 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 ${\displaystyle n}$ distinguishable cells into two groups with ${\displaystyle r}$ distinguishable cells and ${\displaystyle n-r}$ distinguishable cells respectively. With such consideration, the following result is transparent:

Theorem. The number of ways for placing ${\displaystyle r}$ indistinguishable balls into ${\displaystyle n}$ distinguishable cells with capacity one is ${\displaystyle {\binom {n}{r}}={\frac {n!}{r!(n-r)!}}}$.

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 ${\displaystyle {\frac {n!}{(n-r)!}}}$ ways for placing ${\displaystyle r}$ distinguishable balls into ${\displaystyle 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 ${\displaystyle r!}$ placements (obtained by permutating the ${\displaystyle r}$ distinguishable balls) where the balls are distinguishable. It follows that the desired number of ways is

${\displaystyle {\frac {n!}{(n-r)!}}{\bigg /}r!={\frac {n!}{r!(n-r)!}}.}$

${\displaystyle \Box }$

Remark.

• ${\displaystyle {\binom {n}{r}}}$ is called the binomial coefficient. It can also be denoted by ${\displaystyle _{n}C_{r}}$.
• ${\displaystyle {\binom {n}{r}}}$ is read as "n c r"

Example. Consider a group of 10 people.

(a) How many ways are there to select 4 people to be committees from a group of 10 people?

(b) Suppose the 10 people consist of 6 men and 4 women, and the committees should contain 2 men and 2 women. What is the number of ways for now?

(c) In addition to the requirement that the committees should contain 2 men and 2 women, there are roles in the 4 committees: 1 leader and 3 members. What is the number of ways for now?

Solution.

(a) The order for the selection of committees is not important. So, we can regard the 4 committee positions as indistinguishable balls, to be placed into 10 distinguishable cells (10 people). Hence, the number of ways is ${\displaystyle {\binom {10}{4}}=210}$.

(b) In this case, to form the committees, we require two steps:

1. select 2 to be committees from the 6 men (${\displaystyle {\binom {6}{2}}}$ ways)
2. select 2 to be committees from the 4 women (${\displaystyle {\binom {4}{2}}}$ ways)

By the multiplication counting principle, the number of ways is ${\displaystyle {\binom {6}{2}}\times {\binom {4}{2}}=90}$.

(c) We consider two different cases:

Case 1: Leader is a man. Then, the 3 members should be one man and two women. In this case, to form the committees, we need three steps:

1. select 1 to be leader from 6 men (6 ways)
2. select 1 to be member from 5 men (5 ways) (the leader cannot be member concurrently)
3. select 2 to be members from 4 women (${\displaystyle {\binom {4}{2}}}$ ways)

By multiplication counting principle, there are ${\displaystyle 6\times 5\times {\binom {4}{2}}=180}$ ways.

Case 2: Leader is a woman. Then, the 3 members should be one woman and two men. We similar need three steps to form the committees:

1. select 1 to be leader from 4 women (4 ways)
2. select 1 to be member from 3 women (3 ways)
3. select 2 to be members from 6 men (${\displaystyle {\binom {6}{2}}}$ ways)

Then, by multiplication counting principle, there are ${\displaystyle 4\times 3\times {\binom {6}{2}}=180}$ ways.

We can observe that there are no common ways in case 1 and case 2, since the leader is either a man or woman. It then follows that the desired number of ways is ${\displaystyle 180+180=360}$.

Exercise. Continue from (c). Suppose Amy is one of the 4 women and Bob is one of the 6 men. Further suppose that if the leader is a man, then Amy must be selected to be a member, and if the leader is a woman, then Bob must be selected to be a member. Show that the number of ways is 150.

Solution

We consider two different cases:

Case 1: Leader is a man. Then, the 3 members should be one man and two women. In this case, to form the committees, we need four steps:

1. select 1 to be leader from 6 men (6 ways)
2. select 1 to be member from 5 men (5 ways)
3. select Amy to be member (1 way)
4. select 1 to be member from 3 women (3 ways)

By multiplication counting principle, there are ${\displaystyle 6\times 5\times 1\times 3=90}$ ways.

Case 2: Leader is a woman. Then, the 3 members should be one woman and two men. We similar need four steps to form the committees:

1. select 1 to be leader from 4 women (4 ways)
2. select 1 to be member from 3 women (3 ways)
3. select Bob to be member (1 way)
4. select 1 to be member from 5 men (5 ways)

Then, by multiplication counting principle, there are ${\displaystyle 4\times 3\times 1\times 5=60}$ ways.

We can observe that there are no common ways in case 1 and case 2, since the leader is either a man or woman. It then follows that the desired number of ways is ${\displaystyle 90+60=150}$.

Example.

Consider the set ${\displaystyle \{1,2,3\}}$. How many ways are there to choose (a) zero element; (b) one element; (c) two elements; (d) three elements from the three elements in the set? Hence, list the subsets with 0,1,2,3 elements respectively, and show that there are altogether ${\displaystyle 2^{3}=8}$ subsets.

Solution. First, choosing elements is unordered, since the order for selecting the elements does not affect the final result of the selection.

(a) ${\displaystyle {\binom {3}{0}}=1}$.

(b) ${\displaystyle {\binom {3}{1}}=3}$.

(c) ${\displaystyle {\binom {3}{2}}=3}$.

(d) ${\displaystyle {\binom {3}{3}}=1}$.

List of subsets:

• ${\displaystyle {\binom {3}{0}}=1}$ set has 0 element. It is the empty set: ${\displaystyle \varnothing }$.
• ${\displaystyle {\binom {3}{1}}=3}$ sets have 1 element. They are ${\displaystyle \{1\}}$,${\displaystyle \{2\}}$,and ${\displaystyle \{3\}}$.
• ${\displaystyle {\binom {3}{2}}=3}$ sets have 2 elements. They are ${\displaystyle \{2,3\}}$,${\displaystyle \{1,3\}}$,and ${\displaystyle \{1,2\}}$.
• ${\displaystyle {\binom {3}{3}}=1}$ set has 3 elements. It is the set itself: ${\displaystyle \{1,2,3\}}$.

There are altogether ${\displaystyle 1+3+3=1=8}$ subsets.

Example. (Competition) There are 16 candidates for a competition, and there are exactly 3 places for the final. The number of ways to enter the final is ${\displaystyle {\binom {16}{3}}={\frac {16\times 15\times 14}{3\times 2\times 1}}=560.}$

Exercise.

1 Amy, Bob and Chris are among the ${\displaystyle 16}$ candidates. Calculate the number of ways to select them to enter the final.

 1 3 6 32 96

2 Continue from the previous question. Calculate the number of ways to select candidates other than Amy, Bob and Chris to enter the final.

 220 286 554 557 559

Example. We have 10 identical light bulbs where three of them are defective, and the other seven light bulbs operate normally. We want to place the 10 light bulbs in a row for lighting. To ensure an even lighting along the row, it is required that no two defective light bulbs are placed next to each other. How many ways are there to arrange the 10 light bulbs?

Solution. To ensure that no two defective light bulbs are placed next to each other, consider the following diagram:

        * * * * * * *
^ ^ ^ ^ ^ ^ ^ ^
* : normally operating bulb
^ : place for at most one defective light bulb


For every defective light bulb, we need to place it into one of the gaps between light bulbs operating normally. Also, to ensure no two defective light bulbs are placed next to each other, every gap can only contain at most one defective light bulb.

Since the defective light bulbs are identical, and hence indistinguishable (among the defective one). So, the situation is the same as placing 3 indistinguishable balls into 8 distinguishable cells (the 8 places indicated by "^"). It follows that the number is

${\displaystyle {\binom {8}{3}}=56.}$

Example. (Mega Millions) Consider the Mega Millions game. In the game, a player must select five numbers from 1 to 56 in the upper white play area of the play board (corresponding to the white balls), and one Mega Ball number from 1 to 46 in the lower yellow play area of the play board (corresponding to the gold Mega ball). Afterward, five of the white balls numbered from 1-56 are drawn and one of the gold Mega balls numbered from 1-46 is drawn, and the numbers of those ball decide the outcome of the lottery. In particular, the player wins the jackpot if the numbers of the five white balls drawn and the number of the gold Mega ball drawn match exactly with the player's selection.

How many different outcomes for the lottery are there?

Solution. We consider the decision of outcomes as a two-step process:

1. (five white balls) Regard the five draws as five indistinguishable balls (the exact number of each draw is not important. We are only interested in what five numbers are there for the five draws), and the number 1-56 as 56 distinguishable cells (with capacity one, since a white ball cannot be drawn multiple times). Then, the number of ways to draw the five white balls is ${\displaystyle {\binom {56}{5}}=3819816}$.
2. (one gold Mega ball) There are 46 ways to draw one from the 46 gold Mega balls.

Hence, the number of outcomes is ${\displaystyle 3819816\times 46=175711536}$.

Example. (Proving an identity combinatorially) Let ${\displaystyle n}$ and ${\displaystyle r}$ be nonnegative integers such that ${\displaystyle n\geq r}$. Prove that

${\displaystyle {\binom {n}{r}}={\binom {n-1}{r-1}}+{\binom {n-1}{r}}}$

(a) combinatorially;

(b) analytically.

To prove something combinatorially, here we mean considering a particular situation, and counting the number of ways/outcomes/etc. for that situation using two methods, and thereby resulting in two expressions for calculating the same number. Then, we can equate the two expressions. Such proof is also known as proof by double counting since we count the same number twice.

(a)

Proof. Consider the situation where ${\displaystyle r}$ indistinguishable balls are placed into ${\displaystyle n}$ distinguishable cells with capacity one. By the previous theorem, the number of ways is ${\displaystyle {\binom {n}{r}}}$.

So, we have the first method to count the number of ways, corresponding to the LHS of the equation. Now, we use another method to count the number of ways. First, we focus on the cell 1, and split the situation into two cases:

Case 1: cell 1 contains one ball. Then, there are ${\displaystyle r-1}$ balls remaining, and ${\displaystyle n-1}$ cells remaining. So, the number of ways of placing the ${\displaystyle r-1}$ remaining balls into the ${\displaystyle n-1}$ remaining cells is ${\displaystyle {\binom {n-1}{r-1}}}$. Since there is only one way for cell to contain one ball, it follows by the multiplication counting principle that the number of ways is ${\displaystyle {\binom {n-1}{r-1}}}$.

Case 2: cell 1 contains zero ball. Then, there are ${\displaystyle r}$ balls remaining, and ${\displaystyle n-1}$ cells remaining. So, the number of ways is similarly ${\displaystyle {\binom {n-1}{r}}}$.

Since cell 1 either contain one ball or zero ball, there are no common ways in cases 1 and 2. Hence, the number of ways for the placement is

${\displaystyle {\binom {n-1}{r-1}}+{\binom {n-1}{r}},}$
corresponding to the expressions in RHS.

${\displaystyle \Box }$

(b)

Proof. Consider the RHS. We have

{\displaystyle {\begin{aligned}{\binom {n-1}{r-1}}+{\binom {n-1}{r}}&={\frac {(n-1)!}{(r-1)!(n-1-r+1)!}}+{\frac {(n-1)!}{r!(n-1-r)!}}\\&={\frac {(n-1)!}{(r-1)!(n-r)!}}+{\frac {(n-1)!}{r!(n-r-1)!}}\\&={\frac {(n-1)!}{{\color {blue}(r-1)!}(n-r){\color {blue}(n-r-1)!}}}+{\frac {(n-1)!}{r{\color {blue}(r-1)!(n-r-1)!}}}&{\big (}(n-r)!=(n-r)(n-r-1)!{\text{ and }}r!=r(r-1)!{\big )}\\&={\frac {{\color {red}r}(n-1)!+(n{\color {red}-r})(n-1)!}{r(n-r){\color {blue}(r-1)!(n-r-1)!}}}\\&={\frac {n(n-1)!}{\underbrace {r{\color {blue}(r-1)!}} _{r!}\underbrace {(n-r){\color {blue}(n-r-1)!}} _{n-r!}}}\\&={\frac {n!}{r!(n-r)!}}\\&={\binom {n}{r}},\end{aligned}}}
establishing the desired identity.

${\displaystyle \Box }$

Remark.

• Another type of combinatorial proof is bijective proof, but we will not discuss it here since it is quite advanced.

Example. Let ${\displaystyle n}$ and ${\displaystyle r}$ be nonnegative integers such that ${\displaystyle n\geq r}$. Prove that

${\displaystyle {\binom {n}{r}}={\binom {n}{n-r}}}$
combinatorially.

Proof. Consider the situation where there are ${\displaystyle n}$ people, and we select ${\displaystyle r}$ of them to take part in a committee. Such selection is unordered (order does not affect the result), and without replacement (we cannot select one person to take part in the committee multiple times). By the previous theorem, the number of ways for doing that is ${\displaystyle {\binom {n}{r}}}$.

On the other hand, we can regard this situation as selecting ${\displaystyle n-r}$ of them to not take part in the committee. Similarly, such selection is unordered and without replacement (one person cannot be chosen multiple times to not take part). Hence, the number of ways for doing that is ${\displaystyle {\binom {n}{n-r}}}$.

Since these two interpretations are made on the same situation, it follows that these two numbers of ways are the same. Hence, we have the desired identity.

${\displaystyle \Box }$

Exercise. Let ${\displaystyle m,n}$ and ${\displaystyle r}$ be nonngative integers such that ${\displaystyle m\geq r}$ and ${\displaystyle n\geq r}$. Prove the Vandermonde's identity, that is,

${\displaystyle {\binom {m+n}{r}}=\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}}$
combinatorially.

Proof

Proof. Consider the situation where ${\displaystyle r}$ indistinguishable balls are placed into ${\displaystyle m+n}$ distinguishable cells with capacity one. By the previous theorem, the number of ways for doing that is ${\displaystyle {\binom {m+n}{r}}}$.

Now, let us consider another method to count the number of ways. We focus on the first ${\displaystyle m}$ cells in the ${\displaystyle m+n}$ cells. We separate the situation into ${\displaystyle r}$ cases, based on the number of balls placed into the ${\displaystyle m}$ cells:

Case 0: 0 ball is placed into the ${\displaystyle m}$ cells. We consider the placement as a two-step process:

1. Place 0 ball into the ${\displaystyle m}$ cells (${\displaystyle {\binom {m}{\color {blue}0}}}$ way)
2. Place ${\displaystyle r-{\color {blue}0}}$ balls into the other ${\displaystyle n}$ cells (${\displaystyle {\binom {n}{r-{\color {blue}0}}}}$ ways)

Hence, the number of ways in this case is ${\displaystyle {\binom {m}{\color {blue}0}}\times {\binom {n}{r-{\color {blue}0}}}}$.

Case 1: 1 ball is placed into the ${\displaystyle m}$ cells. We consider the placement as a two-step process:

1. Place 1 ball into the ${\displaystyle m}$ cells (${\displaystyle {\binom {m}{\color {blue}1}}}$ ways)
2. Place ${\displaystyle r-{\color {blue}1}}$ balls into the other ${\displaystyle n}$ cells (${\displaystyle {\binom {n}{r-{\color {blue}1}}}}$ ways)

Hence, the number of ways in this case is ${\displaystyle {\binom {m}{\color {blue}1}}\times {\binom {n}{r-{\color {blue}1}}}}$.

...

Case ${\displaystyle k}$: ${\displaystyle {\color {blue}k}}$ balls are placed into the ${\displaystyle m}$ cells. We consider the placement as a two-step process:

1. Place ${\displaystyle {\color {blue}k}}$ balls into the ${\displaystyle m}$ cells (${\displaystyle {\binom {m}{\color {blue}k}}}$ ways)
2. Place ${\displaystyle r-{\color {blue}k}}$ balls into the other ${\displaystyle n}$ cells (${\displaystyle {\binom {n}{r-{\color {blue}k}}}}$ ways)

Hence, the number of ways in this case is ${\displaystyle {\binom {m}{\color {blue}k}}\times {\binom {n}{r-{\color {blue}k}}}}$.

...

Case ${\displaystyle r}$: ${\displaystyle {\color {blue}r}}$ balls are placed into the ${\displaystyle m}$ cells. We consider the placement as a two-step process:

1. Place ${\displaystyle {\color {blue}r}}$ balls into the ${\displaystyle m}$ cells (${\displaystyle {\binom {m}{\color {blue}r}}}$ ways)
2. Place ${\displaystyle r-{\color {blue}r}}$ balls into the other ${\displaystyle n}$ cells (${\displaystyle {\binom {n}{r-{\color {blue}r}}}}$ way)

Hence, the number of ways in this case is ${\displaystyle {\binom {m}{\color {blue}r}}\times {\binom {n}{r-{\color {blue}r}}}}$.

We can observe that there are no common ways in any pair of these cases. Hence, the number of ways is

${\displaystyle \sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}.}$

${\displaystyle \Box }$

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

So far, we have only considered the selection without replacement, or equivalently, cells with capacity one. From this section onward, we will discuss the selection with replacement, or equivalently, cells with unlimited capacity (same thing can be chosen unlimited times). In this section, let us consider the simpler one: placing ${\displaystyle r}$ distinguishable balls into ${\displaystyle n}$ distinguishable cells with unlimited capacity. This is equivalent to ordered selection of ${\displaystyle r}$ objects from ${\displaystyle n}$ distinguishable objects with replacement, by regarding the ball 1,2,...,${\displaystyle r}$ as choice 1,2,...,${\displaystyle r}$, cell 1,2,...,${\displaystyle n}$ as object 1,2,...,${\displaystyle 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.

Proposition. The number of ways for placing ${\displaystyle r}$ distinguishable balls into ${\displaystyle n}$ distinguishable cells with unlimited capacity is ${\displaystyle n^{r}}$.

Proof. We consider the placement as a ${\displaystyle r}$-step process:

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

Altogether, by the multiplication counting principle, the number of ways is

${\displaystyle \underbrace {n\times n\times \dotsb \times n} _{r{\text{ times}}}=n^{r}.}$

${\displaystyle \Box }$

Remark.

• Actually, this situation is just a special case for the application of multiplication counting principle, where the number of ways for each of the ${\displaystyle r}$ tasks is the same (${\displaystyle n}$ ways).

Example. How many 6-digit numbers are there such that every digit is odd number?

Solution. Since every digit is odd number, there are five choices for every digit: 1,3,5,7,9. It follows that there are ${\displaystyle 5^{6}=15625}$ such numbers.

Example. How many possible outcomes are there for rolling two distinguishable dices?

Solution. There are six outcomes for each dice. Hence, the number of possible outcomes is ${\displaystyle 6^{2}=36}$.

Exercise. Suppose we draw 5 cards from a poker deck with 52 cards with replacement, where every card drawn is recorded, and the records are kept in order. How many possible records are there for drawing

(a) five aces?

(b) five aces of the same kind?

(c) five identical cards?

(Note: the method for counting the number is not necessarily the one mentioned in this section.)

Solution

(a) The number of possibilities is ${\displaystyle 4^{5}=1024}$. (For every draw, there are four choices of aces.)

(b) The number of possibilities is ${\displaystyle 4\times 1\times 1\times 1\times 1=4}$. (For the first draw, there are four choices of aces. For the following four draws, the ace drawn must be of the same kind as the first ace, and so there is only one choice for each of these four draws.)

(c) The number of possibilities is ${\displaystyle 52\times 1\times 1\times 1\times 1=52}$. (For the first draw, there are 52 choices, and for each of the remaining draws, there is only 1 choice, which is the card drawn in the first draw.)

Example. (Setting password) Suppose we set a password with 6 characters, with the following rules:

(R1) numbers are allowed
(R2) alphabets are allowed, and they are case-sensitive [1]
(R3) special characters (i.e. all characters other than numbers and alphabets) are not allowed

Show that the number of ways o set such password is 56800235584.

Proof. For each of the 6 positions available for the password, there are ${\displaystyle \underbrace {2} _{\text{cases}}\times \underbrace {26} _{\text{alphabets}}+\underbrace {10} _{\text{numbers}}=62}$ choices of characters. Also, the characters can be repeated in more than one positions, and order matters. So, this is a case of ordered selection of distinguishable objects with replacement. Thus, the desired number is ${\displaystyle \underbrace {62} _{\text{1st position}}\times \underbrace {62} _{\text{2nd position}}\times \dotsb \times \underbrace {62} _{\text{6th position}}=62^{6}=56800235584.}$

${\displaystyle \Box }$

Exercise.

1 Suppose a machine can have ${\displaystyle 3.5\times 10^{11}}$ password guesses per second. Approximate the maximum time needed for the machine to guess the six-character password correctly using the formula

${\displaystyle {\text{the maximum time needed}}\approx {\frac {\text{number of ways to set the password}}{\text{guessing speed}}}.}$
(correct to two decimal places)

 0.00 seconds 0.15 seconds 0.16 seconds 6.16 seconds 369.72 seconds

2 Suppose the password is safe if the maximum time needed for the machine to guess the password correctly, using the same formula in the previous question, is greater than or equal to 100 years (i.e. ${\displaystyle 100\times 365.25\times 24\times 3600=3155760000}$ seconds). The minimum number of characters needed for the password (with the same rules) to be safe is

 11 12 13 14 15

Example. Consider a drawer that contains some red socks and blue socks. Suppose you draw a sock from the drawer five times, with replacement. How many possible sequences of socks drawn are there?

Solution. For every draw, there are two possibilities: (i) drawing a red sock; (ii) drawing a blue sock. Thus, the number of possible sequences is ${\displaystyle 2^{5}=32}$ (since we are considering sequences, order matters).

Example. Consider a class in probability theory consisting 23 people. How many possible sequence of birthdays of the 23 people are there? (Assume that one year has 365 days.)

Solution. For every person, there are 365 possibilities for his birthday. Hence, the number of possible sequences is ${\displaystyle 365^{23}\approx 8.565\times 10^{58}}$.

Exercise. How many possible sequences are there where all people in the class have different birthdays? Hence, show that the proportion in the number of all possible sequences (those in above example) where at least two people in the class have the same birthday is approximately 50.73%. (Hint: in the class, either all people have different birthdays, or at least two people have the same birthday.)

Solution

We consider the situation as a 23-step process:

• There are 365 possibilities for the birthday of person 1.
• There are 364 possibilities for the birthday of person 2 (different from person 1).
• There are 363 possibilities for the birthday of person 3 (different from the previous 2 people).
• ...
• There are 343 possibilities for the birthday of person 23 (different from the previous 22 people).

Hence, the number of sequences is ${\displaystyle 365\times 364\times 363\times \dotsb \times 343={\frac {365!}{342!}}\approx 4.22\times 10^{58}}$.

This means the number of sequences where at least two people in the class have the same birthday is ${\displaystyle 8.565\times 10^{58}-4.22\times 10^{58}\approx 4.345\times 10^{58}}$. Hence, the proportion is ${\displaystyle {\frac {4.345\times 10^{58}}{8.565\times 10^{58}}}\approx 0.5073=50.73\%}$.

### 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 ${\displaystyle r}$ indistinguishable balls into ${\displaystyle n}$ distinguishable cells with capacity one ("task"). In that previous situation, we know that every way in the task corresponds to ${\displaystyle r!}$ ways in the procedure (where we are placing ${\displaystyle r}$ distinguishable balls), by considering the number of ways of permutating the ${\displaystyle r}$ cells occupied by one ball each.

However, in this case, every cell can contain more than one ball. This means the number of occupied cells can range from 1 (all ${\displaystyle r}$ balls in one cell) to ${\displaystyle r}$ (one ball each for the ${\displaystyle 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.

Theorem. The number of ways placing ${\displaystyle r}$ indistinguishable balls into ${\displaystyle n}$ distinguishable cells with unlimited capacity is ${\displaystyle _{n}H_{r}={\binom {n-1+r}{r}}}$.

Proof. To prove this, we introduce the stars and bars notation, to represent the placement of balls into cells. In particular, ${\displaystyle r}$ (identical) stars are used to represent the ${\displaystyle r}$ indistinguishable balls, and ${\displaystyle n}$ (ordered) spaces created by ${\displaystyle n-1}$ bars are used to represent the ${\displaystyle 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 ${\displaystyle r=9}$ indistinguishable balls into ${\displaystyle n=7}$ cells.

After introducing this notation, we are going to count the number of ways of arranging such stars and bars, since every arrangement of stars and bars correspond to one placement of the ${\displaystyle r}$ indistinguishable balls into ${\displaystyle 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 ${\displaystyle n-1}$ bars and ${\displaystyle r}$ stars can be arbitrarily arranged, to represent different placements. Altogether, there are ${\displaystyle 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 ${\displaystyle r}$ positions from these ${\displaystyle 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 ${\displaystyle {\binom {n-1+r}{r}}}$. Once we place the ${\displaystyle r}$ stars, there is only 1 way to place the bars: place them into the remaining positions.

It then follows that there are ${\displaystyle {\binom {n-1+r}{r}}}$ ways to arrange the ${\displaystyle n-1}$ bars and ${\displaystyle r}$ stars, and hence the result follows.

${\displaystyle \Box }$

Remark.

• ${\displaystyle r}$ can be greater than ${\displaystyle n}$.

Example. How many ways are there to distribute 10 identical balls into 4 different urns (with unlimited capacity)?

Solution. We can regard the 10 identical balls as 10 indistinguishable balls, and 4 different urns as 4 distinguishable cells with unlimited capacity. Then, the number of ways is ${\displaystyle _{4}H_{10}={\binom {4-1+10}{10}}={\binom {13}{10}}=286}$.

Example.

How many outcomes are there from rolling two identical dices?

Solution. We can regard the two identical dices as 2 indistinguishable balls, and the 6 outcomes from rolling a dice as 6 distinguishable cells (with unlimited capacity, since an outcome can occur more than once for the two dices). Then, the number of outcomes is ${\displaystyle _{6}H_{2}={\binom {6-1+2}{2}}={\binom {7}{2}}=21}$.

Exercise. How many outcomes are there from rolling three identical dices?

Solution

This time, we have 3 indistinguishable balls and also 6 distinguishable cells. Hence, the number of outcomes is ${\displaystyle _{6}H_{3}={\binom {6-1+3}{3}}={\binom {8}{3}}=56}$.

Example. There are 8 distinct food or drink items, namely hamburger, egg, fries, cake, apple pie, apple juice, orange juice and coke. Unless otherwise specified, a combo may consist of the same item more than once.

(a) How many distinct 4-item combos that must consist of distinct items are there?

(b) How many distinct 4-item combos are there?

(c) How many distinct 3-food-1-drink combos are there?

Solution.

We can consider the 4 choices in a combo as 4 indistinguishable balls (it should be regarded as indistinguishable since we are interested in what four choices are in a whole, but not interested in what each of the four choices is specifically), and 8 food/drink items as 8 distinguishable cells.

(a) Since the combo must consist of distinct items, it means that we cannot put at most one food choice in every cell. In other words, the capacity of the cells is one. Hence, the number of combos is given by ${\displaystyle {\binom {8}{4}}=70}$.

(b) This time, since the combo may consist of the same item more than once, it means the capacity of the cells become unlimited. Hence, the number of combos is ${\displaystyle {\binom {8-1+4}{4}}=330}$.

(c) Since the combo needs to consist of 3 food items and 1 drink item, we need two steps:

1. We need to place one of the 4 indistinguishable balls into one of the 3 distinguishable cells, representing the 3 drink items (apple juice, orange juice, and coke). (3 ways)
2. Then, we place the remaining 3 indistinguishable balls into the other 5 distinguishable cells (unlimited capacity), representing the 5 food items. (${\displaystyle _{5}H_{3}}$ ways)

It follows that the number of combos is ${\displaystyle 3\times {}_{5}H_{3}=3\times {\binom {5-1+3}{3}}=3\times {\binom {7}{3}}=105}$.

Exercise.

(a) How many distinct 4-food combos are there?

(b) Amy loves eating hamburger, so she always choose exactly two hamburgers when she chooses the items for the 4-item combos. Calculate the number of distinct ways for Amy to order a 4-item combo.

Solution

(a) Since the combo needs to consist of 4 food items, we are placing the 4 indistinguishable balls into 5 distinguishable cells representing the 5 food items. Thus, the number of combos is ${\displaystyle _{5}H_{4}={\binom {5-1+4}{4}}=70}$

(b) Since there are two indistinguishable balls that must be placed into the cell representing hamburger (one way to do this), there are two indistinguishable balls remaining, to be put into the other 7 cells (they must not be put into the cell for hamburger since Amy chooses exactly two hamburgers). Thus, the number of combos is ${\displaystyle _{7}H_{2}={\binom {7-1+2}{2}}=28}$.

Example. (Pick 3) Consider a lottery game called Pick 3. In the game, a player picks three numbers from 0 to 9 in an order, and 3 winning numbers in an order are announced a number of times per day. There are two ways to play with the three numbers when the player picks his three numbers:

1. Exact order: The player wins if the three numbers chosen by him matches exactly (in numbers and in order) with the winning numbers announced at the closest time after his pick. (Higher payout)
2. Any order: The player wins if the three numbers chosen by him matches in numbers (but not necessarily in order) with the winning numbers announced at the closest time after his pick. (Lower payout)

Thus, players choosing different ways of playing consider the winning numbers differently:

• For the players who choose exact order, they are concerning about both the order and the numbers in the winning numbers.
• For the players who choose any order, they are only concerning about the numbers in the winning numbers.

Hence, the number of distinct winning numbers can be different, since the meaning of "distinct" depends on the way of playing. (Here, "distinct" is in the sense that the outcomes meant by the distinct winning numbers are different. For instance, 1,2,3 and 1,3,2 are distinct from the exact order perspective, but not distinct from the any order perspective (since the three numbers in the winning numbers are the same, and hence the meaning of these two winning numbers are the same: if the player picks the number 1,2,3 once each, then he wins.)) In this example, we will calculate the number of distinct winning numbers, from these two perspectives.

(a) From the exact order perspective, how many distinct winning numbers are there?

(b) From the any order perspective, how many distinct winning numbers are there?

Solution.

(a) From the exact order perspective, the order of the winning numbers matters. We can then regard the formation of the winning number as a three-step process:

1. Choose one from the ten numbers 0-9 to be the first winning number. (10 ways)
2. Choose one from the ten numbers 0-9 to be the second winning number. (10 ways)
3. Choose one from the ten numbers 0-9 to be the third winning number. (10 ways)

Hence, there are ${\displaystyle 10^{3}=1000}$ distinct winning numbers.

(b) From the any order perspective, the order of the winning numbers does not matter. We are only concerned with what three numbers appear in the winning numbers. Hence, we can regard the three positions of the winning number as three indistinguishable balls, and the ten numbers 0-9 as ten distinguishable cells (with unlimited capacity since a number from 0-9 can be chosen more than once for the 3 winning numbers). Then, the number of distinct winning numbers is

${\displaystyle _{10}H_{3}={\binom {10-1+3}{3}}=220.}$

Example. (Number of integer solutions of a equation) Consider the equation

${\displaystyle x_{1}+x_{2}+\dotsb +x_{7}=10.}$
(a) How many solutions to the equation are there, where ${\displaystyle x_{1},\dotsc ,x_{7}}$ are nonegative integers?

(b) How many solutions to the equation are there, where ${\displaystyle x_{1},\dotsc ,x_{7}}$ are positive integers?

(c) Show that there are 11440 solutions to the inequality ${\displaystyle x_{1}+x_{2}+\dotsb +x_{7}<10}$ where ${\displaystyle x_{1},\dotsc ,x_{7}}$ are nonnegative integers.

Solution.

(a) We can regard the number 10 as 10 indistinguishable balls (each representing "1"), and ${\displaystyle x_{1},x_{2},\dotsc ,x_{7}}$ be 7 distinguishable cells with unlimited capacity (each can contain 0 or more balls, corresponding to the nonnegative natures of ${\displaystyle x_{1},x_{2},\dotsc ,x_{7}}$). (For instance, if the cell ${\displaystyle x_{3}}$ contains 2 balls, then it means ${\displaystyle x_{3}=2}$.) The number of solutions is thus the number of ways for placing the balls into cells, which is

${\displaystyle _{7}H_{10}={\binom {7-1+10}{10}}=8008.}$

(b) Let ${\displaystyle x_{1}'=x_{1}-1,\dotsc ,x_{7}'=x_{7}-1}$. Then, ${\displaystyle x_{1}',\dotsc ,x_{7}'}$ are nonnegative integers. Then, we have

${\displaystyle x_{1}+x_{2}+\dotsb +x_{7}=10\iff x_{1}'+x_{2}'+\dotsb +x_{7}'={\color {darkgreen}3}.}$
It follows that the number of solutions is ${\displaystyle _{7}H_{\color {darkgreen}3}={\binom {7-1+3}{3}}=84}$.

(c) One may count the number of solutions by considering all the 10 possible cases: ${\displaystyle x_{1}+\dotsb +x_{7}=0,1,\dotsc ,{\text{ or }}9}$. But here we offer an alternative and more convenient approach which uses a clever trick:

Proof. To make the inequality become an equation, we add an extra positive integer term ${\displaystyle x_{8}}$ to the LHS, which results in an equation:

${\displaystyle x_{1}+x_{2}+\dotsb +x_{8}=10}$
where ${\displaystyle x_{8}}$ is a positive integer. This equation is equivalent to the inequality, since
${\displaystyle x_{1}+x_{2}+\dotsb +x_{7}<10\iff x_{1}+x_{2}+\dotsb +x_{7}=10-\underbrace {x_{8}} _{\text{+ve integer}}<10\iff x_{1}+x_{2}+\dotsb +x_{8}=10.}$
So, the get the number of solutions to this equation, we consider the situation as the following:

• 10 indistinguishable balls
• 8 distinguishable cells representing ${\displaystyle x_{1},x_{2},\dotsc ,x_{8}}$, where each of the cells ${\displaystyle x_{1},\dotsc ,x_{7}}$ contains zero or more balls, while the cell ${\displaystyle x_{8}}$ contains one or more balls.

Since the cell ${\displaystyle x_{8}}$ must contain one or more balls, we must place one of the 10 indistinguishable balls into this cell first (1 way). Hence, there are 9 remaining indistinguishable balls. Similarly, we can ignore the ball in the cell ${\displaystyle x_{8}}$ temporarily. Then, the number of ways for placing the 9 balls into the 8 cells is ${\displaystyle _{8}H_{9}}$. After that, we can consider back the ball in cell ${\displaystyle x_{8}}$, to determine the corresponding solutions.

Thus, the number of solutions is ${\displaystyle _{8}H_{9}={\binom {8-1+9}{9}}=11440.}$

${\displaystyle \Box }$

Exercise. An investor is actively monitoring 7 different stocks, and he wants to invest $100,000 on them in some ways. Suppose the price per share for each stock is$10000. Using an appropriate result in the above example, determine

(a) the number of ways for investing in the 7 stocks.

(b) the number of ways for investing in the 7 stocks, and saving some amount of money (nonzero).

Solution

We can regard the ${\displaystyle x_{1},\dotsc ,x_{7}}$ as the number of share bought for stock 1,...,7 respectively.

(a) 8008. (The number of shares is a nonnegative integer for each stock. Since the total investment amount is $100000, the total number of shares bought is 10.) (b) 11440. (The total investment amount is less than$100000, so the total number of shares bought is less than 10.)

Example. Consider the multinomial theorem which states that

${\displaystyle (x_{1}+x_{2}+\dotsb +x_{r})^{n}=\sum _{(n_{1},n_{2},\dotsc ,n_{r}):n_{1}+n_{2}+\dotsb +n_{r}=n}^{}{\binom {n}{n_{1},n_{2},\dotsc ,n_{r}}}x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{r}^{n_{r}}}$
for every positive integer ${\displaystyle k}$ and nonnegative integer ${\displaystyle n}$. Also, ${\displaystyle n_{1},\dotsc ,n_{r}}$ are nonnegative. In particular, the summation notation means that the sum is taken over all nonnegative integer vectors (i.e., lists of numbers) ${\displaystyle (n_{1},n_{2},\dotsc ,n_{r})}$ such that ${\displaystyle n_{1}+n_{2}\dotsc +n_{r}=n}$. For example,
${\displaystyle (x_{1}+x_{2}+x_{3})^{2}={\binom {2}{2,0,0}}x_{1}^{2}x_{2}^{0}x_{3}^{0}+{\binom {2}{0,2,0}}x_{1}^{0}x_{2}^{2}x_{3}^{0}+{\binom {2}{0,0,2}}x_{1}^{0}x_{2}^{0}x_{3}^{2}+{\binom {2}{1,1,0}}x_{1}^{1}x_{2}^{1}x_{3}^{0}+{\binom {2}{1,0,1}}x_{1}^{1}x_{2}^{0}x_{3}^{1}+{\binom {2}{0,1,1}}x_{1}^{0}x_{2}^{1}x_{3}^{1}=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+2x_{1}x_{2}+2x_{1}x_{3}+2x_{2}x_{3}.}$
Show that there are ${\displaystyle _{n}H_{r}}$ terms in the expansion by the multinomial theorem.

Proof. Notice that every term in the expansion corresponds to a nonnegative integer vector ${\displaystyle (n_{1},n_{2},\dotsc ,n_{r})}$. So, the number of terms in the expansion is exactly the number of nonnegative integer vectors ${\displaystyle (n_{1},n_{2}\dotsc ,n_{r})}$, satisfying the condition that ${\displaystyle n_{1}+n_{2}+\dotsb +n_{r}=n}$, that is, the number of solutions to the equation ${\displaystyle n_{1}+n_{2}+\dotsb +n_{r}=n}$ where ${\displaystyle n_{1},n_{2},\dotsc ,n_{r}}$ are nonnegative integers.

To get this number, we regard the situation as placing ${\displaystyle n}$ indistinguishable balls into ${\displaystyle r}$ distinguishable cells, with unlimited capacity, representing ${\displaystyle n_{1},n_{2},\dotsc ,n_{r}}$ respectively. By previous result, the number is ${\displaystyle _{n}H_{r}}$.

${\displaystyle \Box }$

Example. Four fishers go fishing together. Suppose they caught 20 identical fishes today, and the fishes need to be divided among themselves. How many ways of divisions are there?

Solution. We regard the 20 fishes as 20 indistinguishable balls, and the four fishers as four distinguishable cells. The number of ways is thus

${\displaystyle _{4}H_{20}={\binom {4-1+20}{20}}=1771.}$

Example. Ten identical robots take a lift which goes from 1/F to 6/F one by one. Suppose they must exit the left at one of the floors.

(a) How many distinct exit patterns are there?

(b) Suppose the ten identical robots are replaced by ten distinct people. How many distinct exit patterns are there?

Solution.

(a) We regard ten identical robots as 10 indistinguishable balls, and the six floors as six distinguishable cells. Then, the number is ${\displaystyle _{6}H_{10}=3003}$.

(b) We regard the exit process of the 10 people as a 10-step process:

• Step 1: the first person can exit at one of the six floors. (6 ways)
• Step 2: the second person can exit at one of the six floors. (6 ways)
• ...
• Step 10: the tenth person can exit at one of the six floors. (6 ways)

Hence, the number is ${\displaystyle 6^{10}=60466176}$.

Exercise. A company has 20 employees, and they are to be divided into three teams: team A, B, C. Three of the 20 employees are to be chosen to be the team leads of team A,B,C respectively. Besides this, there are no requirements on the number of people in each team.

(a) Show that there are 171 ways of division if the 20 employees are identical robots.

(b) Show that there are 883318714920 ways of division if the 20 employees are distinct people.

Proof
(a)

Proof. We consider the division as a two-step process:

1. Choose the three team leads for team A,B,C respectively from the 120 identical robots (one way).
2. There are 17 employees remaining, and we regard them as 17 indistinguishable balls, to be placed into 3 distinguishable cells (representing three teams) with unlimited capacity. (${\displaystyle _{3}H_{17}}$ ways)

The number of ways is thus ${\displaystyle _{3}H_{17}={\binom {3-1+17}{17}}=171}$.

${\displaystyle \Box }$

(b)

Proof. We consider the division as a two-step process:

1. Choose the three team leads for team A,B,C respectively from the 20 people (${\displaystyle 20\times 19\times 18}$ ways)
2. For each of the 17 people remaining, they can be assigned to one of the three teams. (${\displaystyle 3^{17}}$ ways)

So, the number of ways is ${\displaystyle 20\times 19\times 18\times 3^{17}=883318714920}$.

${\displaystyle \Box }$

Exercise. Amy has nine identical rings. Assume that each of her fingers can wear unlimited number of rings.

(a) Show that there are 715 ways for her right hand to wear the rings.

(b) Show that there are 48620 ways for her both hands to wear the rings.

(c) Suppose four of the rings are to be worn by her left hand, and the other five to be worn by her right hand. Show that there are 8820 ways for her both hands to wear the rings.

(d) Suppose exactly one ring is to be worn by each of her ring fingers. Show that there are 3432 ways for her both hands to wear the rings.

Proof
(a)

Proof. The number of ways is ${\displaystyle _{5}H_{9}=715}$. (9 indistinguishable balls: 9 rings; 5 distinguishable cells with unlimited capacity: 5 fingers)

${\displaystyle \Box }$

(b)

Proof. The number of ways is ${\displaystyle _{10}H_{9}=48620}$. (9 indistinguishable balls: 9 rings; 10 distinguishable cells with unlimited capacity: 10 fingers)

${\displaystyle \Box }$

(c)

Proof. Consider two steps:

1. Left hand wears the rings. (${\displaystyle _{5}H_{4}=70}$ ways. 4 indistinguishable balls: 4 rings; 5 distinguishable cells with unlimited capacity: 5 fingers)
2. Right hand wears the rings. (${\displaystyle _{5}H_{5}=126}$ ways. 5 indistinguishable balls: 5 rings; 5 distinguishable cells with unlimited capacity: 5 fingers

So, the number of ways is ${\displaystyle 70\times 126=8820}$.

${\displaystyle \Box }$

(d)

Proof. Consider two steps:

1. Each of two ring fingers wear one ring. (1 way)
2. The remaining eight fingers wear seven remaining rings. (${\displaystyle _{8}H_{7}=3432}$ ways. 7 indistinguishable balls: 7 rings; 8 distinguishable cells with unlimited capacity: 8 fingers)

So, the number of ways is 3432.

${\displaystyle \Box }$

### Summary

Placing ${\displaystyle r}$ balls into ${\displaystyle n}$ distinguishable cells
cells with capacity one cells with unlimited capacity
distinguishable balls
${\displaystyle n^{r}}$
${\displaystyle {\frac {n!}{(n-r)!}}}$
indistinguishable balls
${\displaystyle {\binom {n-1+r}{r}}}$
${\displaystyle {\binom {n}{r}}}$

Exercise. Try to prove each of the above formulas, without looking the previous subsections. After that, you can compare your proofs against the proofs in the previous subsections.

Alternatively and equivalently,

Selecting ${\displaystyle r}$ objects from ${\displaystyle n}$ distinguishable objects
with replacement without replacement
ordered
${\displaystyle n^{r}}$
${\displaystyle {\frac {n!}{(n-r)!}}}$
unordered
${\displaystyle {\binom {n-1+r}{r}}}$
${\displaystyle {\binom {n}{r}}}$

### Indistinguishable cells

When the cells 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 and 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.

Example. Four people are to be grouped into 3 indistinguishable groups. Suppose every group can contain zero or more people. Show that there are 14 possible groupings.

Proof. We regard the situation as placing four distinguishable balls (representing four people) into three indistinguishable cells (representing three groups), with unlimited capacity. [2] Then, we have the following distinct placements for ball 1,2,3,4 into three indistinguishable cells (cells sorted by the number of balls contained. The one with the least balls is at leftmost, and the one with the most balls is at rightmost.). (We use the number 1,2,3,4 to indicate ball 1,2,3,4 respectively, and the three spaces created by two bars as indistinguishable cells ("sorted" cells). Notice that the order of numbers in the space does not matter. We are only concerning about what numbers are contained in each space.)

1. ${\displaystyle ||1234}$
2. ${\displaystyle |1|234}$
3. ${\displaystyle |2|134}$
4. ${\displaystyle |3|124}$
5. ${\displaystyle |4|123}$
6. ${\displaystyle |12|34}$
7. ${\displaystyle |13|24}$
8. ${\displaystyle |14|23}$
9. ${\displaystyle 1|2|34}$
10. ${\displaystyle 1|3|24}$
11. ${\displaystyle 1|4|23}$
12. ${\displaystyle 2|3|14}$
13. ${\displaystyle 2|4|13}$
14. ${\displaystyle 3|4|12}$

So, there are 14 ways.

${\displaystyle \Box }$

## A powerful tool for counting problems: generating functions

Definition. (Generating function) A generating function is a power series whose coefficients give a specific sequence of numbers. That is, the generating function of a sequence ${\displaystyle a_{0},a_{1},a_{2},\dotsc }$ is given by

${\displaystyle G(x)=\sum _{n=0}^{\infty }a_{n}x^{n}=a_{\color {darkgreen}0}x^{\color {darkgreen}0}+a_{\color {darkgreen}1}x^{\color {darkgreen}1}+a_{\color {darkgreen}2}x^{\color {darkgreen}2}+\dotsb .}$

Remark.

• The coefficient of ${\displaystyle x^{k}}$, i.e., ${\displaystyle a_{k}}$, can be obtained by ${\displaystyle a_{k}={\frac {1}{k!}}G^{(k)}(0)}$ where ${\displaystyle G^{(k)}(0)}$ denotes the ${\displaystyle k}$th derivative of the function ${\displaystyle G}$ at ${\displaystyle x=0}$.
• In later chapters, we will study two important kinds of generating functions: moment generating functions (mgf) and probability generating functions (pgf), whose coefficients give sequences of moments and probabilities respectively in some sense. The coefficients (representing moments/probabilities) can be obtained using a similar way as in above.

The following theorem gives some common generating functions.

Theorem. (Newton's generalized binomial theorem) Let ${\displaystyle \alpha }$ be a real number. Then,

${\displaystyle (1+x)^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}}$
where ${\displaystyle |x|<1}$, and ${\displaystyle {\binom {\alpha }{k}}={\frac {\alpha (\alpha -1)(\alpha -2)\dotsb (\alpha -k+1)}{k!}}}$ is the generalized binomial coefficient.

Remark.

• The series in the theorem is also called binomial series.
• The series in the equation is actually the Taylor series of ${\displaystyle (1+x)^{\alpha }}$ at zero. That is, if we let ${\displaystyle f(x)=(1+x)^{\alpha }}$, then the series is given by

${\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(0)}{n!}}x^{n}}$

where ${\displaystyle f^{(n)}(0)}$ is the ${\displaystyle n}$th derivative of function ${\displaystyle f}$ at ${\displaystyle x=0}$, and the condition ${\displaystyle |x|<1}$ is to ensure this series converges.
• However, one should be aware that merely the convergence of this Taylor series does not guarantee it converges to the actual function value (it may converge to elsewhere). Hence, just using this Taylor series is not enough to prove this theorem.
• The series in the theorem is a generating function of the sequence ${\displaystyle {\binom {\alpha }{0}},{\binom {\alpha }{1}},{\binom {\alpha }{2}},\dotsc }$.

The following are some special cases of this theorem:

• (geometric series) ${\displaystyle (1+x)^{-1}=1-x+x^{2}-x^{3}+\dotsb }$: a generating function of the sequence 1,-1,1,-1,...;
• (geometric series) ${\displaystyle (1-x)^{-1}=1+x+x^{2}+x^{3}+\dotsb }$: a generating function of the sequence 1,1,1,1,...;
• (negative binomial series) ${\displaystyle (1-x)^{-n}=\sum _{r=0}^{\infty }{\binom {n-1+r}{r}}x^{r}}$: a generating function of the sequence ${\displaystyle {\binom {n-1}{0}},{\binom {n-1+1}{1}},{\binom {n-1+2}{2}},{\binom {n-1+3}{3}},\dotsc }$ ;
• (binomial series) ${\displaystyle (1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+\dotsb +{\binom {n}{n}}x^{n}}$: a generating function of the sequence ${\displaystyle {\binom {n}{0}},{\binom {n}{1}},{\binom {n}{2}},\dotsc ,{\binom {n}{n}}}$; (${\displaystyle n}$ is nonnegative integer)
• (binomial theorem) ${\displaystyle (x+y)^{n}={\binom {n}{0}}x^{n}y^{0}+{\binom {n}{1}}x^{n-1}y+\dotsb +{\binom {n}{n}}x^{n-n}y^{n}}$. (We get this from noticing that ${\displaystyle (x+y)^{n}=x^{n}(1+y/x)^{n}}$, and applying the theorem to ${\displaystyle (1+y/x)^{n}}$ in RHS.)

Example. Show that the number of ways for placing ${\displaystyle r}$ indistinguishable balls into ${\displaystyle n}$ distinguishable cells is ${\displaystyle {\binom {n}{r}}}$ using the notion of generating function.

Proof. We encode the selection process into a binomial series, and then use the coefficients to determine the desired number of ways. To be more precise, consider the binomial series:

${\displaystyle \underbrace {(1+x)(1+x)\dotsb (1+x)} _{n{\text{ times}}}=(1+x)^{n}=1+\cdots +{\binom {n}{r}}x^{r}+\cdots +{\binom {n}{n}}x^{n}.}$
We encode the ${\displaystyle n}$ brackets ${\displaystyle (1+x)}$ as ${\displaystyle n}$ cells, and if we choose "1" in the bracket, then the cell has zero ball. If we choose "${\displaystyle x}$" in the bracket, then the cell has one ball. Since there are ${\displaystyle r}$ balls, and thus ${\displaystyle r}$ of the ${\displaystyle n}$ brackets contain one ball, it follows that the desired number of ways is the coefficient of ${\displaystyle x^{r}}$ (the coefficient gives the number of ways to "build" ${\displaystyle x^{r}}$ through multiplying ${\displaystyle x}$ in exactly ${\displaystyle r}$ brackets together (the "${\displaystyle x}$"s are obtained by placing one ball in exactly ${\displaystyle r}$ cells)). Thus, the number of ways is ${\displaystyle {\binom {n}{r}}}$.

${\displaystyle \Box }$

Example. Show that the number of ways for placing ${\displaystyle r}$ indistinguishable balls into ${\displaystyle n}$ distinguishable cells with unlimited capacity is ${\displaystyle {\binom {n-1+r}{r}}}$.

Proof. We encode the ${\displaystyle n}$ brackets ${\displaystyle (1+x+x^{2}+\dotsb )}$ as ${\displaystyle n}$ cells. If we choose "1" in the bracket, then the cell has zero ball, if we choose "${\displaystyle x}$" in the bracket, then the cell has one ball, if we choose "${\displaystyle x^{2}}$" in the bracket, then the cell has two balls, etc. Then, the desired number is the coefficient of ${\displaystyle x^{r}}$ (number of ways to "build" ${\displaystyle x^{r}}$, through multiplying some powers of ${\displaystyle x}$ in different brackets (the powers are obtained by some balls in some cells)) in the generating function

${\displaystyle \underbrace {(1+x+x^{2}+\dotsb )(1+x+x^{2}+\cdots )\cdots (1+x+x^{2}+\cdots )} _{n{\text{ times}}}=\underbrace {(1-x)^{-1}(1-x)^{-1}\dotsb (1-x)^{-1}} _{n{\text{ times}}}=(1-x)^{-n}.}$
This is the negative binomial series. So, the coefficient of ${\displaystyle x^{r}}$ is
${\displaystyle {\binom {n-1+r}{r}}.}$

${\displaystyle \Box }$

Example. Show that the number of ways for placing ${\displaystyle n}$ distinguishable balls into cell 1,2,...,${\displaystyle k}$, where cell 1,2,...,${\displaystyle k}$ must contain ${\displaystyle n_{1},n_{2},\dotsc ,n_{k}}$ balls respectively, is ${\displaystyle {\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}}$, using the notion of generating function.

Proof. We encode the ${\displaystyle n}$ brackets ${\displaystyle (x_{1}+x_{2}+\dotsb +x_{k})}$ as ${\displaystyle n}$ cells. If ${\displaystyle x_{1},x_{2},\dotsc ,x_{k}}$ are chosen, then we put a ball into the cell 1,2,...,${\displaystyle k}$. Since we want cell 1,2,...,${\displaystyle k}$ contains exactly ${\displaystyle n_{1},n_{2},\dotsc ,n_{k}}$ balls, we are interested in the coefficient of ${\displaystyle x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}}$, i.e., the number of ways to multiply different "${\displaystyle x_{i}}$" in different brackets together to create the product ${\displaystyle x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}}$, in

${\displaystyle \underbrace {(x_{1}+x_{2}+\cdots +x_{k})(x_{1}+x_{2}+\cdots +x_{k})\cdots (x_{1}+x_{2}+\cdots +x_{k})} _{n{\text{ times}}}=(x_{1}+x_{2}+\cdots +x_{k})^{n},}$
which is ${\displaystyle {\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}}$, by multinomial theorem.

${\displaystyle \Box }$

Example. Calculate the number of solutions to the equation ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=26}$ where ${\displaystyle x_{1},x_{2},\dotsc ,x_{6}}$ are positive, ${\displaystyle x_{5}>3}$, and ${\displaystyle 3\leq x_{6}<6}$.

Solution. Consider the generating function

${\displaystyle \underbrace {(x+x^{2}+x^{3}+\dotsb )^{4}} _{x_{1},x_{2},x_{3},x_{4}}\underbrace {(x^{4}+x^{5}+x^{6}+\dotsb )} _{x_{5}}\underbrace {(x^{3}+x^{4}+x^{5})} _{x_{6}}=x^{4}(1-x)^{-4}x^{4}(1-x)^{-1}(x^{3}+x^{4}+x^{5})=(x^{11}+x^{12}+x^{13})(1-x)^{-5}.}$
(Powers of ${\displaystyle x}$ in different brackets indicate the intger chosen for different unknown ${\displaystyle x_{i}}$)

By Newton's generalized binomial theorem, the coefficient of ${\displaystyle x^{15},x^{14},x^{13}}$ in ${\displaystyle (1-x)^{-5}}$ is ${\displaystyle {\binom {-5}{15}}(-1)^{15}=3876,{\binom {-5}{14}}(-1)^{14}=3060,{\binom {-5}{13}}(-1)^{13}=2380}$ respectively. This means the coefficient of ${\displaystyle x^{26}}$ in ${\displaystyle (x^{11}+x^{12}+x^{13})(1-x)^{-5}}$ is ${\displaystyle 3876+3060+2380=9316}$. Hence, the number of solutions is 9316.

Remark.

• One can also notice that ${\displaystyle (1-x)^{-5}}$ is a negative binomial series, and proceed to use, e.g., ${\displaystyle {\binom {5-1+15}{15}}}$ to get the coefficient of ${\displaystyle x^{15}}$ in ${\displaystyle (1-x)^{-5}}$.

Example. Suppose you go to a fruit shop for buying 15 fruits. The fruit shop has two apples, three pears, six bananas, and unlimited number of grapefruits left. Show that you can buy the 15 fruits in 84 ways. (Assume that fruits of each type are identical, and hence indistinguishable.)

Proof. Consider the generating function

{\displaystyle {\begin{aligned}G(x)&=\underbrace {(1+x+x^{2})} _{\text{apple}}\underbrace {(1+x+x^{2}+x^{3})} _{\text{pear}}\underbrace {(1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})} _{\text{banana}}\underbrace {(1+x+x^{2}+\dotsb )} _{\text{grapefruit}}\\&={\frac {1-x^{3}}{1-x}}\cdot {\frac {1-x^{4}}{1-x}}\cdot {\frac {1-x^{7}}{1-x}}\cdot {\frac {1}{1-x}}&({\text{geometric series formulas}})\\&=(1-x^{3})(1-x^{4})(1-x^{7})(1-x)^{-4}\\&=(1-x^{3}-x^{4}+x^{10}+x^{11}-x^{14})(1-x)^{-4}.\end{aligned}}}
(The powers of ${\displaystyle x}$ in different brackets indicate the number of different fruits bought.) By Newton's generalized binomial theorem, the coefficients of ${\displaystyle x^{15},x^{12},x^{11},x^{5},x^{4},x}$ in ${\displaystyle (1-x)^{-4}}$ is ${\displaystyle {\binom {-4}{15}}(-1)^{15}=816,{\binom {-4}{12}}(-1)^{12}=455,{\binom {-4}{11}}(-1)^{11}=364,{\binom {-4}{5}}(-1)^{5}=56,{\binom {-4}{4}}(-1)^{4}=35,{\binom {-4}{1}}(-1)=4}$ respectively. Thus, the desired number of ways is the coefficient of ${\displaystyle x^{15}}$ in ${\displaystyle G(x)}$, which is
${\displaystyle 816-455-364+56+35-4=84.}$

${\displaystyle \Box }$

Example. Suppose you roll four identical dices. Show that there are 136 outcomes such that the sum of the numbers got is divisible by 9.

Proof. Consider the generating function

${\displaystyle G(x)=\underbrace {(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}} _{4{\text{ dices}}}{\overset {\text{ GS }}{=}}x^{4}(1-x^{6})^{4}(1-x)^{-4}=(x^{4}-4x^{10}+6x^{16}-4x^{22}+x^{28})(1-x)^{-4}}$
(The powers of ${\displaystyle x}$ indicate the number got.) Since four dices are rolled, the sum of the numbers ranges from 4 to 24. In this number range, 9 and 18 are divisible by 9. Thus, the desired number of outcomes is the sum of the coefficients of ${\displaystyle x^{9},x^{18}}$ in ${\displaystyle G(x)}$. Now, let us find these coefficients one by one.

Coefficient of ${\displaystyle x^{9}}$:

By Newton's generalized binomial theorem, the coefficient of ${\displaystyle x^{5}}$ in ${\displaystyle (1-x)^{-4}}$ is

${\displaystyle -{\binom {-4}{5}}=56.}$
Thus, the coefficient of ${\displaystyle x^{9}}$ is 56.

Coefficient of ${\displaystyle x^{18}}$:

By Newton's generalized binomial theorem, the coefficient of ${\displaystyle x^{14},x^{8},x^{2}}$ in ${\displaystyle (1-x)^{-4}}$ is

${\displaystyle {\binom {-4}{14}}=680,{\binom {-4}{8}}=165,{\binom {-4}{2}}=10}$
respectively. Hence, the coefficient of ${\displaystyle x^{18}}$ is
${\displaystyle 680-4(165)+6(10)=80.}$

It follows the number of outcomes is ${\displaystyle 56+80=136}$.

${\displaystyle \Box }$

Exercise. There are 8 distinct food or drink items, namely hamburger, egg, fries, cake, apple pie, apple juice, orange juice and coke. Unless otherwise specified, a combo may consist of the same item more than once.

(a) Suppose each food or drink item only has 2 left in the stock. Show that the number of distinct 4-item combos is 266. (Hint: You may find the following useful: ${\displaystyle (1-x^{3})^{8}=1-8x^{3}+{\text{terms with order higher than }}x^{4}}$ (this can be obtained by applying the Newton's generalized binomial theorem, regarding "${\displaystyle -x^{3}}$" as ${\displaystyle x}$ in the theorem.)

(b) Suppose each food costs $10, while each drink costs$5. Show that the number of distinct $20 combos is 60. (Hint: consider$5 as a unit. Then, each food corresponds to two units, and each drink corresponds to one unit. Using this idea, construct an appropriate generating function with the powers as those "units". After that you may find the following useful: ${\displaystyle (1-x^{2})^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}(-x^{2})^{k}}$ (obtained by regarding the "${\displaystyle x^{2}}$" as "${\displaystyle x}$" in the generalized binomial theorem (and the condition becomes ${\displaystyle |x^{2}|<1}$).)

Proof
(a)

Proof. Consider the generating function

${\displaystyle G(x)=\underbrace {(1+x+x^{2})^{8}} _{\text{food/drink item}}{\overset {\text{ GS }}{=}}(1-x^{3})^{8}(1-x)^{-8}=(1-8x^{3}+{\text{terms with order higher than }}x^{4})(1-x)^{-8}}$
(Powers of ${\displaystyle x}$ in different brackets represent the number of different items chosen.) By Newton's generalized binomial theorem, the coefficient of ${\displaystyle x^{4},x}$