Readings

• Combinatorics - Brilliant
• Rule of Sum - Brilliant
• Rule of Product - Brilliant
• Permutations - Brilliant
• Combinations - Brilliant
• Ball-and-urn - Art of Problem Solving

Counting Integers in Ranges

$[a, b]$: the number of integers is $b - a + 1$.

• $[1, 10]$: From 1 to 10 inclusive, there are 10 integers.
• $[0, 10]$: From 0 to 10 inclusive, there are 11 integers.
• $[20, 79]$: From 20 to 79 inclusive, there are 60 integers.

$[a, b)$: the number of integers is $b - a$.

• $[0, 10)$: From 0 to 10 exclusive, there are 10 integers.
• $[20, 79)$: From 20 to 79 exclusive, there are 59 integers.

Need to write it down to remember it and avoid the off-by-one error.

Rule of Sum

If there are $n$ ways to do something and $m$ ways to do another, then there are $n + m$ ways to do either one thing or the other.

• If I can only buy a shirt or a pair of pants, and there are 3 ways to choose a shirt and 2 ways to choose a pair of pants, then there are $3 + 2 = 5$ ways to choose either a shirt or a pair of pants.

Intermediate Examples

Example 1

How many outcomes of throwing 6 indistinguishable coins? (Assume HHHHHT and THHHHH are the same)

Method 1: List all possible outcomes.

• There can be 0 heads, 1 head, 2 heads, 3 heads, 4 heads, 5 heads or 6 heads.
• There are 7 outcomes in total.

Method 2: Let's Head be 1 and Tail be 0.

• The largest sum of 6 coins is 6 (HHHHHH).
• The smallest sum of 6 coins is 0 (TTTTTT).
• There are 7 possible integers between 0 and 6 inclusive.

Example 2

How many unique sums from throwing 6 dice?

• The largest sum of 6 dice is 36 (666666).
• The smallest sum of 6 dice is 6 (111111).
• There are 31 possible integers between 6 and 36 inclusive.

Rule of Product

If there are $n$ ways to do something and $m$ ways to do another, then there are $n \times m$ ways to do both things.

• If there are 3 ways to choose a shirt and 2 ways to choose a pair of pants, then there are $3 \times 2 = 6$ ways to choose a shirt and a pair of pants.
• If there are 3 colors, 2 sizes and 5 variants, then there are $3 \times 2 \times 5 = 30$ ways to choose a shirt.

Intermediate Examples

Example 1

We can take either buses or trains to travel between two cities. There are 2 trains and 3 buses between city A and B and 4 trains and 5 buses between city B and C. How many ways are there to travel from city A to C?

• There are $2 + 3 = 5$ ways from A to B. (Sum: We only take either 1 train or 1 bus from A to B)
• There are $4 + 5 = 9$ ways from B to C. (Sum: We only take either 1 train or 1 bus from B to C)
• There are $5 \times 9 = 45$ ways from A to C. (Product: We need to travel between both A to B and B to C)

Example 2

How many ways to place 6 people in 3 seats?

• First seat: 6 ways to choose a person. (Sum: We only take either 1 person from 6 people)
• Second seat: 5 ways to choose a person. (Sum: We only take either 1 person from 5 people)
• Third seat: 4 ways to choose a person. (Sum: We only take either 1 person from 4 people)
• Total: $6 \times 5 \times 4 = 120$ ways. (Product: We need to fill all 3 seats)
• This also is the permutation of taking 3 people from 6 people: $P_3^6 = 6 \times 5 \times 4 = 120$.

Permutations

A Permutation is an arrangement of objects in a specific order. The number of permutations of $n$ objects is $n!$.

• There are n positions to fill and n objects to choose.
• The first position can be filled with the $(n)$ objects.
• The second position can be filled with the remaining $(n - 1)$ objects.
• ...
• The last position can be filled with the remaining $1$ object.
• Total there are $n!$ ways: $n \times (n - 1) \times (n - 2) \times ... \times 1$

Example 1

How many ways to place 4 men and 4 women at a circular table so that no two women are adjacent?

• No two women are adjacent -> men can only be placed between two women.
• There are 3 gaps between 4 women -> there are $3!$ ways to place 4 men.
• There number of permutations of placing 4 women is $4!$.
• Total there are $3! \times 4! = 144$ ways.

Example 2

How many 5-digit numbers can be formed from ${0, 2, 4, 6, 8}$?

• The total number of permutations is $5! = 120$.
• However, $4!$ permutations start with 0.
• Total there are $5! - 4! = 96$ ways.

Perumutations of a Subset of Distinct Objects

The number of permutations of $k$ objects chosen from $n$ distinct objects is $P_k^n = \frac{n!}{(n - k)!}$.

Example 1

How many 3-digit numbers can be formed from 10 digits ranging from [0, 9]?

Method 1:

• The total number of permutations is $P_3^{10} = \frac{10!}{(10 - 3)!} = \frac{10!}{7!} = 720$.
• But there are $P_2^{9} = \frac{9!}{(9 - 2)!} = \frac{9!}{7!} = 72$ permutations starting with 0. (The first digit is fixed to 0, and the remaining 2 digits can be chosen from 9 digits.)
• There are $720 - 72 = 648$ ways.

Method 2:

• The first digit can be chosen from 9 digits (1 to 9).
• The second digit can be chosen from 9 digits [0, 9], excluding the first digit.
• The third digit can be chosen from 8 digits [0, 9], excluding the first and second digits.
• Total there are $9 \times 9 \times 8 = 648$ ways.

Example 2

