# Counting Principles

1. Fundamental Counting Principle :

If task-I can be performed in m ways, followed by task-II can be performed in n ways, then task-I followed by task-II can be performed in ( m x n ) ways.

2. Permutations:

A permutation is an arrangement of objects in a definite order.

The number of permutations of n different object is the product of first n natural numbers is called n factorial, that is  $$n!=n(n-1)(n-2)\times ……….\times 3\times 2\times 1$$

For example, the number of permutations of 5 different objects would be $$5!= 5\times 4\times 3\times 2\times 1$$ = 120.  So 5 different objects can be arranged in 120 different ways.

Some resultes to rember :

$$n!=n(n-1)(n-2)\times ……….\times 3\times 2\times 1$$
also n! can be expressed as,
$$n!=n(n-1)!$$ ,
$$n!=n(n-1)(n-2)!$$ etc.,

1! = 1 and  0! = 1

Permutations fo r objects from n different objects:
The number of permutations of only r objects from n different objects is the product of r natural numbers in descending starting with n.

That is $${ _{ n }{ P }_{ r } }=n(n-1)(n-2)\times ……….\times (n-r+1)$$.

$${ _{ n }{ P }_{ r } }=n(n-1)(n-2)\times ……….\times (n-r+1)=\frac { n! }{ (n-r)! }$$.

Some results to remember
[1]  $${ _{ n }{ P }_{ r } }=\frac { n! }{ (n-r)! }$$,
when r = n then we have $${ _{ n }{ P }_{ n } }=\frac { n! }{ (n-n)! } \\ \quad \quad =\frac { n! }{ 0! } \\ \quad \quad =\frac { n! }{ 1 } \quad since\quad0!=1\\ { _{ n }{ P }_{ n } }=n!\\$$.
[2]  $${ _{ n }{ P }_{ r } }=\frac { n! }{ (n-r)! }$$,
when r = 0 then we have $${ _{ n }{ P }_{ 0 } }=\frac { n! }{ (n-0)! } \\ \quad \quad =\frac { n! }{ n! } \\ { _{ n }{ P }_{ n } }=1\\$$

Permutations of repeated elements

The number of permutations of n objects in which m objects are identical is $$\frac { n! }{ m! }$$.

In a set of n object, if there are  n1 number of identical items, n2 number of identical items then the total permutations is $$\frac { n! }{ { n }_{ 1 }!{ n }_{ 2 }! }$$

Example :

Find the number of different arrangements of the eleven letters of the word ABRACADABRA

Solution

In the word MATHEMATICS , some letters repeating out of 11 letters.

There are 2 A’s , 2 M’s out of 11 letters

Therefore the number of different arrangements = $$\frac { 11! }{ 2!\times 2!}$$

Circular Permutations

The number of permutations of n objets in a circular arrangement is $$(n-1)!$$.

There are $$(n)!$$ ways$$n$$ non-identical objects can be arranged in a line and $$(n-1)!$$ ways in a circular arrangement.

3. Combinations:

A Combination is any selection of objects where the order of the objections is of no concern.

The number of Combinations r objects from n different objects is $${ _{ n }{ C }_{ r } }$$.

To permutate r objects from n different objects, we could first select the r objects in $${ _{ n }{ C }_{ r } }$$ ways and then arrange these r objects in r! ways.

So the permutation of r objects from n objects is $${ _{ n }{ P }_{ r } }={ _{ n }{ C }_{ r }\times }r!\\$$.Thus $${ _{ \quad \quad n }{ P }_{ r } }={ _{ n }{ C }_{ r }\times }r!\\ \Rightarrow \quad _{ n }{ C }_{ r }=\frac { _{ n }{ P }_{ r } }{ r! } \\ \quad \quad _{ n }{ C }_{ r }=\frac { n! }{ (n-r)!\times r! } \quad \quad \\ \\$$

Problem Solving

Question no: 1

Find the number of different arrangements of the eleven letters of the word ABRACADABRA

Solution

In the word ABRACADABRA , some letters repeating out of 11 letters.

There are 5 A’s , 2 B’s , 1 C , 1 D  and 2 R’s out of 11 letters

Therefore the number of different arrangements = $$\frac { 11! }{ 5!\times 2!\times 2! } =83160$$

Question no: 2

A girl wishes to phone a friend but cannot remember the exact number. She knows that it is a five digit number, that it is even, and it consists of the digits 2,3,4,5,6 in some order. Using this information, find the largest number of different wrong telephone numbers she could try.

Solution

Since the number is even the last digit must end with either 2 or 4 or 6.

No of ways the last digit can be filled is 3.

The first four digits can be of any of the 4 remaining numbers.

No of ways =  4!

Total no of possible telephone numbers = 4! X 3 = 72.

But only one of the numbers is correct.

Therefore no. Of different wrong telephones, she could try  = 71.

Question no: 3

In how many ways can a committee of 3 men and 3 women e chosen from a group of 7 men and 6 women? The oldest of the 7 men is A and the oldest of the 6 women is B. It is decided that the committee can included at most one of A and B. It is decided that the committee can include at most one of A and B. In how many ways can the committee now be chosen?

Solution

No of ways committee can be formed (no restriction) = $$\left( \begin{matrix} 7 \\ 3 \end{matrix} \right) \times \left( \begin{matrix} 6 \\ 3 \end{matrix} \right) =700$$

No of ways such that A is in and B is not in = $$\left( \begin{matrix} 6 \\ 2 \end{matrix} \right) \times \left( \begin{matrix} 5 \\ 3 \end{matrix} \right) =150$$

No of ways such that B is in and A is not in = $$\left( \begin{matrix} 6 \\ 3 \end{matrix} \right) \times \left( \begin{matrix} 5 \\ 2 \end{matrix} \right) =200$$

No of ways such that both A and B are not in = $$\left( \begin{matrix} 6 \\ 3 \end{matrix} \right) \times \left( \begin{matrix} 5 \\ 3 \end{matrix} \right) =200$$

Total no of ways = 550.

Question no:4

A ten-digit number is formed by writing down the digits 0,1,2,3,4,5,6,7,8,9 in some order. No number is allowed to start with 0. Find how many such numbers are odd.

Solution

Since the required number must be odd, the last digit must end in either 1, 3, 5, 7 or 9. No. of combinations = 5.

The first digit cannot start with ‘0’ and also cannot be the same as the last digit. No. of combinations = 8.

For the second to the ninth digits, they can be any number as long as they do not repeat. No of combinations = 8!

No. that are odd = 8 X 8! X 5 = 1 612 800

Question no:5

Eight people go to the theater and sit in a particular group of eight adjacent reserved seats in the front row. Three of the eight belong to one family and sit together.

If the other five people do not mind where they sit, find the number of possible seating arrangements for all eight people.

If the other five people do not mind where they sit, except that two of then refuse to sit together, find the number of possible seating arrangements for all eight people.

(i)  Number of ways a family of three can sit = 3! = 6

Taking the family as a collective group number of ways five people and a

group can sit =  6! = 720.

Number of ways all eight people can sit =  6 X 720 = 4320.

(ii)  Number of ways a group of two can sit = 2! = 2.

Taking the family as a group and the two people who refuse to sit together

as another group, number of ways three people and two groups can

sit = 5! = 120.

Number of ways all eight people can sit, with family sitting together and

the two people next to each other = 6 X 2 X 120 = 1440.

Number of ways all eight people can sit, with the family sitting together

and the two people sitting apart = 4320 – 1440 = 2880.

Question no:6

The salad bar at a restaurant has 6 separate bowls containing lettuce, tomatoes, cucumber, radishes, spring onions and beetroot respectively. John decides to visit the salad bar and make a selection. At each bowl, he can choose to take some of the contents or not.

Assuming that John takes some of the contents from at least one bowl, find how many different selections he can make.

John decides he is going to have 4 salad items, and one of them will be tomatoes. How many different selections can he make?

(i)    At each bowl, John is faced with two possibilities: to take or not to take.

There are 6 bowls, therefore number of different selections = 26 -1 = 63.

(ii)   Since John has already decided to take tomatoes he has now the choice

of 3 salad items out of 5 instead of 4 out of 6.

Number of different selections = 5C3 = 10.

Question no:7

In this question, a ‘world’ is defined to be any set of letters in a row, whether or not it makes sense. Find how many different ‘words’ can be made using all 8 letters of the world SYLLABUS.

Number of “words” = 8! = 10080

2!2!

Question no:8

Find the numbers of 4 letter code worlds that can be made from the letters of the world ADVANCE,

Using neither for the “A” ’s ,

Using both of the “A” ’

(i)  If neither of the “A” is used, then there are only 5 distinct letters from which to form 4-letter code-words.

No of 4-letter code words = 5 X 4 X 3 X 2 = 120.

(ii)  If both “A”’ s are used, then each resulting 4-lettercode-word consists of 2 “A”’s and two distinct letters out of the remaining 5.

No of 4-letter code words = 5 X 4 = 20.

Question no:9

Find the number of different arrangements of the 9 letters of the world SINGAPORE I which S does not occur as the first letter.

Solution

No of different arrangements with no conditions = 9!

No of different arrangements with S as the first letter = 8!

No of different arrangements of the word in which S does not occur as the first letter = 9! – 8! = 322560.

Question no:10

Three students are selected to form a chess team from a group of 5 girls and 3 boys. Find the number of possible teams that can be selected in which there are more girls than boys.

No of possible teams = 5C2 X 3C1 + 5C3 X 3C0

= 30 + 10 = 40

Question no:11

A garden Centre sells 10 different varieties of rose bush. A gardener wishes to buy 6 rose bushes, all of different varieties.

Calculate the number of ways she can make her selection. Of the 10 varieties, 3 are pink, 5 are red and 2 are yellow. Calculate the number of ways in which her selection of 6 rose bushes could contain,

[a] No pink rose bush

[b] At least one rose bush of each color.

Solution

10C6 = 210

7C6 = 7.

No of ways in which there is no yellow rose bush = 8C6 = 28.

No of ways = 210 – 7 – 28 = 175.

Question no:12

