Counting lots of things!
A Math Circle session by Aditya and Nart
Permutations
Number of ways to pick teams with numbering
Permutations
How many ways can Alice color her cake?
How many ways can Alice color her cake?
First layer is Red:
Second layer is Blue:
Third layer is Green:
Second layer is Green:
Third layer is Blue:
How many ways can Alice color her cake?
First layer is Red:
First layer is Blue:
Second layer is Blue:
Third layer is Green:
Second layer is Green:
Third layer is Blue:
Second layer is Red:
Third layer is Green:
Second layer is Green:
Third layer is Red:
How many ways can Alice color her cake?
First layer is Red:
First layer is Blue:
First layer is Green:
Second layer is Blue:
Third layer is Green:
Second layer is Green:
Third layer is Blue:
Second layer is Red:
Third layer is Green:
Second layer is Green:
Third layer is Red:
Second layer is Red:
Third layer is Blue:
Second layer is Blue:
Third layer is Red:
How many ways can Alice color her cake?
First layer is Red:
First layer is Blue:
First layer is Green:
Second layer is Blue:
Third layer is Green:
Second layer is Green:
Third layer is Blue:
Second layer is Red:
Third layer is Green:
Second layer is Green:
Third layer is Red:
Second layer is Red:
Third layer is Blue:
Second layer is Blue:
Third layer is Red:
2
2
2
+
+
Permutations
Note that Alice has two options once she colors the first layer. Hence, Alice can color
Color choices for the first layer
Permutations
Note that Alice has two options once she colors the first layer. Hence, Alice can color
Color choices for the first layer
Color choices for the second layer
Permutations
Note that Alice has two options once she colors the first layer. Hence, Alice can color
Color choices for the first layer
Color choices for the second layer
Color choices for the third layer
Factorial
We call this number the factorial of 3. We write this as 3!
6 = 3 x 2 x 1
So, 4! = 4 x 3 x 2 x 1 = 24
And 5! = 5 x 4 x 3 x 2 x 1=
Factorial
We call this number the factorial of 3. We write this as 3!
6 = 3 x 2 x 1
So, 4! = 4 x 3 x 2 x 1 = 24
And 5! = 5 x 4 x 3 x 2 x 1= 120
What if we had more colors?
We had three colors and three layers. What happens if these numbers don't match?
Say we started with 5 colors: Red, Blue, Green, Orange and Purple, and we have to color three layers.
What if we had more colors?
Say we started with 5 colors: Red, Blue, Green, Orange and Purple, and we have to color three layers.
Color choices for the first layer
Color choices for the second layer
Color choices for the third layer
5 x 4 x 3
What if we had more colors?
Say we started with 5 colors: Red, Blue, Green, Orange and Purple, and we have to color three layers.
Color choices for the first layer
Color choices for the second layer
Color choices for the third layer
5 x 4 x 3 = 60
Let us now make teams and play rock, paper and scissors!
We will pick out names and form teams.
Combinations
Number of ways to pick teams without numbering
Combinations
We will pick teams now but everyone is allowed to work together.
It doesn't matter who gets chosen at what point, the team remains the same.
Combinations
Examples:
Let us think of more examples!
Combinations
How to count number of combinations? Suppose, we want to pick 3 donuts out of 10 possible flavors.
Combinations
How to count number of combinations? Suppose, we want to pick 3 donuts out of 9 possible flavors.
There are 9 ways to pick the first one, 8 ways to pick the second, and 7 ways to pick the third.
Combinations
But all these 6 ways are now the same
A
B
C
A
C
B
B
A
C
B
C
A
C
A
B
C
B
A
Combinations
So we get 9 x 8 x 7 divided by 6 which is 84 ways.
A
B
C
A
C
B
B
A
C
B
C
A
C
A
B
C
B
A
Combinations
A
B
C
A
C
B
B
A
C
B
C
A
C
A
B
C
B
A
Where does the number 6 come from here?
Combinations
A
B
C
A
C
B
B
A
C
B
C
A
C
A
B
C
B
A
Where does the number 6 come from here?
It is 3! because we have 3 things being shuffled
Combinations
A
B
C
A
C
B
B
A
C
B
C
A
C
A
B
C
B
A
So, the total number of ways are given by
9 x 8 x 7 / 6 = 84
Pigeonhole Principle
Pigeonhole Principle
Pigeonhole Principle
Pigeonhole Principle
Pigeonhole Principle
The Pigeonhole principle
The Pigeonhole principle
Wonders in Wonderland
People in Wonderland speak English and the population of Wonderland is 700 people.
Wonders in Wonderland
People in Wonderland speak English and the population of Wonderland is 700 people.
Are there two people with the same first and last initial?
How many potential First and Last initials are there?
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
….
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
….
People:
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
….
People:
1 2 3 4 5 6 7 8 699 700
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
….
….
People:
1 2 3 4 5 6 7 8 699 700
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
….
….
Initials:
People:
1 2 3 4 5 6 7 8 699 700
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
AA
AB
AC
AD
AE
AF
AG
ZY
ZZ
….
….
Initials:
People:
1 2 3 4 5 6 7 8 699 700
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
AA
AB
AC
AD
AE
AF
AG
ZY
ZZ
….
….
Initials:
People:
1 2 3 4 5 6 7 8 699 700
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
AA
AB
AC
AD
AE
AF
AG
ZY
ZZ
….
….
Initials:
People:
1 2 3 4 5 6 7 8 699 700
How many potential First and Last initials are there?
Choices for first initial
Choices for last initial
What’s the number of my Pigeons and what’s the number of my holes?
AA
AB
AC
AD
AE
AF
AG
ZY
ZZ
….
….
Initials:
People:
1 2 3 4 5 6 7 8 699 700
By the Pigeonhole principle we conclude there are at least two people with the same first and last initials!
Let’s look at some scenarios
Are there two people with the same number of hairs on their head?
Let’s look at some scenarios
Are there two people with the same number of hairs on their head?
What is the average number of hairs on a person's head?
Let’s look at some scenarios
Are there two people with the same number of hairs on their head?
What is the average number of hairs on a person's head?
It is about 100,000
Let’s look at some scenarios
Are there two people with the same number of hairs on their head?
What is the average number of hairs on a person's head?
It is about 100,000
How many people are there in the world?
Let’s look at some scenarios
Are there two people with the same number of hairs on their head?
What is the average number of hairs on a person's head?
It is about 100,000
How many people are there in the world?
About 8 billion which is 8,000,000,000
Let’s look at some scenarios
Are there two people with the same number of hairs on their head?
8 billion is bigger than 100,000, so by pigeonhole principle, there are two people with the same number of hairs.
Chess Cheeseboard
Mouse moving on a cheese-board
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
Can the mouse get here
in exactly 25 moves?
It can only move
up, down, left, right but NOT diagonally