Counting Principles

COUNTING PRINCIPLES

There are two fundamental counting principles viz. Multiplication principle and Addition principle. There are certain other counting principles also as given below:

⋄ Bijection principle

⋄ Inclusion-exclusion principle

Multiplication Principle:

If one experiment has n possible outcomes and another experiment has m possible outcomes, then there are m x n possible outcomes when both of these experiments are performed.
In other words, if a job has n parts and the job will be completed only when each part is completed and the first part can be completed in a1 ways, the second part can be completed in a2 ways and so on …. the nth part can be completed in an ways, then the total number of ways of doing the job is a1a2a3……….. an. This is known as the Multiplication principle.

Example : A college offers 7 courses in the morning and 5 in the evening. Find the possible number of choices with the student if he wants to study one course in the morning and one in the evening.

Solution: The student has seven choices from the morning courses out of which he can select one course in 7 ways.

For the evening course, he has 5 choices out of which he can select one in 5 ways. Hence the total number of ways in which he can make the choice of one course in the morning and one in the evening = 7 x 5 = 35.

Example : A person wants to go from station A to station C via station B. There are three routes from A to B and four routes from B to C. In how many ways can he travel from A to C?

Solution:

A -> B in 3 ways

B -> C in 4 ways

=> A -> C in 3 x 4 = 12 ways

Remark:

⋄ The rule of product is applicable only when the number of ways of doing each part is independent of each other
i.e. corresponding to any method of doing the first part, the other part can be done by any method

Example : How many (i) 5 − digit (ii) 3 − digit numbers can be formed by using 1, 2, 3, 4, 5 without repetition of digits.

Solution: (i) Making a 5-digit number is equivalent to filling 5 places. Places:

Number of Choices:

The first place can be filled in 5 ways using anyone of the given digits.

The second place can be filled in 4 ways using any of the remaining 4 digits.

Similarly, we can fill the 3rd, 4th and 5th place.

No. of ways of filling all the five places

= 5 x 4 x 3 x 2 x 1 = 120 => 120       5-digit numbers can be formed.

(ii) Making a 3-digit number is equivalent to filling 3 places.

:Places

Number of Choices:

Number of ways of filling all the three places = 5 x 4 x 3 = 60

Hence the total possible 3-digit numbers = 60.

Addition principle

If one experiment has n possible outcomes and another has m possible outcomes, then there are (m + n) possible outcomes when exactly one of these experiments is performed.

In other words, if a job can be done by n methods and by using the first method, can be done in a1ways or by second method in a2 ways and so on . . . by the nth method in an ways, then the number of ways to get the job done is (a1 + a2 + … + an).

Example : A college offers 7 courses in the morning and 5 in the evening. Find the number of ways a student can select exactly one course, either in the morning or in the evening.

Solution: The student has seven choices from the morning courses out of which he can select one course in 7 ways.

For the evening course, he has 5 choices out of which he can select one course in 5 ways.

Hence he has total number of 7 + 5 = 12 choices.

Example : A person wants to leave station B. There are three routes from station B to A and four routes from B to C. In how many ways can he leave the station B.

Solution:

B -> A in 3 ways

B -> C in 4 ways

=> He can leave station B in 3 + 4 = 7 ways.

Bijection Principle:

Generally it is not easy to count the numbers belonging to a very large collection(set) directly. Let us assume that we have a set X and we want to count n(x) ( number of elements in X). And we have another set Y and n(Y) can be counted(easily). Now if there exists one-one and onto relationship from set X to set Y, then n(X) = n(Y) .

In other words, if X and Y are two finite sets such that there is a bijection ( i.e. one-one onto map) from X to Y ,

then n(X) = n(Y).

For example let us take a simple case. The sitting capacity of a class is 30. On a particular day, the class is full then, without actual counting, we can say that the total number of the students present in the class is 30.

Inclusion-Exclusion Principle:

Let U be a finite set of m elements and p1 , p2 , p3 , . . . ,pr be some properties which the objects of U may or may not have,

Then the number of elements of U which have at least one of the properties p1, p2, p3, ….. , pr is given by

= S1 − S2 + S3 − S4 + . . . +(−1)r−1Sr

