Permutation and Combination – Distribution of identical object

Tuesday, May 21st, 2019


Permutation and Combination Distribution of identical object

Distribution of identical object is quite wide and important topic in permutation and combination. While distributing identical object it does not matter which object is given to which person, what matter that how many objects are given to any person.

Let us take a basic example to understand the concept of this topic let us assume we have to distribute five identical apples between two students such that a student can get any number of apples. If we give zero apple to first student second student will get all the five apples and if we give one apple to first student then other student will get remaining four apples. Note that we are counting only number of apples which we are giving to a student, which apple we are giving to which student it doesn’t matter because all the apples are identical. So total number of ways will be (0, 5), (1, 4), (2, 3), (3, 2), (4, 1) and (5, 0). Hence, there are six different ways for this distribution.

To understand this topic better first we start with non negative integral solution of an equation x1 + x2 + x3 …….+ xr = n

Consider a simple equation x + y = 5, then total number of non negative integral solution can be obtained by simple counting.

x y
0 5
1 4
2 3
3 2
4 1
5 0

Observe carefully the number of non negative solutions is exactly similar with distribution of 5 identical objects between two persons as discussed above. But if the equation has more than two variables It is difficult to count all the solutions manually.

In general if there are more than two variables in a equation such as x1 + x2 + x3 …….+ xr = n, so the total number of non negative solution is n+r-1Cr-1 . We can use this relation in various types of problems which are directly or indirectly (distribution of identical object) based on it. Note that the variables are non negative if it is given that variables are natural numbers or positive integer this formula can be transformed by assuming x1 = y1 +1, x2 = y2 +1,………………. xr = yr +1. Hence the transformed equation is y1 + y2 + ……. + yr + r = n or y1 + y2 ……. + yr  = n – r, so the required number of solution is n-1Cr-1. Where y1, y2, y3, ….. yr all are non negative integers because of the transformation x1, x2, x3 ….., xr becomes positive integers.

 

 Eg1:  Find the number of solution of equation x + y + z = 50; given that

  1. a) x, y and z are non negative integers
  2. b) x, y and z are natural numbers
  3. c) None of x, y and z is less than 2.
  4. d) x, y and z are even non negative

 Solution:

Case a) Let us assume we have fifty identical balls which we have to distribute between three students x, y and z such that a student can get any number of balls. This is equivalent to non negative integral solution of equation x + y + z = 50 where n = 50 and r = 3. So, it can be done in 52C2 ways.

Case b) Let us assume we have fifty identical balls which we have to distribute between three students x, y and z such that each student can get at least one ball. In this case we will one – one ball to each student and then we will distribute remaining balls in any way. Means mathematically we transform x = a + 1, y = b + 1 and z = c + 1, where a, b and c are non negative integers. So putting value of x, y and z in equation x + y + z = 50 we get  a + b + c  = 47 where n = 47 and r = 3. So, it can be done in 49C2 ways. In this case a, b and c are non negative integers and for that x, y and z becomes natural numbers or positive integers.

Case c) In this case we substitute x = a + 2, y = b + 2 and z = c + 2, where a, b and c are non negative integers and x, y and z are greater than or equal to 2. So putting value of x, y and z in equation x + y + z = 50 we get a + b + c = 44 where n = 44 and r =3. So, total number of solution is 46C2.

Case d) In this case put x = 2a, y = 2b and z = 2c, so the equation becomes 2(a + b + c) = 50 or a + b + c = 25, hence total number of solution is = 27C2.

 

 Eg2: 20 identical coins are distributed in four beggars. Find the total number of ways of distribution if each beggar gets at least two coins.

 Solution: Let us assume number of coins received by four beggars is a, b, c and d respectively. The question is similar to find solution of the equation a + b + c + d = 20, where a, b, c and d are more than 2. In this case since coins are identical, hence it does not matter which coin is given to which beggar so after giving 2 coins to each beggar remaining 12 coins can be distributed according to n+r-1Cr-1

So required number of ways = 15C3

 

Eg3: In a room there is unlimited number of identical black, white red and yellow balls. In how many ways 10 balls can be selected so that there is at least one ball of each colour?

 Solution: In this case since balls are identical, hence it does not matter which ball is selected, what matters is that how many balls are selected. So first we select one ball of each colour after that remaining six balls can be selected in any way. Hence after selecting one ball of each colour the remaining problem is similar to: Black + White + Red + Yellow = 6. So the number of solution is 9C3

 

Eg4: In how many ways can 12 identical pens be distributed among A, B and C so that A gets at least 1 pen, B gets at least 2 pens and C gets at least 3 pens?

 Solution: Again in this case since the pens are identical so first we give one pen to A, two pens to B and three pens to C. After that remaining pens can be distributed in any manner. So for remaining the equation can be a + b + c = 6, where a, b and c are non negative integers. So the number of ways of distributing is 8C2 = 28.       

 

Eg5: Find the non negative integral solution of the equation a + b + c + d = 100, where a, b, c and d are multiple of 5?

 Solution: Since all the non negative integer are multiple of 5, Let us assume a = 5x, b = 5y, c = 5z and d = 5u. So the given equation will become x + y + z + u = 20. So the number of solution is 23C3.

 

Eg6: Find the number of solutions of the equation 2a + b + c = 15, where a, b and c are non negative?

 Solution: Since a, b and c are non negative integers, so the maximum value of a can be 7.

a b + c Solution
7 1 2C1 = 2
6 3 4C1 = 4
5 5 6C1 = 6
4 7 8C1 = 8
3 9 10C1 = 10
2 11 12C1 = 12
1 13 14C1 = 14
0 15 16C1 = 16

