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 $n_{1}$ ways to do task 1 and $n_{2}$ ways to do task 2, but we cannot do both tasks together, then we have $n_{1}+n_{2}$ ways to do task 1 or task 2.

Remark.

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

More generally, we have the subtraction counting principle:

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

Remark.

• An interpretation: since $n_{1}+n_{2}$ includes too many ways (some are double counted), we need to exclude the double counted ways ($n_{3}$ of them).
• Setting $n_{3}=0$ gives the addition principle of counting.
• In set theoretic terms, this means if $A$ and $B$ are finite sets (containing the ways to do task 1 and 2 respectively), then $|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 $n$ be a positive integer, and $S_{1},S_{2},\dotsc ,S_{n}$ be finite sets. Then, the cardinality of their union is $${\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 $S_{1},S_{2},\dotsc ,S_{n}$ contains the ways to do task 1,2,...,$n$. Then, the union $S_{1}\cup S_{2}\cup \dotsb \cup S_{n}$ contains the ways to do task 1,2,... or $n$.

Example. (Special cases of inclusion-exclusion principle) When $n=2$, the inclusion-exclusion principle gives $$|S_{1}\cup S_{2}|=|S_{1}|+|S_{2}|-|S_{1}\cap S_{2}|.$$ When $n=3$, the inclusion-exclusion principle gives $$|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 $E$, $F$, $G$ be the set containing the people speaking English, French and German respectively. Then, by inclusion-exclusion principle, $$|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 $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 $k$ people among the 140 people now learn to speak English. Calculate $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)

A tree diagram that illustrates the idea.

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

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

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

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

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

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

is true.

Inductive Step: We want to show that $P(k+1)$ is true. So, we now assume that there are $m_{1},m_{2},\dotsc ,m_{k},{\color {darkgreen}m_{k+1}}$ ways to do the task $1,2,\dotsc ,k,{\color {darkgreen}k+1}$ respectively. By the inductive hypothesis, there are $m_{1}\times m_{2}\times \dotsb \times m_{k}$ ways to do the first $k$ tasks (task $1,2,\dotsc ,k$). Now, for each of the $m_{1}\times m_{2}\times \dotsb m_{k}$ ways of doing the first $k$ tasks, there are ${\color {darkgreen}m_{k+1}}$ ways to do the task $k+1$. Expressing it using a table, we have $${\begin{array}{cc}{\text{ways of doing the first }}k{\text{ tasks}}&{\text{number of ways to do task }}k+1\\\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 $k+1$ tasks (the first $k$ tasks, and the task $k+1$) is $$\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, $P(k+1)$ is true.

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

$\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 $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:

1. "two heads"
2. "one heads, one tails"
3. "two tails",

instead of $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 $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 $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 $3\times 2\times 3=18$.

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

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

$\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 $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 $6\cdot 6=36$.

$\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 $(a,b)$ to denote number $a$ and $b$ facing up in original red and blue dice respectively, we have $${\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 $5+4+3+2+1=15$ pairs removed, so the desired number is $36-15=21$.

$\Box$

Division counting principle

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

Graphically, it looks like $${\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 ${\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)

An animation illustrating the idea.

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 $$\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 $${\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 $$\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 $${\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 $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 $${\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 $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 $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 $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 $${\frac {1814400}{14400}}=126.$$

$\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 ${\frac {120}{4}}=30$ animals in the cage.
• Student B: Since every chicken has two feet, there are ${\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 ${\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: $${\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 $r$ balls into $n$ cells. From here, one may then ask why do we consider this particular situation, and it may seem that we rarely encounter this situation in practice. Often, we want to count the number of ways for doing things other than placing balls into cells.

Although many situations encountered may seem to be quite different from this situation, particularly, the background is usually not about placing balls into cells, we may 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 $r$ balls into $n$ cells" (for some $n$ and $r$):

1. Number of possible birthdays for 10 people: placing 10 "people" (balls) into 365 "birthday dates" (cells). (Here, we assume one year has only 365 days.) Notice that we are 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 $n$ be a nonnegative integer. The factorial of $n$, denoted by $n!$, is $$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 $r$ objects from $n$ objects without replacement. We can regard this to be abstractly equivalent to placing $r$ distinguishable balls (choice 1,2,...,$r$) into $n$ distinguishable cells (object 1,2,...,$n$) with capacity one.

• The capacity is one, since 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 $r$ distinguishable balls into $n$ distinguishable cells with capacity one is $_{n}P_{r}={\frac {n!}{(n-r)!}}$.

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

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

Thus, by multiplication principle of counting, the desired number of ways is $$\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)!}}.$$

$\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 $$_{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 $$_{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 $$_{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 $_{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 $${\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 $$_{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 $$_{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) $n$ distinguishable objects is $n!$.

Proof. Ordering $n$ distinguishable objects is the same as putting the $n$ distinguishable objects (balls) into $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 $_{n}P_{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$.

$\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 $5!$ ways for the "procedure". But the two "P"s are actually indistinguishable, so some ways in the $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": $${\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 $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 $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 $${\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 $n$ distinguishable objects into $k$ groups, where group 1,2,...,$k$ must contain $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 $n$ distinguishable balls into cell 1,2,...,$k$, where cell 1,2,...,$k$ must contain $n_{1},n_{2},\dotsc ,n_{k}$ balls respectively".

Theorem. The number of ways for placing $n$ distinguishable balls into cell 1,2,...,$k$, where cell 1,2,...,$k$ must contain $n_{1},n_{2},\dotsc ,n_{k}$ balls respectively, is ${\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,...,$k$ contains $n_{1},n_{2},\dotsc ,n_{k}$ ordered positions for placing one ball each (e.g., there are $n_{1},n_{2},\dotsc ,n_{k}$ "subcells" in cell 1,2,...,$k$). In this case, we can just regard the placement as a permutation of the $n$ distinguishable balls, since the $k$ cells altogether contain $n$ "ordered positions" ("subcells"). After having such consideration, the number of ways of placement is $n!$.

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

$\Box$

Remark.

• ${\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 ${\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 ${\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 $3360+3360=6720$.

Now, we consider the number of ordering without any restrictions. The number is given by ${\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 $30240-6720=23520$.

$\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 $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 $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 $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 $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 ${\frac {52!}{(13!)^{4}}}\approx 5.364\times 10^{28}$.

$\Box$

(b)

Proof. We first consider the 48 cards in the deck without ace. There are ${\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 $4!$. It follows that the number is $4!\times {\frac {48!}{(12!)^{4}}}\approx 5.659\times 10^{27}$.

$\Box$

(c)

Proof. We first consider the 48 cards in the deck without ace. There are ${\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 $4\times {\frac {48!}{(13!)^{3}\times 9!}}\approx 5.667\times 10^{26}$.

$\Box$

(d)

Proof. We first consider the 39 cards in the deck, with a certain kind of cards removed. There are ${\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 $4\times {\frac {39!}{(13!)^{3}}}\approx 3.379\times 10^{17}$.

$\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 ${\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.

$\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. $${\begin{array}{c|c|c|c|c}A&&&&B\\\hline &&E&&\\\hline C&&&&D\\\end{array}}$$ Suppose we are initially located at $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 $A$ to $D$ is 15.

Proof. First, observe that we need exactly 6 steps to walk from $A$ to $D$, consisting 4 steps of walking rightward ($\rightarrow$) and 2 steps of walking downward ($\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 $\rightarrow$'s and 2 $\downarrow$'s.

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

Hence, the desired number is $$\underbrace {6!} _{\text{steps}}/(\underbrace {2!} _{\downarrow }\underbrace {4!} _{\rightarrow })=15.$$

$\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 $E$ in the walking process from $A$ to $D$ (Hint: consider this as walking from $A$ to $E$, then from $E$ to $D$).

	9
	10
	11
	12
	13

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

	10
	11
	12
	13
	14

4 Suppose Amy and Bob is initially located at $A$ and $B$ respectively. Calculate the number of distinct sequence of steps for Amy such that Amy and Bob meet at $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 $r$ distinguishable balls into $n$ distinguishable cells with capacity one. Now, we will consider the case where the $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 $r$ balls represent the choices, and every cell can still contain at most one ball). However, in this case, the $r$ balls (choices) are indistinguishable. So, we only know that which $r$ of the $n$ cells contain one ball (are selected), but do not know in 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 ($r$ of them), they are put into the group "selected" (they are selected to place one ball).
• For the cells with zero ball ($n-r$ of them), they are put into the group "not selected" (they are not selected to place one ball).

So, this means such placement is equivalent to the partition of $n$ distinguishable cells into two groups with $r$ distinguishable cells and $n-r$ distinguishable cells respectively. With such consideration, the following result is transparent:

Theorem. The number of ways for placing $r$ indistinguishable balls into $n$ distinguishable cells with capacity one is ${\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 ${\frac {n!}{(n-r)!}}$ ways for placing $r$ distinguishable balls into $n$ distinguishable cells with capacity one. But here we want the number of ways where the balls are indistinguishable. So, we consider the division counting principle: every placement where the balls are indistinguishable corresponds to $r!$ placements (obtained by permutating the $r$ distinguishable balls) where the balls are distinguishable. It follows that the desired number of ways is $${\frac {n!}{(n-r)!}}{\bigg /}r!={\frac {n!}{r!(n-r)!}}.$$

$\Box$

Remark.

• ${\binom {n}{r}}$ is called the binomial coefficient. It can also be denoted by $_{n}C_{r}$.
• ${\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 ${\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 (${\binom {6}{2}}$ ways)
2. select 2 to be committees from the 4 women (${\binom {4}{2}}$ ways)

By the multiplication counting principle, the number of ways is ${\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 (${\binom {4}{2}}$ ways)

By multiplication counting principle, there are $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 (${\binom {6}{2}}$ ways)

Then, by multiplication counting principle, there are $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 $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 $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 $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 $90+60=150$.

Example.

The dotted ellipses remind us that these are sets, where order is not important.

Consider the set $\{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 $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) ${\binom {3}{0}}=1$.

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

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

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

List of subsets:

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

There are altogether $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 ${\binom {16}{3}}={\frac {16\times 15\times 14}{3\times 2\times 1}}=560.$

Exercise.

1 Amy, Bob and Chris are among the $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 $${\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 ${\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 $3819816\times 46=175711536$.

Example. (Proving an identity combinatorially) Let $n$ and $r$ be nonnegative integers such that $n\geq r$. Prove that $${\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 $r$ indistinguishable balls are placed into $n$ distinguishable cells with capacity one. By the previous theorem, the number of ways is ${\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 $r-1$ balls remaining, and $n-1$ cells remaining. So, the number of ways of placing the $r-1$ remaining balls into the $n-1$ remaining cells is ${\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 ${\binom {n-1}{r-1}}$.

Case 2: cell 1 contains zero ball. Then, there are $r$ balls remaining, and $n-1$ cells remaining. So, the number of ways is similarly ${\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 $${\binom {n-1}{r-1}}+{\binom {n-1}{r}},$$ corresponding to the expressions in RHS.

$\Box$

(b)

Proof. Consider the RHS. We have $${\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.

$\Box$

Remark.

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

Example. Let $n$ and $r$ be nonnegative integers such that $n\geq r$. Prove that $${\binom {n}{r}}={\binom {n}{n-r}}$$ combinatorially.

Proof. Consider the situation where there are $n$ people, and we select $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 ${\binom {n}{r}}$.

On the other hand, we can regard this situation as selecting $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 ${\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.

$\Box$

Exercise. Let $m,n$ and $r$ be nonngative integers such that $m\geq r$ and $n\geq r$. Prove the Vandermonde's identity, that is, $${\binom {m+n}{r}}=\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}$$ combinatorially.

Proof

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

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

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

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

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

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

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

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

...

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

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

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

...

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

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

Hence, the number of ways in this case is ${\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 $$\sum _{k=0}^{r}{\binom {m}{k}}{\binom {n}{r-k}}.$$

$\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 $r$ distinguishable balls into $n$ distinguishable cells with unlimited capacity. This is equivalent to ordered selection of $r$ objects from $n$ distinguishable objects with replacement, by regarding the ball 1,2,...,$r$ as choice 1,2,...,$r$, cell 1,2,...,$n$ as object 1,2,...,$n$. In particular, since every object can be chosen unlimited times, every cell has unlimited capacity. But counting the number of ways of such placement is actually quite simple, since we can just use the multiplication counting principle.

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

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

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

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

$\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 $r$ tasks is the same ($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 $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 $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 $4^{5}=1024$. (For every draw, there are four choices of aces.)

(b) The number of possibilities is $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 $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

(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 $\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 $\underbrace {62} _{\text{1st position}}\times \underbrace {62} _{\text{2nd position}}\times \dotsb \times \underbrace {62} _{\text{6th position}}=62^{6}=56800235584.$

$\Box$

Exercise.

1 Suppose a machine can have $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 $${\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. $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 $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 $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 $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 $8.565\times 10^{58}-4.22\times 10^{58}\approx 4.345\times 10^{58}$. Hence, the proportion is ${\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 $r$ indistinguishable balls into $n$ distinguishable cells with capacity one ("task"). In that previous situation, we know that every way in the task corresponds to $r!$ ways in the procedure (where we are placing $r$ distinguishable balls), by considering the number of ways of permutating the $r$ cells occupied by 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 $r$ balls in one cell) to $r$ (one ball each for the $r$ cells), depending on how we put the balls into the cells in the task. Hence, different ways in the task correspond to different number of ways in the procedure. Thus, we cannot apply the division counting principle.

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

Theorem. The number of ways placing $r$ indistinguishable balls into $n$ distinguishable cells with unlimited capacity is $_{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, $r$ (identical) stars are used to represent the $r$ indistinguishable balls, and $n$ (ordered) spaces created by $n-1$ bars are used to represent the $n$ distinguishable cells. For instance,

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

           |
           |          placement
           v

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

is used to represent

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

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

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

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

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

$\Box$

Remark.

• $r$ can be greater than $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 $_{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 $_{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 $_{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 ${\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 ${\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. ($_{5}H_{3}$ ways)

It follows that the number of combos is $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 $_{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 $_{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 $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 $$_{10}H_{3}={\binom {10-1+3}{3}}=220.$$

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

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

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

Solution.

(a) We can regard the number 10 as 10 indistinguishable balls (each representing "1"), and $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 $x_{1},x_{2},\dotsc ,x_{7}$). (For instance, if the cell $x_{3}$ contains 2 balls, then it means $x_{3}=2$.) The number of solutions is thus the number of ways for placing the balls into cells, which is $$_{7}H_{10}={\binom {7-1+10}{10}}=8008.$$

(b) Let $x_{1}'=x_{1}-1,\dotsc ,x_{7}'=x_{7}-1$. Then, $x_{1}',\dotsc ,x_{7}'$ are nonnegative integers. Then, we have $$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 $_{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: $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 $x_{8}$ to the LHS, which results in an equation: $$x_{1}+x_{2}+\dotsb +x_{8}=10$$ where $x_{8}$ is a positive integer. This equation is equivalent to the inequality, since $$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 $x_{1},x_{2},\dotsc ,x_{8}$, where each of the cells $x_{1},\dotsc ,x_{7}$ contains zero or more balls, while the cell $x_{8}$ contains one or more balls.

Since the cell $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 $x_{8}$ temporarily. Then, the number of ways for placing the 9 balls into the 8 cells is $_{8}H_{9}$. After that, we can consider back the ball in cell $x_{8}$, to determine the corresponding solutions.

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

$\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 $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 $$(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 $k$ and nonnegative integer $n$. Also, $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) $(n_{1},n_{2},\dotsc ,n_{r})$ such that $n_{1}+n_{2}\dotsc +n_{r}=n$. For example, $$(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 $_{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 $(n_{1},n_{2},\dotsc ,n_{r})$. So, the number of terms in the expansion is exactly the number of nonnegative integer vectors $(n_{1},n_{2}\dotsc ,n_{r})$, satisfying the condition that $n_{1}+n_{2}+\dotsb +n_{r}=n$, that is, the number of solutions to the equation $n_{1}+n_{2}+\dotsb +n_{r}=n$ where $n_{1},n_{2},\dotsc ,n_{r}$ are nonnegative integers.

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

$\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 $$_{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 $_{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 $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. ($_{3}H_{17}$ ways)

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

$\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 ($20\times 19\times 18$ ways)
2. For each of the 17 people remaining, they can be assigned to one of the three teams. ($3^{17}$ ways)

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

$\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 $_{5}H_{9}=715$. (9 indistinguishable balls: 9 rings; 5 distinguishable cells with unlimited capacity: 5 fingers)

$\Box$

(b)

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

$\Box$

(c)

Proof. Consider two steps:

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

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

$\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. ($_{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.

$\Box$

Summary

Placing $r$ balls into $n$ distinguishable cells

	cells with capacity one	cells with unlimited capacity
distinguishable balls	$$n^{r}$$	$${\frac {n!}{(n-r)!}}$$
indistinguishable balls	$${\binom {n-1+r}{r}}$$	$${\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 $r$ objects from $n$ distinguishable objects

	with replacement	without replacement
ordered	$$n^{r}$$	$${\frac {n!}{(n-r)!}}$$
unordered	$${\binom {n-1+r}{r}}$$	$${\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. 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. $||1234$
2. $|1|234$
3. $|2|134$
4. $|3|124$
5. $|4|123$
6. $|12|34$
7. $|13|24$
8. $|14|23$
9. $1|2|34$
10. $1|3|24$
11. $1|4|23$
12. $2|3|14$
13. $2|4|13$
14. $3|4|12$

So, there are 14 ways.

$\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 $a_{0},a_{1},a_{2},\dotsc$ is given by $$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 $x^{k}$, i.e., $a_{k}$, can be obtained by $a_{k}={\frac {1}{k!}}G^{(k)}(0)$ where $G^{(k)}(0)$ denotes the $k$th derivative of the function $G$ at $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 $\alpha$ be a real number. Then, $$(1+x)^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}$$ where $|x|<1$, and ${\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 $(1+x)^{\alpha }$ at zero. That is, if we let $f(x)=(1+x)^{\alpha }$, then the series is given by

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

where $f^{(n)}(0)$ is the $n$th derivative of function $f$ at $x=0$, and the condition $|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 ${\binom {\alpha }{0}},{\binom {\alpha }{1}},{\binom {\alpha }{2}},\dotsc$.

The following are some special cases of this theorem:

• (geometric series) $(1+x)^{-1}=1-x+x^{2}-x^{3}+\dotsb$: a generating function of the sequence 1,-1,1,-1,...;
• (geometric series) $(1-x)^{-1}=1+x+x^{2}+x^{3}+\dotsb$: a generating function of the sequence 1,1,1,1,...;
• (negative binomial series) $(1-x)^{-n}=\sum _{r=0}^{\infty }{\binom {n-1+r}{r}}x^{r}$: a generating function of the sequence ${\binom {n-1}{0}},{\binom {n-1+1}{1}},{\binom {n-1+2}{2}},{\binom {n-1+3}{3}},\dotsc$ ;
• (binomial series) $(1+x)^{n}={\binom {n}{0}}+{\binom {n}{1}}x+\dotsb +{\binom {n}{n}}x^{n}$: a generating function of the sequence ${\binom {n}{0}},{\binom {n}{1}},{\binom {n}{2}},\dotsc ,{\binom {n}{n}}$; ($n$ is nonnegative integer)
• (binomial theorem) $(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 $(x+y)^{n}=x^{n}(1+y/x)^{n}$, and applying the theorem to $(1+y/x)^{n}$ in RHS.)

Example. Show that the number of ways for placing $r$ indistinguishable balls into $n$ distinguishable cells is ${\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: $$\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 $n$ brackets $(1+x)$ as $n$ cells, and if we choose "1" in the bracket, then the cell has zero ball. If we choose "$x$" in the bracket, then the cell has one ball. Since there are $r$ balls, and thus $r$ of the $n$ brackets contain one ball, it follows that the desired number of ways is the coefficient of $x^{r}$ (the coefficient gives the number of ways to "build" $x^{r}$ through multiplying $x$ in exactly $r$ brackets together (the "$x$"s are obtained by placing one ball in exactly $r$ cells)). Thus, the number of ways is ${\binom {n}{r}}$.

$\Box$

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

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

$\Box$

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

Proof. We encode the $n$ brackets $(x_{1}+x_{2}+\dotsb +x_{k})$ as $n$ cells. If $x_{1},x_{2},\dotsc ,x_{k}$ are chosen, then we put a ball into the cell 1,2,...,$k$. Since we want cell 1,2,...,$k$ contains exactly $n_{1},n_{2},\dotsc ,n_{k}$ balls, we are interested in the coefficient of $x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$, i.e., the number of ways to multiply different "$x_{i}$" in different brackets together to create the product $x_{1}^{n_{1}}x_{2}^{n_{2}}\dotsb x_{k}^{n_{k}}$, in $$\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 ${\frac {n!}{n_{1}!n_{2}!\dotsb n_{k}!}}$, by multinomial theorem.

$\Box$

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

Solution. Consider the generating function $$\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 $x$ in different brackets indicate the intger chosen for different unknown $x_{i}$)

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

Remark.

• One can also notice that $(1-x)^{-5}$ is a negative binomial series, and proceed to use, e.g., ${\binom {5-1+15}{15}}$ to get the coefficient of $x^{15}$ in $(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 $${\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 $x$ in different brackets indicate the number of different fruits bought.) By Newton's generalized binomial theorem, the coefficients of $x^{15},x^{12},x^{11},x^{5},x^{4},x$ in $(1-x)^{-4}$ is ${\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 $x^{15}$ in $G(x)$, which is $$816-455-364+56+35-4=84.$$

$\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 $$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 $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 $x^{9},x^{18}$ in $G(x)$. Now, let us find these coefficients one by one.

Coefficient of $x^{9}$:

By Newton's generalized binomial theorem, the coefficient of $x^{5}$ in $(1-x)^{-4}$ is $$-{\binom {-4}{5}}=56.$$ Thus, the coefficient of $x^{9}$ is 56.

Coefficient of $x^{18}$:

By Newton's generalized binomial theorem, the coefficient of $x^{14},x^{8},x^{2}$ in $(1-x)^{-4}$ is $${\binom {-4}{14}}=680,{\binom {-4}{8}}=165,{\binom {-4}{2}}=10$$ respectively. Hence, the coefficient of $x^{18}$ is $$680-4(165)+6(10)=80.$$

It follows the number of outcomes is $56+80=136$.

$\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: $(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 "$-x^{3}$" as $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: $(1-x^{2})^{\alpha }=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}(-x^{2})^{k}$ (obtained by regarding the "$x^{2}$" as "$x$" in the generalized binomial theorem (and the condition becomes $|x^{2}|<1$).)

Proof

(a)

Proof. Consider the generating function $$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 $x$ in different brackets represent the number of different items chosen.) By Newton's generalized binomial theorem, the coefficient of $x^{4},x$ in $(1-x)^{-8}$ is $${\binom {-8}{4}}=330,-{\binom {-8}{1}}=8$$ respectively. Thus, the coefficient of $x^{4}$ in $G(x)$ (the desired number) is $$330-8(8)=266.$$

$\Box$

(b)

Proof. Consider the generating function $$G(x)=\underbrace {(1+x^{2}+x^{4}+\dotsb )^{5}} _{\text{food}}\underbrace {(1+x+x^{2}+\dotsb )^{3}} _{\text{drink}}=(1-x^{2})^{-5}(1-x)^{-3}$$ (The powers of $x$ in different brackets indicate how many $5 is used for different food/drink items. For every food item, two $5 are needed, so the powers of $x$ increase by 2 at a time) Since the total cost n the combo needs to be $20, or four $5, the desired number is given by the coefficient of $x^{4}$.

Now, we consider the coefficients of $x^{0},x^{2},x^{4}$ in $(1-x^{2})^{-5}$: (regard the "$x^{2}$" as the "$x$" in the generalized binomial theorem)

• $x^{0}:{\binom {-5}{0}}={\color {red}1}$
• $x^{2}:-{\binom {-5}{1}}={\color {blue}5}$
• $x^{4}=(x^{2})^{2}:{\binom {-5}{2}}={\color {darkgreen}15}$

Now, we consider the coefficients of $x^{0},x^{2},x^{4}$ in $(1-x)^{-3}$: (for $x^{1},x^{3}$, we cannot use it to build $x^{4}$ since only $x^{0},x^{2},x^{4}$ (for terms with order at most $x^{4}$) are available in $(1-x^{2})^{-5}$)

• $x^{0}:{\binom {-3}{0}}={\color {darkgreen}1}$
• $x^{2}:{\binom {-3}{2}}={\color {blue}5}$
• $x^{4}:{\binom {-3}{4}}={\color {red}15}$

It follows that the coefficient of $x^{4}$ in $G(x)$ is $${\color {red}1(15)}+{\color {blue}5(6)}+{\color {darkgreen}15(1)}=60.$$

$\Box$

Miscellaneous exercises

Exercise.

File:Ryu combo.gif

Consider the game Street Fighter. In this exercise, we are considering different "combos". For simplicity, we make the following assumptions:

1. There are only four kinds of moves: punch (P), kick (K), forward (F), jump (J)
2. A combo can consist of 2-4 moves, which may or may not be distinct, and the moves can be arranged in any order (the order matters). For example,

• P is not a combo since it only consist of 1 move.
• PJJ is a combo.
• PPKF is a combo.
• KKKFJ is not a combo since it consists of 5 moves.

(a) How many distinct combos are there?

(b) How many distinct combos are there if a combo cannot start with jump?

(c) Show that there are 308 distinct combos if a combo must consist of at least one "attack move" (i.e., punch or kick).

Solution

(a) We divide the situation into 3 cases.

Case 1: The combo consists of 2 moves. Then, there are $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}=16$ distinct combos (4 choices for each move).

Case 2: The combo consists of 3 moves. Then, there are $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}=64$ distinct combos.

Case 3: The combo consists of 4 moves. Then, there are $\underbrace {4} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}\times \underbrace {4} _{\text{move 4}}=256$ distinct combos.

Since there are no common combos in these four cases, the total number of distinct combos is $16+64+256=336$.

(b) We divide the situation into 3 cases.

Case 1: The combo consists of 2 moves. Then, there are $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}=12$ distinct combos (move 1 cannot be jump. So, there are only 3 choices for move 1).

Case 2: The combo consists of 3 moves. Then, there are $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}=48$ distinct combos.

Case 3: The combo consists of 4 moves. Then, there are $\underbrace {3} _{\text{move 1}}\times \underbrace {4} _{\text{move 2}}\times \underbrace {4} _{\text{move 3}}\times \underbrace {4} _{\text{move 4}}=192$ distinct combos.

Since there are no common combos in these four cases, the total number of distinct combos is $12+48+192=252$.

(c)

Proof. We first consider the distinct combos consisting zero attack move. Similarly, we divide the situation into 3 cases.

Case 1: The combo consists of 2 moves. Then, there are $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}=4$ distinct combos (2 choices for each move).

Case 2: The combo consists of 3 moves. Then, there are $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}\times \underbrace {2} _{\text{move 3}}=8$ distinct combos.

Case 3: The combo consists of 4 moves. Then, there are $\underbrace {2} _{\text{move 1}}\times \underbrace {2} _{\text{move 2}}\times \underbrace {2} _{\text{move 3}}\times \underbrace {2} _{\text{move 4}}=16$ distinct combos.

Since there are no common combos in these four cases, the total number of distinct combos consisting zero attack move is $4+8+16=28$. Thus, to get the desired number of combos, we subtract this number (28) from the number of all possible distinct combos (336): $336-28=308$.

$\Box$

Exercise.

Consider a game which is related to swords. In this game, there are five levels of swords, 1-5. To get a level $n$ sword, the player needs to get three level $n-1$ swords, and they will be automatically combined to be a level $n$ sword. For example, to get a level 2 sword, the player needs to get three level 1 swords.

Initially, the player is given a level 1 sword, and he can earn coins by using his highest level sword (only one sword can be used) to defeat monsters. Suppose the health points (HP) of every monster is 100, and using a level $n$ sword, the player can deal $2^{n}$ damage(s) to a monster per second, that is, the damage per second (DPS) of level $n$ sword is $2^{n}$. For example, using a level 3 sword, the DPS is 8, and hence ${\frac {100}{8}}=12.5$ seconds are needed to kill a monster. Upon killing a monster, the player can obtain 1 coin, and the price of a level 1 sword is 1 coin (and only level 1 sword is purchasable, but there is unlimited supply for level 1 swords).

Show that 812.5 seconds are needed for the player to get a level 5 sword.

Proof

Proof. The game process is as follows:

1. when the player owns a level $n$ sword which is his highest level sword, the player uses it to kill some monsters to get some coins sufficient for getting two more level $n$ swords. After that, the player has three level $n$ swords, and hence can get a level $n+1$ sword.
2. Keep repeating 1. until the player gets a level 5 sword.

We consider the process of getting a level 5 sword steps by steps:

1. Use level 1 sword to kill two monsters to obtain 2 coins to purchase two level 1 swords, and then the player gets a level 2 sword. (take ${\frac {200}{2}}=100$ seconds)
2. Use level 2 sword to kill six monsters to obtain 6 coins to purchase six level 1 swords, and then the player gets two level 2 swords, and hence gets a level 3 sword. (take ${\frac {600}{2^{2}}}=150$ seconds)
3. Use level 3 sword to kill 18 monsters to obtain 18 coins to purchase 18 level 1 swords, and then the player gets six level 2 swords, and hence gets two level 3 swords. After that, the player gets a level 4 sword. (take ${\frac {1800}{2^{3}}}=225$ seconds)
4. Use level 4 sword to kill 54 monsters to obtain 54 coins to purchase 54 level 1 swords, and then 18 level 2 swords are obtained, and then 6 level 3 swords are obtained, and then 2 level 4 swords are obtained. After that, the player gets a level 5 sword. (take ${\frac {5400}{2^{4}}}=337.5$ seconds)

So, altogether we need $100+150+225+337.5=812.5$ seconds.

$\Box$

Exercise. In a certain university, a student needs to take five courses in every semester, and after passing eight semesters, the student graduates. On the other hand, if the student fails two semesters consecutively, he will be discontinued from the study. (Here, passing a semester means passing every course taken in that semester, and failing a semester means failing at least one course taken in that semester.) We consider this situation as an ordered sequence of two results: pass (P) and fail (F). For example, PPPFPFF means pass in semester 1,2,3, fail in semester 4, pass in semester 5, and fail in semester 6,7. The student is discontinued after semester 7, so the sequence stops. On the other hand, PPPPPPPP means pass in eight semesters consecutively, and the student graduates, and hence the sequence also stops.

In this exercise, we will count how many different sequences are there, in different situations.

(a) Show that there are 765 different sequences.

(b) Show that there are 466 different sequences if a student is also discontinued when he does not graduate after 12 semesters.

Proof

(a)

Proof. First, notice that the student either graduates eventually or fails eventually. That is, the sequence stops eventually. In other words, the length of the sequence must be finite. (Actually, a sequence with maximum length can be constructed by repeating the pattern "FP" eight times: FPFPFPFPFPFPFPFP. The length of this sequence is 16, and we can see that it is the maximum length, since we cannot add more "F" in between (or else the student will be discontinued), and there are eight "P"s.)

To count the number of sequences, we consider two cases:

Case 1: The student graduates eventually. This means there are eight "P"s in the sequence, but no two consecutive "F"s in the sequence. Graphically,

        P P P P P P P P
       ^ ^ ^ ^ ^ ^ ^ ^ ^
^: position for at most one "F"

In every position indicated by "^" (9 of them), we can either (i) put a "F"; or (ii) not put a "F". So, there are two ways for every position. Altogether, there are nine steps, with two ways each. Hence, the number of sequences is $2^{9}=512$.

Case 2: The student fails eventually. This means there are two consecutive "F"s in the sequence. We now consider how many different sequences are there such that the last semesters are two consecutive "F"s. The following shows the possibilities:

                           number of sequences    number of "P"s before "FF"
                   FF            1                      0

                 P FF            2                      1
                ^
               P P FF           2^2                     2
              ^ ^
             P P P FF           2^3                     3
            ^ ^ ^
           P P P P FF           2^4                     4
          ^ ^ ^ ^
         P P P P P FF           2^5                     5
        ^ ^ ^ ^ ^
       P P P P P P FF           2^6                     6
      ^ ^ ^ ^ ^ ^
     P P P P P P P FF           2^7                     7
    ^ ^ ^ ^ ^ ^ ^
^: position for at most one "F"
(semester just before "FF" must be "P", otherwise the "FF" occurs earlier)

So, the number of sequences in this case is $$1+2+2^{2}+2^{3}+2^{4}+2^{5}+2^{6}+2^{7}=253.$$

Combining both cases, it follows that there are $512+253=765$ different sequences (there are no common sequences in the two cases).

$\Box$

(b)

Proof. In this case, it is more transparent that the sequence must stop eventually, and the maximum length of the sequence is 12.

To count the number of sequences, we similarly consider two cases:

Case 1: The student graduates eventually. This means there are eight "P"s in the sequence, but no two consecutive "F"s in the sequence, and also the length of the sequence is at most 11. Graphically,

        P P P P P P P P
       ^ ^ ^ ^ ^ ^ ^ ^ ^
^: positions for placing at most 3 "F"s, with each contains at most one "F".

In the 9 positions indicated by "^", we can place at most 3 "F"s into them, with each contains at one "F". This is equivalent to the situation for placing $k$ indistinguishable balls ("F"s) into 9 distinguishable cells (indicated by "^") with capacity one, where $k=0,1,2,{\text{ or }}3$. Hence, the number of sequences is $${\binom {9}{0}}+{\binom {9}{1}}+{\binom {9}{2}}+{\binom {9}{3}}=130.$$

Case 2: The student fails eventually. We first consider the situation where there are two consecutive "F"s in the sequence (this means the student fails by making "FF", instead of not having 8 "P"s after 12 semesters). Here, we also include the situation where after making "FF", the length is just 12.

We now consider how many different sequences are there such that the last semesters are two consecutive "F"s (the length is at most 12, including the last two "F"s). The following shows the possibilities:

                           number of sequences    number of "P"s before "FF"
                   FF            1                      0              

                 P FF            2                      1
                ^
               P P FF           2^2                     2
              ^ ^
             P P P FF           2^3                     3
            ^ ^ ^
           P P P P FF           2^4                     4
          ^ ^ ^ ^
         P P P P P FF           2^5                     5   
        ^ ^ ^ ^ ^
       P P P P P P FF           9C4                     6   (place at most 4 "F"s)
      ^ ^ ^ ^ ^ ^
     P P P P P P P FF           9C3                     7   (place at most 3 "F"s)
    ^ ^ ^ ^ ^ ^ ^
(semester just before "FF" must be "P", otherwise the "FF" occurs earlier)

The number of sequences in this situation is $1+2+2^{2}+2^{3}+2^{4}+2^{5}+{\binom {9}{4}}+{\binom {9}{3}}=273$.

Now, we consider the situation where there are no two consecutive "F"s in the sequence, but the student do not pass eight semesters after 12 semesters (this means the student fails by not having 8 "P"s after 12 semesters.) The following shows the possibilities:

No. of  "P"s
     <5                           (impossible. Reason is similar to the case for 5 "P"s)

     5          P P P P P         (impossible. Even placing exactly one "F" at each position, the length is 11 < 12.)
               ^ ^ ^ ^ ^ ^

     6        P P P P P P         (place exactly 6 "F"s where each position contains at most one "F", making the length 12, and no "FF")
             ^ ^ ^ ^ ^ ^ ^  

     7      P P P P P P P         (place exactly 5 "F"s where each position contains at most one "F", making the length 12, and no "FF")
           ^ ^ ^ ^ ^ ^ ^ ^  

For the 6 "P"s case, the number of sequences is ${\binom {7}{6}}=7$, and for the 7 "P"s case, the number of sequences is ${\binom {8}{5}}=56$. So, altogether we have $7+56=63$ sequences in this situation.

Since there are no common sequences in these two situations (one situation contains "FF", another does not), in case 2, there are $273+63=336$ sequences in total.

Combining both cases, it follows that there are $130+336=466$ different sequences (there are no common sequences in the two cases).

$\Box$

Exercise. (Note: the concept of probability distributions itself is not needed to work on this exercise.)

An instructor of a course in probability theory wants to create an in-class test from his question bank. The in-class test is about the concept of probability distributions. There are 74 different questions in the question bank that are related to this concept, and they are of the following types:

• 43 questions about discrete distributions, consisting of

• 9 questions about Bernoulli distribution
• 5 questions about binomial distribution
• 7 questions about negative binomial distribution
• 6 questions about geometric distribution
• 3 questions about hypergeometric distribution
• 13 questions about Poisson distribution

• 31 questions about continuous distributions, consisting of

• 10 questions about normal distribution
• 11 questions about exponential distribution
• 3 questions about gamma distribution
• 2 questions about beta distribution
• 5 questions about uniform distribution

The in-class test will have five (distinct) questions. In the following, when considering the number of ways, the order of the questions is not important, since changing the order does not affect the content in the test.

(a) How many ways are there to create an in-class test?

(b) How many ways are there to create an in-class test with 3 questions about discrete distributions, and 2 questions about continuous distributions?

(c) How many ways are there to create an in-class test with at least 1 question about normal distribution?

(d) How many ways are there to create an in-class test with exactly 1 question about normal distribution?

(e) How many ways are there to create an in-class test with questions covering 5 different continuous distributions? (That is, consisting exactly one question about each of the 5 different continuous distributions)

(f) How many ways are there to create an in-class test with questions covering exactly one distribution? (That is, consisting five questions about a single distribution)

Solution

Since the questions in the test are distinct, and the order of question is not important, the process of creating an in-class test is equivalent to placing 5 indistinguishable balls (representing 5 questions in the test) into 74 distinguishable cells (representing the 74 distinct questions in the question bank) with capacity one (since the question in the test cannot repeat).

(a) The number of ways is ${\binom {74}{5}}=16108764$.

(b) With the requirement, we need to place 3 balls into 43 cells for discrete distributions, and place 2 balls into 31 cells for continuous distributions. Hence, the number of ways is ${\binom {43}{3}}\times {\binom {31}{2}}=5738565$.

(c) With the requirement, we need to place 1 ball into 10 cells for normal distributions (10 ways), and place the remaining 4 balls into the remaining 72 cells (one question for normal distribution is included in the test, and it cannot be repeated) (${\binom {72}{4}}$ ways). Thus, the number of ways is $10\times {\binom {72}{4}}=10287900$.

(d) With the requirement, we need to place 1 ball into 10 cells for normal distributions (10 ways), and place the remaining 4 balls into the remaining 63 cells (excluding all questions related to normal distributions) (${\binom {63}{4}}$ ways). So, the number of ways is $10\times {\binom {63}{4}}=5956650$.

(e) We consider the creation of test under this requirement as a 5-step process: placing one ball into (i) 10 cells; (ii) 11 cells; (iii) 3 cells; (iv) 2 cells; (v) 5 cells. Then, the number of ways is $\underbrace {10} _{\text{norm}}\times \underbrace {11} _{\text{exp}}\times \underbrace {3} _{\text{gamma}}\times \underbrace {2} _{\text{beta}}\times \underbrace {5} _{\text{uniform}}=3300$.

(f) To be possible for all the questions in the test covering only a single distribution, there should be at least 5 questions for that distribution in the question bank. So, it is impossible for the hypergeometric distribution, gamma distribution, and beta distribution. The number of ways is given by $$\underbrace {\binom {9}{5}} _{\text{Ber}}+\underbrace {1} _{\text{bin}}+\underbrace {\binom {7}{5}} _{\text{NB}}+\underbrace {\binom {6}{5}} _{\text{geo}}+\underbrace {\binom {13}{5}} _{\text{Pois}}+\underbrace {\binom {10}{5}} _{\text{norm}}+\underbrace {\binom {11}{5}} _{\text{exp}}+\underbrace {1} _{\text{uniform}}=2150.$$

Exercise. Suppose you go eating a lunch buffet at a restaurant. In the restaurant, there are 60 different food items, consisting of

• 7 kinds of salads
• 23 kinds of meat
• 6 kinds of vegetables
• 14 kinds of desserts
• 10 kinds of breads

Suppose there are unlimited number of servings for each kind of food item. Every time you take food items, you need to put them on a plate. Suppose 3-5 food items are to be put on a plate every time.

(a) Show that there are 8257997 ways to put food items on a plate.

(b) A student makes the following argument to count the number of ways to put food items on a plate if the plate consists of at least one serving of meat:

Since the plate consists of at least one serving of meat, one ball is to be placed into 23 cells representing 23 kinds of meats (23 ways). After that, the remaining balls are placed into 60 distinguishable cells representing 60 food items.

We now consider the different cases with different number of food items (putting $k=2,3,{\text{ or }}4$ indistinguishable balls ("plate positions") into 60 cells), and get

• 3 food items: $23\times {}_{60}H_{2}=42090$
• 4 food items: $23\times {}_{60}H_{3}=869860$
• 5 food items: $23\times {}_{60}H_{4}=13700295$

So, the total number of ways is $42090+869860+13700295=14612245$.

Explain why the answer must be wrong, and explain what mistakes are made in the argument. (Hint: to explain why the answer must be wrong, compare the number with the number in (a). The mistakes is about the improper use of multiplication counting principle. You may read the section discussing about the principle to get some ideas.)

Solution

(a)

Proof. We can regard the 60 different food items as 60 distinguishable cells with unlimited capacity, and the "plate positions" as indistinguishable balls. The number of "plate positions" placed into cells depends on how many food items are put on the plate (3,4, or 5). We thus divide the situation into 3 cases.

Case 1: 3 food items (balls). So, we are putting 3 balls into 60 cells. Hence, the number of ways is $_{60}H_{3}=37820$.

For the 4 food items and 5 food items cases, the situation is similar, and the number of ways is $_{60}H_{4}=595665$ and $_{60}H_{5}=7624512$ respectively. It follows that the total number of ways is $37820+595665+7624512=8257997$.

$\Box$

(b) The answer must be wrong since this number is even greater than the number in (a), but there is an additional condition in (b). Through imposing an additional condition, some ways in (a) are not allowed, and there will not be any additional ways. So, the number should be smaller than the number in (a).

The mistakes of the argument is that the "tasks" are indistinguishable when the student use the multiplication counting principle to get the number of food items, which causes multiple decision paths to lead to the same outcome. Let us consider an example in the 3 food items case.

1. First decision path: for the first step, a ball is placed to meat 1, and for the second step, two balls are placed to meat 2,3 respectively.
2. Second decision path: for the first step, a ball is placed to meat 2, and for the second step, two balls are placed to meat 1,3 respectively.

So, the result is three indistinguishable balls into meat 1,2,3 in both decision paths.

But upon using the multiplication counting principle, we are assuming every decision path leads to exactly one outcome, and thus the number obtained by the student is indeed the number of decision paths. But some paths lead to the same result, so this number is not the total number of ways.

Exercise. Suppose you toss a coin 10 times, to get a sequence of outcomes. For example, the sequence HTHHTHTTTT means heads in toss 1,3,4,6 and tails in toss 2,5,7,8,9,10.

(a) How many different sequences are there?

(b) Show that the number of different sequences consisting of exactly five (i.e., not six,seven,etc.) consecutive heads are 64.

Solution

(a) For each of the 10 tosses, there are two outcomes: H or T. So, the number of different sequences is $2^{10}=1024$.

(b)

Proof. To have heads in exactly five consecutive heads, the "HHHHH" needs to be surrounded by "T"(s). There are six cases:

Case 1: H in toss 1,2,3,4,5 (HHHHHT????).

Case 2: H in toss 2,3,4,5,6 (THHHHHT???).

Case 3: H in toss 3,4,5,6,7 (?THHHHHT??).

Case 4: H in toss 4,5,6,7,8 (??THHHHHT?)

Case 5: H in toss 5,6,7,8,9 (???THHHHHT)

Case 6: H in toss 6,7,8,9,10 (????THHHHH)

There are only freedom for the tosses marked "?" in the above cases. For other tosses, the outcomes are fixed. In two of the above cases, there are four "?"s (so the number of sequences is $2^{4}=16$), and for the remaining cases, there are three "?"s (so the number of sequences is $2^{3}=8$). It follows that the number of sequences is $$2\cdot 16+4\cdot 8=64.$$

$\Box$

Exercise. Consider a role-playing game (RPG) where the player needs to create a character at the beginning, and some skill points need to be assigned to the character. Suppose the player is given 10 skill points, and the character has five attributes, as follows:

1. Health
2. Attack
3. Defense
4. Speed
5. Luck

The player can assign 1-5 skill points to each attribute, and we call an assignment of 10 skill points to these five attributes as a build.

(a) Show that the number of different builds is 121. (Hint: consider using generating function.)

(b) How many different builds with 5 skill points assigned to luck are there?

(c) Suppose a build is called attack build if there are at least 3 skill points assigned to each of the attack and speed attributes, and defense build if there are at least 3 skill points assigned to each of the health and defense attributes. How many attack builds are there? How many defense builds are there? Are the number of attack builds and defense builds equal?

(d) Suppose the player can leave some of the 10 skill points unassigned at the stage of character creation, and can assign the skill points later in game. Nevertheless, at least 1 skill point is still needed to assign to every attribute. Show that there are 247 ways of assignment of skill points at the stage of character creation.

Solution

(a)

Proof. We can regard 10 skill points as 10 indistinguishable balls, and five attributes as five distinguishable cells with capacity 5, which must consist of at least one ball each. For convenience, we consider the following generating function: $$G(x)=(x+x^{2}+x^{3}+x^{4}+x^{5})^{5}=\left({\frac {x(1-x^{5})}{1-x}}\right)^{5}=x^{5}(1-x^{5})^{5}(1-x)^{-5}=x^{5}({\color {blue}1}-{\color {red}5}x^{5}+{\text{terms with order higher than }}x^{5})(1-x)^{-5}$$ (The powers of $x$ in different brackets indicate the number of skill points allocated to different attributes.) (Here, we apply the Newton's generalized binomial theorem to $(1-x^{5})^{5}$.) Since the player has only 10 skill points, the number of different builds is the coefficient of $x^{10}$ in $G(x)$.

By Newton's generalized binomial theorem, the coefficient of $x^{0},x^{5}$ in $(1-x)^{-5}$ is ${\binom {-5}{0}}={\color {red}1},-{\binom {-5}{5}}={\color {blue}126}$ respectively. Thus, the number of builds, which is the coefficient of $x^{10}$ in $G(x)$ is $${\color {blue}126\cdot 1}-{\color {red}5\cdot 1}=121.$$

$\Box$

(b) We may again use the generating function approach: $$G(x)=(x+x^{2}+x^{3}+x^{4}+x^{5})^{\color {darkgreen}4}\underbrace {(x^{5})} _{\text{luck}}=x^{4}(1-x^{5})^{4}(1-x)^{-4}x^{5}=x^{9}({\color {blue}1}+{\text{terms with order higher than }}x)(1-x)^{-4}$$ (We write terms with order higher than $x$, since for these terms, after multiplying it by $x^{9}$, the order is at least $x^{11}$, and so we are not interested in them.) By Newton's generalized binomial theorem, the coefficient of $x$ in $(1-x)^{-4}$ is $-{\binom {-4}{1}}=4$. Hence, the number of different builds, which is the coefficient of $x^{10}$ in $G(x)$, is ${\color {blue}4\cdot 1}=4$.

Alternative approach: Alternatively, we can use the following "smarter" approach. Since 5 skill points are to be assigned to luck, and 1 skill point must be assigned to each of health, attack, defense, and speed respectively. So, there are only freedom for the 1 skill point remaining and all other skill points are fixed. The skill point is to be assigned to one of health, attack, defense, and speed (no luck since luck has five (maximum) skill points already). Then, there are four ways of doing that. So, the number of different builds is 4.

(c) By symmetry, the number of attack builds is the same as that of defense builds. (Each kind of builds has essentially the same requirements. The different attributes have no actual difference in nature apart from their names.) So, let us just focus on the attack build. We again consider the generating function approach: $${\begin{aligned}G(x)&=\underbrace {(x^{3}+x^{4}+x^{5})^{2}} _{{\text{atk }}\&{\text{ spd}}}(x+x^{2}+x^{3}+x^{4}+x^{5})^{3}\\&=\left({\frac {x^{3}(1-x^{3})}{1-x}}\right)^{2}\left({\frac {x(1-x^{5})}{1-x}}\right)^{3}\\&=x^{9}(1-x^{3})^{2}(1-x^{5})^{3}(1-x)^{-5}\\&=x^{9}({\color {blue}1}+{\text{terms with order higher than }}x)({\color {blue}1}+{\text{terms with order higher than }}x)(1-x)^{-5}.\\\end{aligned}}$$ By Newton's generalized binomial theorem, the coefficient of $x$ in $(1-x)^{-5}$ is $-{\binom {-5}{1}}=5$. Hence, the number of different builds, which is the coefficient of $x^{10}$ in $G(x)$, is 5.

(d)

Proof. We recall the generating function $G(x)$ in part (a): $$G(x)=x^{5}(1-5x^{5}+{\text{terms with order higher than }}x^{5})(1-x)^{-5}.$$ Since not all ten skill points have to be assigned, but since every attribute must have at least one skill point assigned, there are at least 5 skill points assigned (and at most 10 skill points assigned). Hence, we will consider the number of builds in all possibilities (5,6,7,8,9,10 skill points assigned), and add them up together. The number is given by the sum of the coefficient of $x^{5},x^{6},x^{7},x^{8},x^{9},x^{10}$ in the generating function $G(x)$.

By the Newton's generalized binomial theorem, $$(1-x)^{-5}=(1+5x+15x^{2}+35x^{3}+70x^{4}+126x^{5}+{\text{terms with order higher than }}x^{5}).$$ Thus, the generating function is given by $$G(x)=x^{5}(1-5x^{5}+{\text{terms with order higher than }}x^{5})(1+5x+15x^{2}+35x^{3}+70x^{4}+126x^{5}+{\text{terms with order higher than }}x^{5})$$ Thus, the sum of the coefficients is $$\underbrace {1\cdot 1} _{x^{5}}+\underbrace {1\cdot 5} _{x^{6}}+\underbrace {1\cdot 15} _{x^{7}}+\underbrace {1\cdot 35} _{x^{8}}+\underbrace {1\cdot 70} _{x^{9}}+\underbrace {121} _{x^{10}{\text{ by (a)}}}=247.$$

$\Box$

Exercise. A group of 12 people goes to a teahouse to eat lunch together. They order a number of dim sum dishes (a kind of Chinese dishes), consisting of

• three different dumplings:

• Shrimp dumpling
• Shumai
• Wonton

• three different buns:

• Barbecued pork bun
• Sweet cream bun
• Lotus seed bun

• four different rolls:

• spring roll
• tofu skin roll
• beef rice noodle roll
• shrimp rice noodle roll

A circular table.

Suppose the dim sum dishes are placed in a circular table, in ten places arranged in a circular shape (see diagram below), and the people seat around the table to eat those dishes.

                                  N
        * * *  *                  ^
      *    1     *              W<+>E
    * 10       2  *               v
   *             3 *              S
   * 9              *
   *              4 *
    *  8        5  *
     *    7  6    *
       * * * *  * 
The region bounded by "*" is the circular table, the numbers indicate the ten dishes.

Using the compass directions (N,E,S,W), both the ten places for the dishes, and the 12 seats for the people are distinguishable.

(a) How many different ways are there to arrange the ten dishes in such way?

(b) How many different ways are there to arrange the seating of the 12 people?

(c) Suppose the three dumplings are to be placed together, and the three buns are to be placed together also. But the dumplings and buns are to be separated (i.e., there are not a dumpling and a bun placed next to each other) by the four rolls. Show that there are 25920 ways to arrange the ten dishes under this requirement? (Hint: We illustrate the situation as follows:

                                  N
        * * *  *                  ^
      *    D     *              W<+>E
    * R        D  *               v
   *             D *              S
   * B              *
   *              R *
    *  B        R  *
     *    B  R    *
       * * * *  * 
D: dumpling
B: bun
R: roll
(1 R in the gap "from B to D" (viewed clockwise). The gap "from B to D" is the upper one, and the gap "from D to B" is the lower one.)

There are two more possible "ways" to separate the dumplings and buns apart from the way shown in above. Determine them, and count the number of arrangements in each case. )

Solution

(a) The number of ways is $10!=3628800$. (Place 10 different dishes into 10 distinguishable places)

(b) The number of ways is $12!=479001600$. (Place 12 different people into 12 distinguishable seats)

(c)

Proof. The diagram in the hint shows one way of separating dumplings and buns The following are two more ways:

                                  N
        * * *  *                  ^
      *    R     *              W<+>E
    * R        D  *               v
   *             D *              S
   * B              *
   *              D *
    *  B        R  *
     *    B  R    *
       * * * *  * 
(2 R in the gap "from B to D" (viewed clockwise))

                                  N
        * * *  *                  ^
      *    R     *              W<+>E
    * R        D  *               v
   *             D *              S
   * R              *
   *              D *
    *  B        R  *
     *    B  B    *
       * * * *  * 
(3 R in the gap "from B to D" (viewed clockwise))

Here, we consider the three cases one by one.

Case 1: "1 R" case. We first focus on the particular case illustrated in the diagram. The number of arrangements is $$\underbrace {3!} _{D}\times \underbrace {4!} _{R}\times \underbrace {3!} _{B}=864.$$ But we can rotate the circular table to generate 9 more arrangements for every such arrangement. Thus, the total number is $$10\times 864=8640.$$

For the "2 R" case and "3 R" case, the situation is similar, and hence the total number is also 8640. There are no common ways in these three cases. So, altogether, there are thus $8640\times 3=25920$ arrangments.

$\Box$