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

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

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.

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   people among the 140 people now learn to speak English. Calculate   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 edit

Theorem. (Multiplication counting principle)

 
A tree diagram that illustrates the idea.

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:

  1. "two heads"
  2. "one heads, one tails"
  3. "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?

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


 

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  .

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

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

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)

 
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

 
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.

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

 
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:

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

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

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:

 



Number of ways for placing r balls into n cells edit

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

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

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.

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

 
 

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  .

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.

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)   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"?

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

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.

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

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  .

 

(b)

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  .

 

(c)

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  .

 

(d)

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.

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.

 
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.

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

9
10
11
12
13

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

10
11
12
13
14

4 Suppose Amy and Bob is initially located at   and   respectively. Calculate the number of distinct sequence of steps for Amy such that Amy and Bob meet at  , 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) edit

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:

  1. select 2 to be committees from the 6 men (  ways)
  2. 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:

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

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

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

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

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.

1 Amy, Bob and Chris are among the   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

 

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

(a)

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.

 

(b)

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

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:

  1. Place 0 ball into the   cells (  way)
  2. 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:

  1. Place 1 ball into the   cells (  ways)
  2. 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:

  1. Place   balls into the   cells (  ways)
  2. 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:

  1. Place   balls into the   cells (  ways)
  2. 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

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

Solution

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

1 Suppose a machine can have   password guesses per second. Approximate the maximum time needed for the machine to guess the six-character password correctly using the formula

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

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  .

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

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?

Solution

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:

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

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  

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

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


Solution

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

The number of ways is thus  .

 

(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 (  ways)
  2. 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
(a)

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

 


(b)

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

 


(c)

Proof. Consider two steps:

  1. Left hand wears the rings. (  ways. 4 indistinguishable balls: 4 rings; 5 distinguishable cells with unlimited capacity: 5 fingers)
  2. 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  .

 


(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. (  ways. 7 indistinguishable balls: 7 rings; 8 distinguishable cells with unlimited capacity: 8 fingers)

So, the number of ways is 3432.

 


Summary edit

Placing   balls into   distinguishable cells
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,

Selecting   objects from   distinguishable objects
with replacement without replacement
ordered
 
 
unordered
 
 

Indistinguishable cells edit

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

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

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

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

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.