How many 4-letter passwords can be formed from 26 uppercase letters, 26 lowercase letters, and 10 digits?

• The total number of permutations is $P_4^{62} = \frac{62!}{(62 - 4)!} = \frac{62!}{58!} = 13388280$.

Example 3

If there are 25 stations on a train line, how many types of tickets (between any stations) can be sold?

• We are choosing 2 stations from 25 stations for each ticket type.
• The total number of permutations is $P_2^{25} = \frac{25!}{(25 - 2)!} = \frac{25!}{23!} = 600$.

Permutations of Objects with Repetition (Partially indistinguishable)

Given $n$ objects, where $n_1$ are of one type, $n_2$ are of another type, ..., $n_k$ are of another type, the number of permutations is $\frac{n!}{n_1! \times n_2! \times ... \times n_k!}$.

• When each type of object only has 1 object (All are distinct), the number of permutations is $n!$.
• When all objects are of the same type (All are indistinguishable), the number of permutations is $1$.

Example 1

If there are 2 indistinguishable cats, 3 indistinguishable dogs, 1 rabbit, 1 penguin, and 1 koala, how many ways to arrange them in a line?

• The total number of permutations is $\frac{8!}{2! \times 3!} = 3360$.

Example 2

How many ways can the letter RAMONA be arranged?

• There are 6 letters in total, but 2 A's.
• The total number of permutations is $\frac{6!}{2!} = 360$.

Example 3

How many ways to arrange 2 deck of indistinguishable cards?

• There are totally $52 \times 2 = 104$ cards.
• Each unique card has 2 copies.
• There are in total $\frac{104!}{2! \times 2! \times ... \times 2!} = \frac{104!}{2^{52}}$ ways.

Example 4

How many ways to arrange BANANA such that no two N's are adjacent?

• There are 6 letters in total, but 3 A's and 2 N's. The total number of permutations without the restriction is $\frac{6!}{3! \times 2!} = 60$.
• Let's consider NN is a single letter. We have 5 letters in total, but 3 A's. The total number of permutations given we have NN is $\frac{5!}{3!} = 20$.
• There are in total $60 - 20 = 40$ ways.

Remark: It is not easy to compute the number of permutations of a subset of objects with repetition: https://math.stackexchange.com/questions/2372/how-to-find-the-number-of-k-permutations-of-n-objects-with-x-types-and-r

Combinations

Here, we want to choose k objects from n objects, ignoring the order.

• The number of permutations of selecting k objects from n objects is $P_k^n = \frac{n!}{(n - k)!}$.
• Each group of selected k objects gives $P_k^k = k!$ permutations.
• Therefore, the number of combinations is $C_k^n = \frac{P_k^n}{k!} = \frac{n!}{k! \times (n - k)!}$.

Example 1

How many ways are there to select 3 males and 2 females out of 7 males and 5 females?

• Choosing 3 males from 7 males and choosing 2 females from 5 females: $C_3^7 \times C_2^5 = 350$.

Example 2

How many ways to form 3 groups of 2, 3 and 4 people from 9 people?

• Select 2 people from 9 people: $C_2^9 = 36$.
• And, Select 3 people from remaining 7 people: $C_3^7 = 35$.
• And, Select 4 people from remaining 4 people: $C_4^4 = 1$.
• Total there are $36 \times 35 \times 1 = 1260$ ways.

Example 3

At a party, everyone shakes hands with everyone else. If there are 66 handshakes in total, how many people are there?

• Each person shakes hands with everyone else except himself/herself.
• Solving the number of 2-combinations from n people = 66
• $n = 12$

Example 4

How can you arrange 3 chocolates and 10 candies in a line?

Method 1: Permutation with repetition

• There are 13 objects in total, but 3 are of one type and 10 are of another type.
• The total number of permutations is $\frac{13!}{3! \times 10!} = 286$.

Method 2: Combinations

• Let's consider the problem as choosing 3 indices from {1, 2, ..., 13} to be the chocolate positions.
• We need to choose 3 positions from 13 positions to be the chocolate position.
• The total number of combinations is $C_3^{13} = \frac{13!}{3! \times (13 - 3)!} = 286$.

Example 5

Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?

• Ignoring the order, let's select 3 consonants from 7 consonants and 2 vowels from 4 vowels.
• There are $C_3^7 \times C_2^4 = 210$ groups of unique 3-consonants and 2-vowels.
• Now we have 5 letters for each group, there are $5!$ permutations for each group.
• The total number of permutations is $210 \times 5! = 25200$.

Ball-and-Urn Model

How many ways can $k$ indistinguishable balls be distributed into $n$ distinguishable urns?

• We can translate the problem into: How do we set up $n-1$ indistinguishable dividers between $k$ indistinguishable balls?
• The order of the balls and dividers defines the distribution among distinct urns.
• There are $k$ balls and $n-1$ dividers. There are $k + n - 1$ objects.
• To arrange these objects, there are $\frac{(k + n - 1)!}{k! \times (n - 1)!}$ ways.
• Which equals to $C_{n - 1}^{k + n - 1}$.

Example 1

How many ways do you distribute 7 cookies to 4 people, so each person gets at least 1 cookie?

Method 1: Ball-and-urn model

• If we distribute 1 cookie to each person, we have 3 cookies left.
• k=3, n=4, there are $C_{4-1}^{3+4-1} = C_3^6 = 20$ ways.

Method 2: Translate to a dividing problem

• If we distribute 1 cookie to each person, we have 3 cookies left.
• We need to set up 3 dividers between 3 cookies, there are 6 objects in total.
• By permutations with repetition: There are $6! / (3! \times 3!) = 20$ ways.