# COUNTING TECHNIQUES - Quantitative Techniques for management

A collection of techniques and rules for counting the number of outcomes that can occur for a particular experiment can be used. They are called counting techniques.

Fundamental Principle of Counting

If the first operation can be performed in any one of the m ways and then a second operation can be performed in any one of the n ways, then both can be performed together in any one of the m*n ways.

This rule can be generalized. If first operation can be performed in any one of the n1 ways, second operation in any one of the n2 ways, ...... kth operation in any one of the nk ways, then together these can be performed in any one of the n1× n2× ...... × nk ways.

Permutation

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

(a) Permutations of n objects: The total number of permutations of n distinct objects is n!. Using symbols, we can write nPn= n!, (where n denotes the permutations of n objects, all taken together).

Let us assume there are n persons to be seated on n chairs. The first chair can be occupied by any one of the n persons and hence, there are n ways in which it can be occupied. Similarly, the second chair can be occupied in n - 1 ways and so on. Using the fundamental principle of counting, the total number of ways in which n chairs can be occupied by n persons or the permutations of n objects taking all at a time is given by:

nPn = n(n – 1)(n – 2) ...... 3.2.1 = n!

(b) Permutations of n objects taking r at a time: In terms of the example, considered above, now we have n persons to be seated on r chairs, where r ≤ n.

Thus, nPr = n(n – 1)(n – 2) ...... [n – (r – 1)] = n(n – 1)(n – 2) ...... (n – r + 1).

On multiplication and division of the R.H.S. by (n - r)!, we get (c) Permutations of n objects taking r at a time when any object may be repeated any number of times: Here, each of the r places can be filled in n ways. Therefore, total number of permutations is nr.

(d) Permutations of n objects in a circular order: Suppose that there are three persons A, B and C, to be seated on the three chairs 1, 2 and 3, in a circular order. Then, the following three arrangements are identical: Similarly, if n objects are seated in a circle, there will be n identical arrangements of the above type. Thus, in order to obtain distinct permutation of n objects in circular order we divide nPnby n, where nPndenotes number of permutations in a row.

Hence, the number of permutations in a circular ordern!/n = (n-1)!

Permutations with restrictions: If out of n objects n1 are alike of one kind, n2 are alike of another kind, ...... nk are alike, the number of permutations are

n!/n1!n2!n3!....nk!

Since permutation of ni objects, which are alike, is only one (i = 1, 2, ...... k). Therefore, n! is to be divided by n1!, n2! .... nk!, to get the required permutations.

Example : What is the total number of ways of simultaneous throwing of
(i) 3 coins,
(ii) 2 dice and
(iii) 2 coins and a die?

Solution:
(i) Each coin can be thrown in any one of the two ways, i.e, a head or a tail, therefore, the number of ways of simultaneous throwing of 3 coins = 23 = 8.
(ii) Similarly, the total number of ways of simultaneous throwing of two dice is equal to 62 = 36 and
(iii) The total number of ways of simultaneous throwing of 2 coins and a die is equal to 22 * 6 = 24.

Example : A person can go from Delhi to Port-Blair via Allahabad and Calcutta using following mode of transport : In how many different ways the journey can be planned?

Solution: The journey from Delhi to Port-Blair can be treated as three operations; From Delhi to Allahabad, from Allahabad to Calcutta and from Calcutta to Port-Blair. Using the fundamental principle of counting, the journey can be planned in 4*4*2 = 32 ways.

Example : In how many ways the first, second and third prize can be given to 10 competitors?
Solution: There are 10 ways of giving first prize, nine ways of giving second prize and eight ways of giving third prize. Therefore, total no. ways is 10* 9* 8 = 720.
Alternative method: Here n = 10 and r = 3, Example :

1. There are 5 doors in a room. In how many ways can three persons enter the room using different doors?
2. A lady is asked to rank 5 types of washing powders according to her preference. Calculate the total number of possible rankings.
3. In how many ways 6 passengers can be seated on 15 available seats.
4. If there are six different trains available for journey between Delhi to Kanpur, calculate the number of ways in which a person can complete his return journey by using a different train in each direction.
5. In how many ways President, Vice-President, Secretary and Treasurer of an association can be nominated at random out of 130 members?

Solution:

1. The first person can use any of the 5 doors and hence can enter the room in 5 ways. Similarly, the second person can enter in 4 ways and third person can enter in 3 ways. Thus, the total number of ways is 5p3= 60
2. Total number of rankings are 5p5= 120
3. Total number of ways of seating 6 passengers on 15 seats are 15p6= 3603600
4. Total number of ways of performing return journey, using different train in each direction are 6*5 = 30, which is also equal to 6p2.
5. Total number of ways of nominating for the 4 post of association are 130p4

Example : Three prizes are awarded each for getting more than 80% marks, 98% attendance and good behaviour in the college. In how many ways the prizes can be awarded if 15 students of the college are eligible for the three prizes?

Solution: Note that all the three prizes can be awarded to the same student. The prize for getting more than 80% marks can be awarded in 15 ways, prize for 90% attendance can be awarded in 15 ways and prize for good behaviour can also be awarded in 15 ways.

Thus, the total number of ways is nr = 153 = 3,375.

Example :

1. In how many ways can the letters of the word EDUCATION be arranged?
2. In how many ways can the letters of the word STATISTICS be arranged?
3. In how many ways can 20 students be allotted to 4 tutorial groups of 4, 5, 5 and 6 students respectively
4. In how many ways 10 members of a committee can be seated at a round table if (i) they can sit anywhere (ii) president and secretary must not sit next to each other?

Solution:

1. The given word EDUCATION has 9 letters. Therefore, number of permutations of 9 letters is 9! = 3,62,880.
2. The word STATISTICS has 10 letters in which there are 3S's, 3T's, 2I's, 1A and 1C. Thus, the required number of permutations 10!/3!3!2!1!1!=50400
3. Required number of permutations 20!/4!5!5!6!=9777287522
4. (i) Number of permutations when they can sit anywhere = (10-1)!= 9! = 3,62,880.
(ii) We first find the number of permutations when president and secretary must sit together. For this we consider president and secretary as one person.
Thus, the number of permutations of 9 persons at round table = 8! = 40,320.
∴ The number of permutations when president and secretary must not sit together
= 3,62,880 - 40,320 = 3,22,560.

Example :

1. In how many ways 4 men and 3 women can be seated in a row such that women occupy the even places?
2. In how many ways 4 men and 4 women can be seated such that men and women occupy alternative places?

Solution:

1. 4 men can be seated in 4! ways and 3 women can be seated in 3! ways. Since each arrangement of men is associated with each arrangement of women, therefore, the required number of permutations = 4! 3! = 144.
2. There are two ways in which 4 men and 4 women can be seated
MWMWMWMWMW or WMWMWMWMWM
The required number of permutations = 2 .4! 4! = 1,152

Example : There are 3 different books of economics, 4 different books of commerce and 5 different books of statistics. In how many ways these can be arranged on a shelf when

1. all the books are arranged at random,
2. books of each subject are arranged together,
3. books of only statistics are arranged together, and
4. books of statistics and books of other subjects are arranged together?

Solution:

1. The required number of permutations = 12!
2. The economics books can be arranged in 3! ways, commerce books in 4! Ways and statistics book in 5! ways. Further, the three groups can be arranged in 3! ways.
∴ The required number of permutations = 3! 4! 5! 3! =1,03,680.
3. Consider 5 books of statistics as one book. Then 8 books can be arranged in 8! ways and 5 books of statistics can be arranged among themselves in 5! ways.
∴ The required number of permutations = 8! 5! = 48,38,400.
4. There are two groups which can be arranged in 2! ways. The books of other subjects can be arranged in 7! ways and books of statistics can be arranged in 5! ways. Thus, the required number of ways = 2! 7! 5! = 12,09,600.

Combination

When no attention is given to the order of arrangement of the selected objects, we get a combination. We know that the number of permutations of n objects taking r at a time is nPr. Since r objects can be arranged in r! ways, therefore, there are r! permutations corresponding to one combination. Thus, the number of combinations of n objects taking r at a time, denoted by nCr, can be obtained by dividing nPrby r!, i.e., Note:

1. Since nCr, nCn r , therefore, nCris also equal to the combinations of n objects taking (n - r) at a time.
2. The total number of combinations of n distinct objects taking 1, 2, ...... n respectively, at a time is nC1 + nC2 + …… + nCn = 2n-1

Example :

1. In how many ways two balls can be selected from 8 balls?
2. In how many ways a group of 12 persons can be divided into two groups of 7 and 5 persons respectively?
3. A committee of 8 teachers is to be formed out of 6 science, 8 arts teachers and a physical instructor. In how many ways the committee can be formed if
1. Any teacher can be included in the committee.
2. There should be 3 science and 4 arts teachers on the committee such that (i) any science teacher and any arts teacher can be included, (ii) one particular science teacher must be on the committee, (iii) three particular arts teachers must not be on the committee?

Solution

Ordered Partitions

1. Ordered Partitions (distinguishable objects)

