The learning objective is to cover the fundamental principles of counting such as sum rule, product rule, permutations and combination.

1 Sum Rule

The sum rule states that if we have m number of ways of doing something and n number of ways of doing another thing and we can not do both at the same time, then there are m + n ways to choose one of the actions.

2 Product Rule

The product rule states that if there are m ways to do A and n ways to do B, then the number of ways to do A and B is m × n. This is true if the number of ways of doing A and B are independent.

Question:

A boy lives at X and wants to go to School at Z. From his home X he has to first reach Y and then Y to Z. He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z. How many ways are there to go from X to Z?

Solution:

From X to Y, he can go in 3+2=5 ways (Sum Rule). Thereafter, he can go Y to Z in 4 + 5 = 9 ways (Sum Rule). Hence from X to Z he can go in 5 × 9 = 45 ways (Product Ruleh).

3 Permutations

A permutation of a set of distinct objects is an ordered arrangement of the objects.

Example

Let S = {a, b, c}

The permutation of S = {{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}}

Note that even though they are the same elements, each is considered a different permutation since they do not have the same order.

• The number of permutations of n different things taken r at a time is denoted by nPr
• nPr = n!/(n - r)!

4 Combinations

A combination is selection of some given elements in which order does not matter.

Example

Let S = {a, b, c}

The 2-combination of S = {{a, b}, {a, c}, {b, c}}

{a, b} covers both the permutations {a, b} and {b, a} since order doesn’t matter for combinations.

• The number of all combinations of n things, taken r at a time is denoted by nCr
• nCr = n!/r!(n - r)!

5 Binomial Theorem

6 Pigeonhole Principle

The pigeonhole principle states that if n pigeons are put into m pigeonholes where n > m, there’s a hole with more than one pigeon.

Generalised Pigeonhole Principle

If N objects are placed into k bins then there is at least one bin containing at least ⌈ N / k ⌉ objects.

Question:

Assume 100 people. Can you tell at least how many people are born in the same month?

Solution:

There exists a month in which at least ⌈ 100 / 12 ⌉ = ⌈ 8.3 ⌉ = 9 people were born.