# 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

[edit | edit source]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

[edit | edit source] **Proposition.**
(Addition counting principle)
If there are ways to do task 1 and ways to do task 2, *but* we cannot do both tasks together, then we have ways to do task 1 or task 2.

**Remark.**

- In set theoretic terms, this means if and are disjoint finite sets (containing the ways to do task 1 and 2 respectively), then .

More generally, we have the *subtraction* counting principle:

**Proposition.**
(Subtraction counting principle)
If there are ways to do task 1 and ways to do task 2, *and* there are ways to do both tasks together,
then we have ways to do task 1 or task 2.

**Remark.**

- An interpretation: since
*includes*too many ways (some are double counted), we need to*exclude*the double counted ways ( of them). - Setting gives the addition principle of counting.
- In set theoretic terms, this means if and are finite sets (containing the ways to do task 1 and 2 respectively), then .
- 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 be a positive integer, and be finite sets.
Then, the cardinality of their union is

**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 contains the ways to do task 1,2,...,. Then, the union contains the ways to do task 1,2,... or .

**Example.**
(Special cases of inclusion-exclusion principle)
When , the inclusion-exclusion principle gives
When , the inclusion-exclusion principle gives

**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 , , be the set containing the people speaking English, French and German respectively.
Then, by inclusion-exclusion principle,
Hence, the number of people that speak English, French and German is .

**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.**

### Multiplication counting principle

[edit | edit source] **Theorem.**
(Multiplication counting principle)

Let be a positive integer. If there are ways to do the task respectively, then there are ways to do the tasks.

**Proof.**
We prove it by mathematical induction. Let be the statement

- "If there are ways to do the task respectively, then there are ways to do the tasks."

**Basis Step**: Assume there is ways to do the task 1. Then clearly there is ways to do this one task. So, is clearly true.

**Inductive Hypothesis**: Let be an arbitrary positive integer. Assume that is true. That is, assume that

- "If there are ways to do the task respectively, then there are ways to do the tasks."

is true.

**Inductive Step**:
We want to show that is true.
So, we now assume that there are ways to do the task respectively.
By the inductive hypothesis, there are ways to do the first tasks (task ).
Now, for *each* of the ways of doing the first tasks, there are ways to do the task .
Expressing it using a table, we have
Hence, the number of ways of doing the tasks (the first tasks, and the task ) is
So, is true.

Thus, by the principle of mathematical induction, is true for every positive integer .

**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 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:

- "two heads"
- "one heads, one tails"
- "two tails",

instead of 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?

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:

- 2 Red
- 1 Red 1 Blue
- 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 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.

The number of ways is .

**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:

- mixing A and B
- mixing B and C
- 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?

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 .

**Example.**
(Number of elements in a power set)
The number of elements in a power set of set with elements is .

**Proof.**
Consider the elements in one by one.
For each of them, we can either *include* or *do not include* it in a subset of .
Then, there are steps involved to construct a subset of , and each step has two outcomes.
It follows from the multiplication counting principle that the steps have outcomes.
That is, there are possible (distinct) subsets of .
Since power set contains all subsets of by definition, it follows that the power set has elements.

**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 .

**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 .

**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.**
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 to denote number and facing up in original red and blue dice respectively, we have
In total, there are pairs removed, so the desired number is .

### Division counting principle

[edit | edit source] **Theorem.**
(Division counting principle)
There are ways to do a task if it can be done using a *procedure* that can be carried out in ways, and for every way for doing the *task*, exactly of the ways in the *procedure* correspond to the way . ( is a positive integer.)

Graphically, it looks like

**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 .
(Here, the "task" may be interpreted as choosing a cow, and the "procedure" may be interpreted as choosing a leg. Then, 4 ways of choosing a leg correspond to 1 way of choosing a cow.)

**Example.**
(Arranging seats in a circular table)

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

1 4 4 2 3 1 3 2

But the following two seatings are *not* considered the same:

1 4 4 2 1 3 3 2

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

*Solution*.

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

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

The number of ways is given by
**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

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

**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
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

**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:

- Point guard
- Shooting guard
- Small forward
- Power forward
- 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 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