1. The total number of ways of putting n distinct objects into r compartments which are marked as 1, 2, ...... r is equal to rn.
Since first object can be put in any of the r compartments in r ways, second can be put in any of the r compartments in r ways and so on.
2. The number of ways in which n objects can be put into r compartments such that the first compartment contains n1 objects, second contains n2 objects and so on the rth compartment contains nr objects, where n1 + n2 + ...... + nr = n, is given by n1!/n1!n2!n3!..nr!

To illustrate this, let r = 3. Then n1 objects in the first compartment can be put in nCn1 ways. Out of the remaining n – n1 objects, n2 objects can be put in the second compartment in n n1Cn2 ways. Finally the remaining n – n1– n2 = n3 objects can be put in the third compartment in one way. Thus, the required number of ways is

ncn1*nn1cn2=n!/n1!n2!n3!

2. Ordered Partitions (identical objects)

(a) The total number of ways of putting n identical objects into r compartments marked as 1, 2, ...... r, is n r 1Cr 1, where each compartment may have none or any number of objects.

We can think of n objects being placed in a row and partitioned by the (r – 1) vertical lines into r compartments. This is equivalent to permutations of (n + r – 1) objects out of which n are of one type and (r – 1) of another type.

The required number of permutations are ( n+r-1/n!(r-1)), which is equal to (n+r-1)Cnor(n+r-1)Cr-1

(b) The total number of ways of putting n identical objects into r compartments is (n-r)+(r-1)C(r-1)or(n-1)C(r-1)- , where each compartment must have at least one object.

In order that each compartment must have at least one object, we first put one object in each of the r compartments. Then the remaining (n – r) objects can be placed as in (a) above.

(c) The formula, given in (b) above, can be generalised. If each compartment is supposed to have at least k objects, the total number of ways is(n-kr )+ (r-1 )C(r-1) where k = 0, 1, 2, .... etc. such that K=n/r

Example : 4 couples occupy eight seats in a row at random. What is the probability that all the ladies are sitting next to each other?

Solution: Eight persons can be seated in a row in 8! ways.

We can treat 4 ladies as one person. Then, five persons can be seated in a row in 5! ways. Further, 4 ladies can be seated among themselves in 4! ways.
∴ The required probability = 5!4!/ 8! = 1/14

Example: 12 persons are seated at random (i) in a row, (ii) in a ring. Find the probabilities that three particular persons are sitting together.

Solution:

1. The required probability = 10!3! / 12! = 1/22
2. The required probability = 9!3! / 11! = 3/ 55

Example : 5 red and 2 black balls, each of different sizes, are randomly laid down in a row. Find the probability that

1. the two end balls are black,
2. there are three red balls between two black balls and
3. the two black balls are placed side by side.

Solution: The seven balls can be placed in a row in 7! ways.

1. The black can be placed at the ends in 2! ways and, in-between them, 5 red balls can be placed in 5! ways.
∴ The required probability = 2!5!/ 7! = 1/21
2. We can treat BRRRB as one ball. Therefore, this ball along with the remaining two balls can be arranged in 3! ways. The sequence BRRRB can be arranged in 2! 3! ways and the three red balls of the sequence can be obtained from 5 balls in 5C3ways.
∴ The required probability = 3!2!3!/ 7! x 5C3= 1/7
3. The 2 black balls can be treated as one and, therefore, this ball along with 5 red balls can be arranged in 6! ways. Further, 2 black ball can be arranged in 2! ways.
∴ The required probability = 6!2!/ 7! = 2/7

Example: Each of the two players, A and B, get 26 cards at random. Find the probability that each player has an equal number of red and black cards.

Solution: Each player can get 26 cards at random in 52C26 ways.

In order that a player gets an equal number of red and black cards, he should have 13 cards of each colour, note that there are 26 red cards and 26 black cards in a pack of playing cards. This can be done in 26C13 , 26C13 ways.

Hence, the required probability = 26C13 x 26C13 / 52C26

Example : 8 distinguishable marbles are distributed at random into 3 boxes marked as 1, 2 and 3. Find the probability that they contain 3, 4 and 1 marbles respectively.

Solution: Since the first, second.... 8th marble, each, can go to any of the three boxes in 3 ways, the total number of ways of putting 8 distinguishable marbles into three boxes is 38.

The number of ways of putting the marbles, so that the first box contains 3 marbles, second contains 4 and the third contains 1, are 8!/ 3!4!1!

∴ The required probability = 8!/ 3!4!1! x 1/38 = 280/ 6561.

Example: 12 'one rupee' coins are distributed at random among 5 beggars A, B, C, D and E. Find the probability that:
(i) They get 4, 2, 0, 5 and 1 coins respectively.
(ii) Each beggar gets at least two coins.
(iii) None of them goes empty handed.

Quantitative Techniques for management Topics