COUNTING PRINCIPLES

There are two fundamental counting principles viz. Multiplication principle and Addition principle.

Multiplication Principle:

If one experiment has n possible outcomes and another experiment has m possible outcomes, then there are m $\times$ n possible outcomes when both of these experiments are performed.

Illustration-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 $\times$ 5 = 35.

Illustration -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 $\to$ B in 3 ways

B $\to$ C in 4 ways

$\Rightarrow$ A $\to$ C in 3 $\times$ 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.

Illustration -3: 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 $\times$ 4 $\times$ 3 $\times$ 2 $\times$ 1 = 120

$\Rightarrow$ 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 $\times$ 4 $\times$ 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 different methods and for the first method there are a1 ways, for the second method there are a2 ways and so on . . . for the nth method, an ways, then the number of ways to get the job done is (a1 + a2 + ... + an).

Illustration-4: 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.

PERMUTATIONS (ARRANGEMENT OF OBJECTS)

The number of permutations of n objects, taken r at a time, is the total number of arrangements of r objects, selected from n objects where the order of the arrangement is important.

Without Repetition:

(a) Arranging n objects, taken r at a time is equivalent to filling r places from n things.

The number of ways of arranging = The number of ways of filling r places

= n(n – 1) (n – 2) ….. (n – r + 1)

= $\frac{n\left(n-1\right)\left(n-2\right).....\left(n-1\right)\left(\left(n-r\right)!\right)}{\left(n-r\right)!}.$ = $=\frac{n!}{\left(n-r\right)!}={}^n{P}_r$

(b) The number of arrangements of n different objects taken all at a time ${}^{n}P-n=n!$

With Repetition:

(a) The number of permutations (arrangements) of n different objects, taken r at a time, when each object may occur once, twice, thrice…. upto r times in any arrangement

= The number of ways of filling r places where each place can be filled by any

one of n objects .

The number of permutations = The number of ways of filling r places

= (n)r

(b) The number of arrangements that can be formed using n objects out of which p are identical (and of one kind), q are identical (and of another kind), r are identical (and of another kind) and the rest are distinct is $\frac{n!}{p!q!r!}$

Illustration-5: (a) How many anagrams can be made by using the letters of the word HINDUSTAN.

(b) How many of these anagrams begin and end with a vowel.

(c) In how many of these anagrams, all the vowels come together.

(d) In how many of these anagrams, none of the vowels come together.

(e) In how many of these anagrams, do the vowels and the consonants occupy the same relative positions as in HINDUSTAN.

Solution: (a) The total number of anagrams

= Arrangements of nine letters taken all at a time = $\frac{9!}{2!}....=181440.$

(b) We have 3 vowels and 6 consonants, in which 2 consonants are alike. The first place can be filled in 3 ways and the last in 2 ways. The rest of the places can be filled in $\frac{7!}{2!}.$.ways. Hence the total number of anagrams $=3\times 2\times \frac{7!}{2!}=15120$

(c) Assume the vowels (I, U, A) as a single letter. The letters (IUA) H, D, S, T, N, N can be arranged in $\frac{7!}{2!}$ways. Also IUA can be arranged among themselves in $3!=6$ ways.

Hence the total number of anagrams = $\frac{7!}{2!}\times 6=15120$

(d) Let us divide the task into two parts. In the first, we arrange the 6 consonants as shown below in $\frac{6!}{2!}$ ways.

$\times$ C $\times$ C $\times$ C $\times$ C $\times$ C $\times$ C $\times$ (C stands for consonants and $\times$ stands for blank spaces inbetween them)

Now 3 vowels can be placed in 7 places (in between the consonants) in $7p_3=\frac{7!}{4!}=210$ways.

Hence the total number of anagrams =$\frac{6!}{2!}\times 210=75600$

(e) In this case, the vowels can be arranged among themselves in 3! = 6ways.

Also, the consonants can be arranged among

themselves in $\frac{6!}{2!}$ ways.

Hence the total number of anagrams =$\frac{6!}{2!}\times 6=2160.$

CIRCULAR PERMUTATIONS

There are arrangements in closed loops also, called as circular arrangements.

Suppose n persons (a1, a2, a3,…,an) are to be arranged around a circular table. The total number of circular arrangements of n persons is $\frac{n!}{n}....=\left(n-1\right)!.$

Distinction between clockwise and anti-clockwise Arrangements:

Consider the following circular arrangements:

In figure I, the order is clockwise whereas in figure II, the order is anti-clock wise. These are two different arrangements. When distinction is made between the clockwise and the anti-clockwise arrangements of n different objects around a circle, then the number of arrangements = (n – 1)!

But if no distinction is made between the clockwise and the anti-clockwise arrangements of n different objects around a circle, then the number of arrangements is $\frac{1}{2}$.(n – 1)!

For an Illustration, consider the arrangements of beads (all different) on a necklace as shown in figures A and B.

Look at (A) having 3 beads x1, x2, x3 as shown. Flip (A) over on its right. We get (B) at once. However, (A) and (B) are really the outcomes of one arrangement but are counted as two different arrangements in our calculation. To nullify this redundancy, the actual number of different arrangements is (n-1)!/2.

Remarks:

When the positions are numbered, circular arrangement is treated as a linear arrangement.

In a linear arrangement, it does not make difference whether the positions are numbered or not.

Illustration-6: Consider 23 different coloured beads in a necklace. In how many ways can the beads be placed in the necklace so that 3 specific beads always remain together?

Solution: By theory, let us consider 3 beads as one. Hence we have, in effect, 21 beads, 'n' = 21. The number of arrangements = (n-1)! = 20!

Also, the number of ways in which 3 beads can be arranged between themselves is 3! = 3 x 2 x 1 = 6.

Thus the total number of arrangements = (1/2). 20!. 3!.

Illustration-7: In how many ways 10 boys and 5 girls can sit around a circular table so that no two girls sit together.

Solution: 10 boys can be seated in a circle in 9! ways. There are 10 spaces inbetween the boys, which can be occupied by 5 girls in 10p5 ways. Hence total number of ways

$=9!{}^{10}{P}_5=\frac{9!10!}{5!}$