## Thursday, 8 December 2011

### Containers – Items (P and C Concepts)

There are 3 containers and 5 items. In how many ways can these items be placed in the containers?

This is a conceptual one and we can see four different cases here:

Type-I:    Similar Containers – Similar Items:

 X X X 5 0 0 4 1 0 3 1 1 3 2 0 2 2 1

5 ways

Type-II:     Different Containers – Similar Items:

Type-II(A) Each container having at least one item:

 X Y Z 3 1 1 3!/2! = 3 ways 2 2 1 3!/2! = 3 ways

3+3 = 6 ways
If the number of containers is r and the number of items is n, and if each container should contain at least one item,
then the number of ways = (n-1)C(r-1)
= (5-1)C(3-1) = 4C2 = 6

Type-II(B) No barring on number of items of each container:

 X Y Z 5 0 0 3!/2! = 3 ways 4 1 0 3! = 6 ways 3 1 1 3!/2! = 3 ways 3 2 0 3! = 6 ways 2 2 1 3!/2! = 3 ways

3+6+3+6+3 = 21 ways
If the number of containers is r and the number of items is n, the formula here is (n+r-1)C(r-1)
= (5+3-1)C(3-1) = 7C2 = 21

Type-III:      Similar Containers – Different Items:

 X X X 5 0 0 1 way 4 1 0 5!/4! = 5 ways 3 1 1 5!/3! = 20 ways 3 2 0 5!/3!2! = 10 ways 2 2 1 5!/2!2! = 30 ways

1+5+20+10+30 = 66 ways

Type-IV:     Different Containers – Different Items:

This is combination of types II and III.
 X Y Z 5 0 0 3*1  = 3 ways 4 1 0 6*5 = 30 ways 3 1 1 3*20 = 60 ways 3 2 0 6*10 = 60 ways 2 2 1 3*30 = 90 ways

3+30+60+60+90 = 243 ways
If the number of containers is r and the number of items is n, the formula here is
r= 35 = 243
Most of the problems can be categorized into one of these four types.

Examples:

Q1)There are 5 types of Ice-creams in a shop. In how many different ways can Rahul buy 6 Ice-creams?
Solution:
Here selecting 6 Ice-creams (may be of any variety) out of 5- different varieties is the only criteria and no further arrangements of the selected Ice-creams is required. Hence, this can be categorized as Type-II(B) problem, where number of different varieties of Ice-creams = r = 5 and number of Ice-creams to buy = n = 6
=> (n+r-1)C(r-1) = 10C4 ways

Q2) A new flag has to be designed with six vertical stripes using some or all of the colours yellow, green, blue and red. Then the number of ways this can be done such that no two adjacent stripes have the same colour is:  (CAT-2004)
(1)12*81         (2)16*192         (3)20*125             (4)24*216
Solution:
Here selecting 6 colours out of 4- different varieties and also arranging them is required (such that no two adjacent stripes have the same colour).
Hence, this can be categorized as Type-IV problem.
First stripe can have 4 choices, second one can have remaining 3 choices, again third one can have 3 choices, similarly, fourth, fifth and sixth ones can have three choices each.
Total number of ways = 4*3*3*3*3*3 = 12*81
Note that had there been no condition that "no two adjacent stripes have the same colour", the answer would have been  rn = 46

Concept on number of integral solutions:
Q3)To find the number of integral solutions of the equation x1+x2+x3+....+xr = n:
This is similar to Type-II model with ‘r’ number of baskets and ‘n’ number of items.
For finding number of non-negative integral solutions:
The solution may contain zeroes also, hence it is similar to Type-II(B) model
=> Number of solutions = (n+r-1)C(r-1)
For finding number of positive integral solutions:
The solution should not contain zeroes, hence it is similar to Type-II(A) model
=> Number of solutions = (n-1)C(r-1)

Q4)Find the total number of natural numbers having sum of digits five and number of digits at most five?
Solution:
Here, the number of digits is at most five. Hence it may be 1 or 2 or 3 or 4 or 5.
_      _      _      _          _
If the left most digit is filled with any non-zero number, then this set becomes a five digit number.
Leaving the left most digit vacant, if the second-left digit is filled, this set becomes a 4-digit number,
and so on and so forth.. Finally, leaving four left most digits vacant, if the unit digit is filled with any non-zero number, than the set becomes a single-digit number. So we can consider 5 digits at a time and depending on the position of zeroes from the left, different sized numbers will be formed.
As we need to get the sum of digits also to be 5, this is of model Type-IIB with the number of containers being 5 and number of items also being 5.
(5+5-1)C(5-1) = 9C4 = (9*8*7*6)/(4*3*2*1) = 126

Q5)In how many ways five different coins can be distributed among three persons where every one get at least one coin?
Solution:
Here, the coins as well as the persons being different, this comes to be Type-IV.
 A B C Ways 3 1 1 3*(5!)/(3!) = 60 ways 2 2 1 3*(5!)/(2!)(2!) = 90 ways
60+90 = 150 ways
Explanation:
First, these five different coins can be divided into 3,1,1 set in 5!/3! ways
Next this (3,1,1) set can be distributed among three in the following 3 ways:
(3,1,1);            (1,3,1);            (1,1,3);
Combining, we get, 3*5!/3! = 60
Similarly (2,1,1) set has 3*5!/(2!*2!)  = 90 ways.
In total, 60+90 = 150 ways.