**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.**
**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:

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

So, the number of arrangements for *each* of the teams is .
Then, arranging the two teams is a two-step process:

- Arrange one of the teams (120 ways)
- Arrange another team (120 ways)

So, there are in total ways for the arrangement, which includes the given way.

Hence, this means given a way in the procedure, we can generate 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

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 animals in the cage.
- Student B: Since every chicken has two feet, there are 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 .

**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?

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:

## Number of ways for placing *r* balls into *n* cells

[edit | edit source]In this section, we will discuss how to count the number of ways for placing balls into 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 balls into cells" (for some and ):

- 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!) - 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.) - Classification of 1000 people into ages 0-10, 11-20, ..., 91-100, 101 or above: placing 1000 "people" (balls) into 11 "age groups" (cells).
- Elevator with 20 passengers and stopping at 10 floors: placing 20 "passengers" (balls) into 10 "floors" (cells).
- 3 pigeons flying into 2 pigeonholes: placing 3 "pigeons" (balls) into 2 "pigeonholes" (cells).
- Rolling 10 dice: placing 10 "dice" (balls) into 6 "outcomes" (cells).
- Drawing 3 cards from a poker deck: placing 3 "draws" (balls) into 52 "cards" (cells).
- Tossing 2 coins: placing 2 "coin tosses" (balls) into 2 "outcomes" (cells).
- 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 be a nonnegative integer. The *factorial* of , denoted by , is

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

[edit | edit source]Let us first discuss ordered selection of objects from objects without replacement. We can regard this to be abstractly equivalent to placing distinguishable balls (choice 1,2,...,) into distinguishable cells (object 1,2,...,) 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 distinguishable balls into distinguishable cells with capacity one is .

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

- for the 1st ball, there are vacant cells left. So, there are ways of placing the ball into a cell.
- for the 2nd ball, there are vacant cells left. So, there are ways of placing the ball into a cell.
- ...
- for the th ball, there are vacant cells left. So, there are ways of placing the ball into a cell.

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

**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

**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

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

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

**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.)

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 .

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

**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

(b) The number is

**Exercise.**

**Example.**
Show that the number of ways of *ordering* (or *permutating*) distinguishable objects is .

**Proof.**
Ordering distinguishable objects is the same as putting the distinguishable objects (balls) into 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 .

**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 ways for the "procedure".
But the two "P"s are actually indistinguishable, so some ways in the 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":
which is what we want.

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

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 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 such orderings, and hence 12 ways in the procedure corresponding to a given string.
It follows that the number of ways is

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

### Partition

[edit | edit source]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 distinguishable objects into groups, where group 1,2,..., must contain 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 distinguishable balls into cell 1,2,...,, where cell 1,2,..., must contain balls respectively".

**Theorem.**
The number of ways for placing distinguishable balls into cell 1,2,...,,
where cell 1,2,..., must contain balls respectively, is .

**Proof.**
First, we consider a procedure where we regard cell 1,2,..., contains *ordered positions* for placing one ball each (e.g., there are "subcells" in cell 1,2,...,).
In this case, we can just regard the placement as a permutation of the distinguishable balls, since the cells altogether contain "ordered positions" ("subcells").
After having such consideration, the number of ways of placement is .

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 ways to permutate the distinguishable balls in the subcells of cell 1,2,..., respectively, so there are altogether ways in the procedure that correspond to one way in the "task". Hence, by the division counting principle, there are ways for the partition.

**Remark.**

- is called the
*multinomial coefficient*.

**Exercise.**

