Transcript Document

Combinatorics - the art of counting
A
B
C
There are 3 different routes to go from A to B.
There are 2 different routes to go from B to C.
How many different routes are there to go from A to C?
Answer is 6
A
m
B
n
C
There are m different routes to go from A to B.
There are n different routes to go from B to C.
How many different routes are there to go from A to C?
Answer is m*n
3 5 8
How many 3-digit numbers can be formed
arranging the digits “3”, “5” and “8”?
1. 358
2. 385
3. 538
4. 583
5. 835
6. 853
Answer is 6
3 5 4 7 9
How many 5-digit numbers can be formed
arranging the above 5 digits?
The answer is 120.
It is hard to list down all the arrangements and
count the number to be 120.
We need a counting technique.
3 5 4 7 9
There are 5 digits as above.
I
II
III
IV
V
Consider 5 vacant positions as above.
The number of ways these 5 vacant positions
can be filled by these 5 digits will give me the
answer.
Digits
3 5 4 7 9
Positions
I
II
III
IV
V
Ways
5
4
3
2
1
Total number of arrangements
=5*4*3*2*1
= 120
Objects
A1 A2
An
Positions
P1 P2
Pn
Ways
n n-1
1
Total number of arrangements
= n * (n-1) * . * . * 1
= n!
3 5 4 7
How many 2-digit numbers can be formed
arranging the above 4 digits?
1. 35
2. 34
3. 37
4. 53
5. 54
6. 57
7. 43
8. 45
9. 47
10.73
11.75
12.74
Answer is 12
Let us apply our newly
learnt counting technique
Digits
3 5 4 7
Positions
I
II
Ways
4
3
Total number of arrangements
=4*3
= 12
Objects
A1 A2
An
In how many ways the above n objects
can be arranged among themselves
taking r (r < n) objects at a time?
We call the number npr
Objects
A1 A2
An
Positions
P1 P2
Pr
Ways
n n-1
n-r+1
Total number of arrangements
= n * (n-1) * . * . * (n-r+1)
= n! / (n-r)!
Objects
A1 A2
An
In how many ways the above n objects
can be grouped among themselves
taking r (r < n) objects at a time?
We call the number ncr
Consider ncr groups of n
objects taking r at a time
Each group contains r objects
that can be arranged among
themselves in r! ways
So, npr = r! ncr
nc
r
=
np
r
nc
r
=
nc
nc
r
= (n-1)cr + (n-1)c(r-1)
/ r! = n! / [r! (n-r!)]
(n-r)
A A A B C
In how many ways the above 5
objects can be arranged among
themselves taking all at a time?
Let the answer be x
A A A B C
Had the all 5 objects been different,
the total number of arrangements
would have been 5! = 120
Had the all 5 objects been different,
each of the x arrangements would
have produced 3! = 6 arrangements
A A A B C
So, 3! * x = 5!
Or, x = 5! / 3! = 120 / 6 = 20
B
A
Consider the 2 by 2 grid above
One needs to travel from A to B
along the lines
One can move only rightwards
and upwards
How many such routes are there?
B
A
1. RRUU
2. RURU
3. RUUR
4. URUR
5. URRU
6. UURR
The answer is 6
6 = 4! / (2! 2!)
Consider an m by n grid
Suppose one needs to travel from
bottom left hand corner to top right
hand corner following the lines
How many different routes are there?
Answer is (m+n)! / (m! * n!)
THANK YOU