(i) Find the number of different arrangements of the letters of the word MEXICO. Find the number of these arrangements.

(ii)   Which begin with M

Which have the letter X at one end and the letter C at the other end. Four of the letters of the word MEXICO are selected at random. Find the number of different combinations if

There is no restriction on the letters selected.

The letter M must be selected.

Solution

No of arrangements

No of arrangements

No of arrangements = 2! X 4! = 48.

No of different combinations = 6C4 = 15

No of different combinations = 5C3 = 10

Question no:13

(a) Calculate the number of different 6-digit numbers which can be formed using the digits 0,1,2,3,4,5 without repetition and assuming that a number cannot begin with 0.

(b)  A committee of 4 people is to be chosen from 4 women and 5 men. The committee must contain at least 1 woman. Calculate the number of different committees that can be formed.

Solution

(a)

(b)   1 woman 3 men = 4C1 X 5C3 = 40

2 woman 2 men = 4C2 X 5C2 = 60

3 woman 1 men = 4C3 X 5C1 = 20

4 woman 0 men = 4C4 =1

Total ways = 40 + 60 + 20 +1 = 121.

Question no:14

(a) The producer of a play requires a total cast of 5, of which 3 are actors and 2 are actresses. He auditions 5 actors and 4 actresses for the cast. Find the total number of ways in which the cast can be obtained.

(b)  Find how many different odd 4-digit number less than 4000 can be made from the digits 1, 2, 3, 4, 5, 6, 7 if no digit may be repeated.

Solution

(a)   Total no of ways = 5C3 X 4C2 = 60

(b)   1.  __  X  __ X odd  =  60

5        4        3

__  X  __ X odd  =  80

5        4        4

__  X  __ X odd  =  60

5        4        3

Total number of odd 4 digit nos < 4000 = 60 + 80 + 60  = 200

Question no:15

A set of 20 students is made up of 10 students from each of two different year-groups. Five students are to be selected from the set and the order of selection id unimportant. Find

The total number of possible selections

The number of selections in which there are at least two students from each of the two year-groups.

Total no of possible selections

= 20C5 = 15504.

Combinations group1       group2

Case1               2                 3

Case2               3                 2

No of selections = 2 X ( 10C2 X 10C3)  =  10800.

Question no:16

A panel of judges in an essay competitions must select and place in order of merit, 4 winning entries from a total entry of 20.

Find the number of ways in which this can be done. As a step in the selection, 5 finalists are selected, without being placed in order. Find the number of ways in which this can be done.

All 20 essays are subsequently assessed by three panels of judges for content, accuracy and style, respectively, and three special prizes are awarded, one by each panel. Find the number of ways in which this can be done, assuming that an essay may win more than one prize.

Solution

No of ways to select, and place in order of merit, 4 winning entries out of 20.

= 20 X 19 X 18 X 17 (or 20P4)

= 116 280

No of ways to select 5 finalists without order = 20C5.

= 20 X 19 X 18 X 17 X 16

5 X 4 X 3 X 2 X 1

= 15 504

No of ways to award the 3 prizes = (20)3 = 8000

Find the number of arrangements of all nine letters of the word SELECTION inn which

The two letters E are next to each other

The two letters E are not next to each other.

(i) If the two letters E are next to each other, we treat them as one object. Therefore there are eight distinct objects to be arranged.

No of arrangements = 8! = 40 320.

(ii) This situation is complement of part(i). Total number of arrangements of all nine letters = 91 / 2 = 181 440.

Hence, the number of arrangements where the E’s are not together

= 181 400 – 40 320 = 141 120.

Question no:17

Eleven cards each bear a single letter, and together they can be made to spell the word ”EXAMINATION”. Three cards are selected from the eleven cards, and the order of selection is not relevant. Find how many possible selections can be made.

(i) if the three cards all bear different letters

(ii) if two of the three cards bear the same letter.

Solution

(i) The different letters are E, X, A ,M, I, N, T,O

No of possible selections = 8C3 = 56.

(ii) There are two A’s, I’s and N’s.

If two of the three cards bear the same letter, then it must be either 2 A’s, 2 I’s, 2 N’s.

I.e 3 possibilities. If two A’s are selected, the remaining card can be either E, X , M, I, N,T or O

i.e 7 possibilities. A similar arrangement applies if the two similar cards are N’s or I’s. No of possible selections = 3 X 7 = 21.

Question no:18

In this question, a ‘word’ is defined by any set of letters in a row, whether or not it makes sense. Find how many different “words” can be made by using all 8 letters of the word SYLLABUS.

Solution

Number of ‘words’ =

Question no:19

The number 105 840 can be expressed in prime factors as 24 X 33 X 51 X72. Excluding 1 and 105840, how many positive integers are factors of 105840?

Solution

Every factor of 105840 is of the form 2a X 3b X 5c X7d where

a = 0, 1, 2, 3, 4 (5 choices)

b = 0, 1, 2, 3 (4 choices)

c = 0, 1, 2 (2 choices)

d = 0, 1, 2, 3 (3 choices) The total number of positive factors is 5 X 4 X 2 X 3 = 120. Not counting 1 and 105840, there are 118 positive integer factors.