**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 (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 (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 .

Now, we consider the number of ordering *without* any restrictions.
The number is given by .
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 .

**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 .

(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 .

(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 .

(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 .

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 .

**Proof.**
We first consider the 48 cards in the deck without ace. There are 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 .
It follows that the number is .

**Proof.**
We first consider the 48 cards in the deck without ace. There are 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 .

**Proof.**
We first consider the 39 cards in the deck, with a certain kind of cards removed. There are 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 .

**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
.

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.

**Exercise.**

**Example.**
(Walking path)
Consider the following diagram.
Suppose we are initially located at , 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 to is 15.

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

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

Hence, the desired number is

**Exercise.**

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)

[edit | edit source]Previously, we have discussed placing *distinguishable* balls into distinguishable cells with capacity one.
Now, we will consider the case where the 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 balls represent the choices, and every cell can still contain at most one ball).
However, in this case, the balls (choices) are indistinguishable. So, we only know that which of the 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 ( of them), they are put into the group "selected" (they are selected to place one ball).
- For the cells with zero ball ( 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 distinguishable cells into two groups with distinguishable cells and distinguishable cells respectively. With such consideration, the following result is transparent:

**Theorem.**
The number of ways for placing indistinguishable balls into distinguishable cells with capacity one is
.

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 ways for placing distinguishable balls into 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 placements (obtained by permutating the distinguishable balls) where the balls are distinguishable.
It follows that the desired number of ways is

**Remark.**

- is called the
*binomial coefficient*. It can also be denoted by . - 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 .

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

- select 2 to be committees from the 6 men ( ways)
- select 2 to be committees from the 4 women ( ways)

By the multiplication counting principle, the number of ways is .

(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:

- select 1 to be leader from 6 men (6 ways)
- select 1 to be member from 5 men (5 ways) (the leader cannot be member concurrently)
- select 2 to be members from 4 women ( ways)

By multiplication counting principle, there are 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:

- select 1 to be leader from 4 women (4 ways)
- select 1 to be member from 3 women (3 ways)
- select 2 to be members from 6 men ( ways)

Then, by multiplication counting principle, there are 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 .

**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.

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:

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

By multiplication counting principle, there are 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:

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

Then, by multiplication counting principle, there are 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 .

**Example.**

Consider the set . 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 subsets.

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

(a) .

(b) .

(c) .

(d) .

List of subsets:

- set has 0 element. It is the empty set: .
- sets have 1 element. They are ,,and .
- sets have 2 elements. They are ,,and .
- set has 3 elements. It is the set itself: .

There are altogether 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

**Exercise.**

**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

**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:

- (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 . - (one gold Mega ball) There are 46 ways to draw one from the 46 gold Mega balls.

Hence, the number of outcomes is .

**Example.**
(Proving an identity combinatorially)
Let and be nonnegative integers such that .
Prove that

(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.

**Proof.**
Consider the situation where indistinguishable balls are placed into distinguishable cells with capacity one.
By the previous theorem, the number of ways is .

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 balls remaining, and cells remaining. So, the number of ways of placing the remaining balls into the remaining cells is .
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 .

**Case 2**: cell 1 contains zero ball. Then, there are balls remaining, and cells remaining.
So, the number of ways is similarly .

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 corresponding to the expressions in RHS.

**Proof.**
Consider the RHS. We have
establishing the desired identity.

**Remark.**

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

**Example.**
Let and be nonnegative integers such that . Prove that
combinatorially.

**Proof.**
Consider the situation where there are people, and we select 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 .

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

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.

**Exercise.**
Let and be nonngative integers such that and .
Prove the *Vandermonde's identity*, that is,
combinatorially.

**Proof.**
Consider the situation where indistinguishable balls are placed into distinguishable cells with capacity one.
By the previous theorem, the number of ways for doing that is .

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

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

- Place 0 ball into the cells ( way)
- Place balls into the other cells ( ways)

Hence, the number of ways in this case is .

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

- Place 1 ball into the cells ( ways)
- Place balls into the other cells ( ways)

Hence, the number of ways in this case is .

...

**Case **: balls are placed into the cells.
We consider the placement as a two-step process:

- Place balls into the cells ( ways)
- Place balls into the other cells ( ways)

Hence, the number of ways in this case is .

...

**Case **: balls are placed into the cells.
We consider the placement as a two-step process:

- Place balls into the cells ( ways)
- Place balls into the other cells ( way)

Hence, the number of ways in this case is .

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

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

[edit | edit source]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 distinguishable balls into distinguishable cells with unlimited capacity.
This is equivalent to ordered selection of objects from distinguishable objects with replacement,
by regarding the ball 1,2,..., as choice 1,2,...,,
cell 1,2,..., as object 1,2,...,.
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 distinguishable balls into distinguishable cells with unlimited capacity is .

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

- Step 1: choose one of the cells to place ball 1. ( ways)
- Step 2: choose one of the cells to place ball 2. ( ways)
- ...
- Step : choose one of the cells to place ball . ( ways)

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

**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 tasks is the same ( 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 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 .

**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.)

(a) The number of possibilities is . (For every draw, there are four choices of aces.)

(b) The number of possibilities is . (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 . (For the first draw, there are 52 choices, and for each of the remaining draws, there is only 1 choice, which is the card drawn in the first draw.)

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

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

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

**Proof.**
For each of the 6 positions available for the password, there are 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

**Exercise.**

**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 (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 .

**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.)

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 .

This means the number of sequences where *at least two* people in the class have the same birthday is .
Hence, the proportion is .

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

[edit | edit source]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 indistinguishable balls into distinguishable cells with capacity one ("task").
In that previous situation, we know that every way in the task corresponds to ways in the procedure (where we are placing distinguishable balls), by considering the number of ways of permutating the 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 balls in one cell) to (one ball each for the 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 indistinguishable balls into distinguishable cells with unlimited capacity is
.

**Proof.**
To prove this, we introduce the stars and bars notation, to represent the placement of balls into cells. In particular,
(identical) stars are used to represent the indistinguishable balls, and (ordered) spaces created by bars are used to represent the 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 indistinguishable balls into 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 indistinguishable balls into distinguishable cells.
So, that number of ways of the arrangement is exactly the number of ways for such placement of balls into cells.

The bars and stars can be arbitrarily arranged, to represent different placements. Altogether, there are (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 positions from these 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 . Once we place the stars, there is only 1 way to place the bars: place them into the remaining positions.

It then follows that there are ways to arrange the bars and stars, and hence the result follows.

**Remark.**

- can be greater than .

**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 .

**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 .

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

This time, we have 3 indistinguishable balls and also 6 distinguishable cells. Hence, the number of outcomes is .

**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 .

(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 .

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

- 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)
- Then, we place the remaining 3 indistinguishable balls into the other 5 distinguishable cells (unlimited capacity), representing the 5 food items. ( ways)

It follows that the number of combos is .

**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.

(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

(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 .

**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:

- 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) - 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:

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

Hence, there are 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

**Example.**
(Number of integer solutions of a equation)
Consider the equation
(a) How many solutions to the equation are there, where are nonegative integers?

(b) How many solutions to the equation are there, where are positive integers?

(c) Show that there are 11440 solutions to the inequality where are nonnegative integers.

*Solution*.

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

(b) Let . Then, are nonnegative integers. Then, we have It follows that the number of solutions is .

(c) One may count the number of solutions by considering all the 10 possible cases: . 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 to the LHS, which results in an equation:
where is a *positive integer*.
This equation is equivalent to the inequality, since
So, the get the number of solutions to this equation, we consider the situation as the following:

- 10 indistinguishable balls
- 8 distinguishable cells representing , where each of the cells contains zero or more balls, while the cell contains one or more balls.

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

Thus, the number of solutions is

**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).

We can regard the 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
for every positive integer and nonnegative integer . Also, are nonnegative.
In particular, the summation notation means that the sum is taken over all nonnegative integer vectors (i.e., lists of numbers) such that .
For example,
Show that there are terms in the expansion by the multinomial theorem.

**Proof.**
Notice that every term in the expansion corresponds to a nonnegative integer vector .
So, the number of terms in the expansion is exactly the number of nonnegative integer vectors , satisfying the condition that ,
that is, the number of solutions to the equation where are nonnegative integers.

To get this number, we regard the situation as placing indistinguishable balls into distinguishable cells, with unlimited capacity, representing respectively. By previous result, the number is .

**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

**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 .

(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 .

**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.**
We consider the division as a two-step process:

- Choose the three team leads for team A,B,C respectively from the 120 identical robots (one way).
- 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. ( ways)

The number of ways is thus .

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

- Choose the three team leads for team A,B,C respectively from the 20 people ( ways)
- For each of the 17 people remaining, they can be assigned to one of the three teams. ( ways)

So, the number of ways is .

**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.**
The number of ways is . (9 indistinguishable balls: 9 rings; 5 distinguishable cells with unlimited capacity: 5 fingers)

**Proof.**
The number of ways is . (9 indistinguishable balls: 9 rings; 10 distinguishable cells with unlimited capacity: 10 fingers)

**Proof.**
Consider two steps:

- Left hand wears the rings. ( ways. 4 indistinguishable balls: 4 rings; 5 distinguishable cells with unlimited capacity: 5 fingers)
- Right hand wears the rings. ( ways. 5 indistinguishable balls: 5 rings; 5 distinguishable cells with unlimited capacity: 5 fingers

So, the number of ways is .

**Proof.**
Consider two steps:

- Each of two ring fingers wear one ring. (1 way)
- The remaining eight fingers wear seven remaining rings. ( ways. 7 indistinguishable balls: 7 rings; 8 distinguishable cells with unlimited capacity: 8 fingers)

So, the number of ways is 3432.

### Summary

[edit | edit source]cells with capacity one | cells with unlimited capacity | |
---|---|---|

distinguishable balls | ||

indistinguishable balls |

**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,

with replacement | without replacement | |
---|---|---|

ordered | ||

unordered |

### Indistinguishable cells

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

When we encounter indistinguishable cells, we may need to consider the ways one by one.

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

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

So, there are 14 ways.

## A powerful tool for counting problems: generating functions

[edit | edit source] **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 is given by

**Remark.**

- The coefficient of , i.e., , can be obtained by where denotes the th derivative of the function at .
- 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 be a *real number*. Then,
where , and 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 at zero. That is, if we let , then the series is given by

- where is the th derivative of function at , and the condition 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 .

The following are some special cases of this theorem:

- (geometric series) : a generating function of the sequence 1,-1,1,-1,...;
- (geometric series) : a generating function of the sequence 1,1,1,1,...;
- (negative binomial series) : a generating function of the sequence ;
- (binomial series) : a generating function of the sequence ; ( is nonnegative integer)
- (binomial theorem) . (We get this from noticing that , and applying the theorem to in RHS.)

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

**Example.**
Show that the number of ways for placing indistinguishable balls into distinguishable cells with unlimited capacity is .

**Proof.**
We encode the brackets as cells. If we choose "1" in the bracket, then the cell has zero ball, if we choose "" in the bracket, then the cell has one ball, if we choose "" in the bracket, then the cell has two balls, etc.
Then, the desired number is the coefficient of (number of ways to "build" , through multiplying some powers of in different brackets (the powers are obtained by some balls in some cells)) in the generating function
This is the negative binomial series. So, the coefficient of is

**Example.**
Show that the number of ways for placing distinguishable balls into cell 1,2,...,,
where cell 1,2,..., must contain balls respectively, is ,
using the notion of generating function.

**Proof.**
We encode the brackets as cells. If are chosen, then we put a ball into the cell 1,2,...,.
Since we want cell 1,2,..., contains exactly balls, we are interested in the coefficient of , i.e., the number of ways to multiply different "" in different brackets together to create the product , in
which is , by *multinomial theorem*.

**Example.**
Calculate the number of solutions to the equation where are positive, , and .

*Solution*.
Consider the generating function
(Powers of in different brackets indicate the intger chosen for different unknown )

By Newton's generalized binomial theorem, the coefficient of in is respectively. This means the coefficient of in is . Hence, the number of solutions is 9316.

**Remark.**

- One can also notice that is a negative binomial series, and proceed to use, e.g., to get the coefficient of in .

**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
(The powers of in different brackets indicate the number of different fruits bought.)
By Newton's generalized binomial theorem, the coefficients of in is
respectively.
Thus, the desired number of ways is the coefficient of in , which is

**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
(The powers of 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 in .
Now, let us find these coefficients one by one.

**Coefficient of **:

By Newton's generalized binomial theorem, the coefficient of in is Thus, the coefficient of is 56.

**Coefficient of **:

By Newton's generalized binomial theorem, the coefficient of in is respectively. Hence, the coefficient of is

It follows the number of outcomes is .

**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: