Discrete Mathematics

2

Counting

In our everyday life, we come across many different counting problems. There are two basic counting principles—Addition Rule and Multiplication Rule.

2.1 ADDITION RULE

If a set A is the union of n distinct mutually disjoint subsets A₁, A₂, …, A_n, then

 

|A| = |A₁| + |A₂| + … + |A_n|,

where |A_i| denotes the number of elements in the set A_i.

The addition rule can also be stated as

If an event E₁ can occur in m ways and an event E₂ can occur in n ways, then E₁ or E₂ can occur in m + n ways.

EXAMPLE 2.1

Let E₁ be the event of choosing an odd number between 10 and 20 and E₂ be the event of choosing an even number between 10 and 20. Since odd numbers between 10 and 20 are {11, 13, 15, 17, 19}, E₁ can occur in five ways. Similarly even numbers ...