and the number of elements of U which have none of the properties p1, p2, p3 , . . . , pr is given by

= m − S1 + S2 − S3 + … + (− 1) r Sr

Where Ai denotes the subset of U each of whose elements has the property pi( i = 1, 2, …. , r) and Aicdenotes the subset of U none of whose elements has the property pi

Ai ∩ Aj denotes the set of all elements of U having both properties pi and pj and so on. And Sk denotes the total number of elements of U having any k of the given r properties.

E.g. S1 = n(A1) + n(A2) + …. + n(Ar) ,

S2 = n(A1∩A2) + n(A1∩ A3) + … + n(A1∩Ar) + n(A2∩A3) + . . . + n(A2∩Ar) + …. + n(Ar−1 ∩ Ar)

In particular case:

For r =2 , n(A1∪A2) = n(A1) + n(A2) − n(A1∩A2)

For r = 3,
n(A1∪A2 ∪A3) = n(A1) + n(A2) + n(A3) − n(A1∩A2) − n(A1∩A3) − n(A2∩A3) + n(A1 ∩ A2 ∩A3)

For r = 4,
n(A1∪A2∪A3∪A4) = n(A1) +n(A2) + n(A3) + n(A4) − n(A1∩A2) − n(A1∩A3) − n(A1∩A4)

− n(A2∩A3) − n(A2∩A4) − n(A3∩A4)+ n(A1 ∩ A2 ∩A3) + n(A1 ∩ A2 ∩A4)
+ n(A1 ∩ A3 ∩A4) + n(A2 ∩ A3 ∩A4) − n(A1∩A2 ∩ A3 ∩A4)

Illustration 6: Find the number of integers between 1 and 1000, both inclusive

(a) Which are divisible by either of 10, 15 and 25.

(b) Which are divisible by neither 10 nor 15 nor 25

Solution: Let U denote the set of numbers between 1 and 1000 so that n(U) = 1000

Let A, B and C denote the sets of integers divisible by 10, 15 and 25 respectively.

Then n(A) = 1000/10 =100

n(B) = 1000/15 = 66, and n(C) = 1000/25 = 40

S1 = n(A) + n(B) + n(C) = 100 + 66 + 40 = 206

Considering two of the three sets A, B, C, we have

A ∩ B = set of integers divisible by 10 and 15

= set of integers divisible by 30 (L.C.M of 10 and 15)

=> n( A ∩ B) = 1000/30 = 33

Similarly, B ∩ C = set of integers divisible by 15 and 25

= set of integers divisible by 75 (L.C.M of 15 and 25)

=> n( B ∩ C) = 1000/75

Similarly, A ∩ C = set of integers divisible by 10 and 25

= set of integers divisible by 50 (L.C.M of 10 and 25)

=> n( A ∩ C) = 1000/50

S2 = 33 + 13 + 20 = 66.

Finally, A ∩ B ∩ C = set of integers divisible by 10, 15 and 25

= set of integers divisible by 150 (L.C.M of 10, 15 and 25)

=> n( A ∩ B ∩ C) = 1000/150 = 6

S3 = 6

(a) We have to find the number of integers divisible by either

of 10 , 15 , and 25 i.e. n(A∪ B∪C)

n(A∪ B∪C) = S1 − S2 + S3 = 206 − 66 + 6 = 146

(b) The number of integers divisible by neither 10 nor 15 , nor 25

= n(U) − n(A∪ B∪C) = 1000 − 146 = 854

Remark:
# The number of integers from 1 to n which are divisible by k is [n/k] ( [ . ] denotes the greatest integer function). e.g. the number of integers from 1 to 100 which are divisible by 2 and 3 individually are [100/2] = 50 and [100/3] = 33 respectively

# The number of natural numbers from 1 to n, which are perfect kth powers, is [n1/k]. e.g. the number of perfect squares from 1 to 110 is [ √110 ] = 10

Exercise 1:

i) Four dice are rolled once. Find the number of outcomes in which at least one die shows 3

ii) A die is rolled ten times find the no of ways so that out comes always contain 1 , 2 , 3

Next Page »

Leave a Reply