So the number of solution is = 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 = 72.

 

Eg7: Find total number of solutions of the equation a + b + c = 27, where a, b and c are distinct non negative integers?

 Solution: Total number of non negative integral solutions = 27 + 3 – 1C2 = 29C2 = 406.

Now suppose number of triplets (a, b, c) when all three are different = M

Number of triplets (a, a, b) when exactly two are same = N

Number of triplet (a, a, a) when all three are same = P

M type triplets are counted 3! times in non negative integral solution as there arrangements is also considered and N type triplets are counted 3!/(2! ) times and P type of triplets are counted only once as all the elements are identical.
Now the total number of non negative integral solution is (3!) M + (3!/2!) N + P = 406.

By simple counting there is only one P type triplet i.e. (9, 9, 9). Number of N type of triplets is (0, 0, 27), (1, 1, 25)…….. (13, 13, 1) i.e. 14 triplets but here a triplet (9, 9, 9) is again counted. So total number of N type triplet is 14 – 1 = 13. Hence, 6M + 3 × 13 + 1 = 406,

6M = 366. So required number of solutions = 366.

 

Eg8: 45 identical chocolates are distributed among 3 students in such a way that every student receives at least one chocolate and no student receives same number of chocolates. Find the total number of ways of distribution?

 Solution: First we give one chocolate to each student after that remaining 42 chocolates can be distributed such that a student can get any number of chocolates can be understood by this equation x + y + z = 42, where x, y and z are non negative integers, so total number of solution is 44C2. Number of ways all three students getting an equal number of chocolates = 1. Number of ways exactly two of them are getting same number of chocolates = 3×21 = 63. Hence the number of ways when no two student receives same number of chocolates = 44C2– 1- 3×21 = 946 – 64 = 882.

 This is the first part of this topic to understand its practical approach better we will discuss its remaining application in next part.  As you can see the topic is quite wide and tricky also, you will face similar problems in the exam where you have to decide the approach of counting if you feel that the problem asked in exam is based on distribution of identical object then this method should hit in your mind. You will get more idea of the type of questions you need to practice through past year CAT papers. This is a very important topic in permutation and combination. Especially the last example is quite tricky and important part of this topic. Hopefully, I am able to explain the concept clearly.

Permutation and Combination – Distribution of Objects
Permutation and Combination – Fundamental Principle of Counting
Permutation and Combination – Division and Distribution of distinct objects

Other posts related to Quantitative Aptitude – Modern Maths

Set Theory- Maximum and Minimum Values
How to solve questions based on At least n in Set Theory for CAT Exam?
Permutation and Combination – Fundamental Principle of Counting
How to find Rank of a Word in Dictionary (With or Without Repetition)
Basic Probability Concepts for CAT Preparation
Sequence and Series Problems and Concepts for CAT Exam Preparation

CAT Questions related to Quantitative Aptitude – Modern Maths

All questions from CAT Exam Quantitative Aptitude – Modern Maths
Quantitative Aptitude – Modern Maths – Progressions – Q1: If a1 = 1/(2*5), a2 = 1/(5*8), a3 = 1/(8*11),……, then a1 + a2 +……..+ a100 is
Quantitative Aptitude – Modern Maths – Progressions – Q2: An infinite geometric progression a1, a2, a3,… has the property that an = 3(a(n+ l) + a(n+2) +….) for every n ≥ 1. If the sum a1 + a2 + a3 +……. = 32, then a5 is
Quantitative Aptitude – Modern Maths – Progressions – Q3: Let a1, a2, a3, a4, a5 be a sequence of five consecutive odd numbers. Consider a new sequence of five consecutive even numbers ending with 2a3.
Quantitative Aptitude – Modern Maths – Progressions – Q4: Let a1, a2,……..a3n be an arithmetic progression with a1 = 3 and a2 = 7. If a1 + a2 + ….+a3n = 1830, then what is the smallest positive integer m such that m (a1 + a2 + …. + an ) > 1830?
Quantitative Aptitude – Modern Maths – Progressions – Q5: If the square of the 7th term of an arithmetic progression with positive common difference equals the product of the 3rd and 17th terms, then the ratio of the first term to the common difference is
Quantitative Aptitude – Modern Maths – P&C – Q1: How many four digit numbers, which are divisible by 6, can be formed using the digits 0, 2, 3, 4, 6, such that no digit is used more than once and 0 does not occur in the left-most position?
Quantitative Aptitude – Modern Maths – P&C – Q2: In how many ways can 8 identical pens be distributed among Amal, Bimal, and Kamal so that Amal gets at least 1 pen, Bimal gets at least 2 pens, and Kamal gets at least 3 pens?
Quantitative Aptitude – Modern Maths – P&C – Q3: In how many ways can 7 identical erasers be distributed among 4 kids in such a way that each kid gets at least one eraser but nobody gets more than 3 erasers?
Quantitative Aptitude – Modern Maths – P&C – Q4: Let AB, CD, EF, GH, and JK be five diameters of a circle with center at O. In how many ways can three points be chosen out of A, B, C, D, E, F, G, H, J, K, and O so as to form a triangle?
Quantitative Aptitude – Modern Maths – P&C – Q5

Online Coaching Course for CAT 2020

a) 900+ Videos covering entire CAT syllabus
b) 2 Live Classes (online) every week for doubt clarification
c) Study Material & PDFs for practice and understanding
d) 10 Mock Tests in the latest pattern
e) Previous Year Questions solved on video


If you Like this post then share it!


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.