Counting
Principles
There are two fundamental counting
principles viz. Multiplication principle and Addition principle. There are
certain other counting principles also as given below:.
q
Bijection
principle
q
Inclusion-exclusion
principle
Multiplication Principle:
If one experiment has n possible outcomes and another
experiment has m possible outcomes, then there are m ´ 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.1
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 ´ 5 = 35.
Example.2
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 ´ 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.3
Find the number of three -digit natural numbers having
digits in increasing order from left to right
Solution :
Here we
have to fill three places.
First place can be
filled by numbers 1, 2, ….7, second by 2, 3, ….8 and third by 3, 4,….9. i.e.
the number of ways of .
filling each place is seven but total number of ways is
not 7´7´7= 343. Reason behind this is that
corresponding to 1 at first place, second place can be filled up by anyone of
seven digits 2–8 but when we put 2 at first place, the number of ways of
filling second place is only six. So the number of ways of doing each part is
not independent. So rule of product is not applicable in this case. The
right approach for this problem is that first select three distinct non-zero
digits which can be done in 9C3 ways, then arrange them
in increasing order which can be done in one way only. Therefore, the required
number of natural numbers is 9C3 ´ 1 = 84.
Example.4
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.
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 ´ 4 ´ 3 ´
2 ´ 1 = 120
&⇒ 120 5-digit numbers can be formed.
(ii) Making a
3-digit number is equivalent to filling 3 places.
Number of ways of
filling all the three places = 5 ´
4 ´ 3 = 60
Hence the total
possible 3-digit numbers = 60.
