The Feline Trouble Beckons - This time It’s PnC and its applications - Ankan Sengupta, FMS Delhi
ankan_sengupta last edited by zabeer
FMS Delhi (2015 - 2017), CAT 2014 - 99.79 percentile
Permutation and combination has always been a chapter where even a maths wizard might stumble. Cause you can infer an answer(not all of them are correct of course) for a particular question by various methods and to a layman all of them might seem probable. So how to go about a chapter like this which commands an immense importance from not only the perspective of any competitive exam, but also due to its application to other topics.
I’ll be discussing a few relevant questions today to try to demystify this topic as much as possible. So let me segregate this chapter into several parts at first-
Problems regarding arrangements of a few things in a few boxes/container:
a) Different balls and different boxes:
If there are n balls and they are put into r boxes,total number of arrangements= rn.
Now this includes cases where 1 or more boxes are empty. So the no. of ways of putting the balls in n boxes so that each box contains at least 1 ball is=0(if n < r) or rn - rC1*(r-1)n + rC2*(r-2)n - rC3*(r-3)n+…,unless a term is becoming 0. This result can be proved by inclusion-exclusion principle. Interested readers can refer to it to delve into this method further.
Note-This is the same formula that we apply to count no. of onto function from set A(containing r elements) to set B (containing n elements).
Now this included cases where arrangement among the balls is also important.
In how many ways can you distribute 5 rings in 4 fingers?
Ans: Ring 1 can go to any finger.Ring 2 can go to 4 fingers,but it has 5 choices.Because there is aready a ring in a finger,so ring 2 can go to that particular finger in two positions.Above the previous ring and below that previous ring.So it has 5 choices.Similarly next ring will have 6 choices and so on.Thus we’ll get total arrangements=8!/3!.This can be generalised with a single formula= (n+r-1)!/(r-1)!, n=number of balls, r=no. of boxes.
b) Identical balls different boxes:
If we try to distribute n identical balls into r different boxes ,no. of ways to do it is n+r-1Cr-1.If each box contains at least 1 ball then the number of arrangements= n-1Cr-1.
Now a related question is, if there are n balls out of p are alike, q are alike, r are alike and rest s are all different, then number of arrangements=n!/(p!*q!*r!)
This concept can be used for further applications. We can use it in multinomial theorem.
Find co-efficient of the term a^4b^3c in the expression ( a + b + c )8
Ans: the answer would be of the form n!/p!*q!*r!,where p+q+r=n=8 and p=power of a in the given term=4,q=power of b and r=power of c.So the required answer is 8!/4!*3!
The total number of ways in which n different object are to be divided into groups such that k1 groups have groups size n1 , k2 groups have groups size n2 and so on kr groups have size nr , is given as
c) Identical balls identical boxes
There are 2 ways you can go about this problem- a) manual counting b) by using concept of unordered cases.
Manual counting is the process known to everybody.I’d discuss the latter one. In the previous case we had boxes that are different. So that means the order of the boxes does matter. Here we just have to eliminate that order.
In how may ways 5 identical balls can be distributed in 3 identical boxes ?
Then ordered cases=7C2.Justmake it unordered by the technique explained in my previous article on number theory. You’ll get answer as 5 only which is same if you calculate it manually.
d) Different balls identical boxes:
Now this is the unordered of the first sub-topic.
In how many ways can we arrange 5 different balls in 3 identical boxes ?
If the boxes were different, answer would have been 3^5.
But again making it unordered will yield the answer as 41 which is the required answer.
Now here’s another method to solve this problem: using starling number of second kind.
The Stirling numbers of the second kind, written with other notations, count the number of ways to partition a set of n labelled objects into k non empty unlabelled subsets. Equivalently, they count the number of different equivalence relations with precisely k equivalence classes that can be defined on an n element set. Obviously,
They can be calculated using the following explicit formula:
So simply the problems becomes S(5,1) + S(5,2) + S(5,3) = 41.
Now I’ll be discussing a few problems on Permutation and Combination on rest of the portions,mainly on how to generate cases in solving problems.
How many 6 digit numbers formed from the digits 1 to 5 and any digit that appears in it, appears atleast twice ?
A.for all identical 5 cases
Total 1405 cases
How many 6-digit numbers contain exactly four different digits?
(d) None of these
A. Only two Possible cases pqrspp and pqrspq.
1st-- 10c4*4c1*6!/3! = 100800
2nd -- 10c4*4c2*6!/2!2! = 226800
now it includes no starting with 0 as we have taken out of 10 no 0 cant be at the start so no would be 9*327600/10 so 294840
Now here comes a trick to a problem where many people starts counting or try to make series just after seeing the problem. It can be done in a much easier way actually just by using logic and basic combinations.
Out of first 1000 natural numbers how many numbers have digits in ascending order and how many in descending order ?
A. ascending 10c3 and descending 10c3+10c2
For ascending 3 digit numbers 3 digits have been selected out of 10.
Now since the digits are in ascending order the digits will be automatically arranged among themselves if I just select those 3 digits.
So answer is 10C3.
Similar case will happen for 2 digit numbers also making the answer for this case=10C2
So total is 10C3+10C2
Similar case for descending too.
Now comes 2 of my most favourite type of problems in PnC.
In how many ways can 73 identical chocolates be stuffed into three boxes – B1, B2 and B3 – such that B1 contains more chocolates that B2 and B2 contains more chocolates than B3 ?
36+34+33+31+...are you getting the series?it'll run upto 1..12 terms in the series 36+33+30+.. and 12 terms in 34+31+28+...just sum these 2 up.you'll get 444
Take first whole numbers solutions all cases.
u get 75c2. So 2775 cases
Then in which there are cases where some are equal.
For every value 2 values of b1, b2=b3 once. (beginning from odd)
So 37 values for each equality. So 111 cases eliminated.
Now Remaining cases 2664,
none of which are equal to each other , that means arrangement is 3!. So one of the arrangements is the answer, that is 2664/6= 444
a < b means b=a+x+1
And b < c, means c= b+y+1
So a+b+c = > a+a+x+1+a+x+y+2= > 3a+2+2b+1+c=73
Same as a+2b+3c=70
Now put c values, n u’ll get the pattern, then sum up.
5 digit multiples of 6 are formed using digits 0,2,4,6,5,8 exactly once. What is the remainder if sum of all such numbers is divided by 1000 ?
A. unit digit can be 0/2/4/6/8
sum of digits= 3k
only way to get sum of digits 3k is by taking (0,2,5,6,8 )
so sum of all such nos.= 3!*(0+2+5+6+8 )* [44444- 1111]= 126* 43333
From this remove the case of odd numbers which is
_ _ _ _ 5
basically find the sum of _ _ _ _ by using normal formulae, multiply the sum by 10 and add 5 for each case.
3*3! case.. so add 5 total 18 times =90
sum of _ _ _ _ (0,2,6,8 )= 2!*16*(3333-111)= 32 * 3222
Sum of odd nos= 90+ (103104*10)=1031130
So finally sum of all multiples of 6= 126*43333 - 1031130= 4428828
These two are examples of most complicated problems that you can face from PnC.
Now before ending this article I’d discuss one more important topic: De-arrangement.
If n distinct things are arranged in a row,then number of ways they can be rearranged such that none of those things are occupying their previous position,then the no of ways this can be achieved=
Here comes one superlative example of this type of problem
Five friends attended a party. At the end of the night, they each randomly grabbed a left shoe and a right shoe.Find the number of ways such that each person left with exactly one of their own shoes?
A. 2*D(5)+ 5c3 *2*2 =2*44+40=128
Case 1:all of them got their right shoew correctly.So they all got their eft shoew wrongly. Cases=D(5).again they can all get left shoe correctly,right show wrongly.So total 2*D(5) cases for this
Case 2: If 4 of them gets their right shoe correctly,it’s obvious that 5 th one will also get his right shoe correctly.So ultimately it becomes equal to case 1
Case 3: 3 of them got their right shoe correct and rest 2 got their left shoe correctly. Now these 3 can be chosen in 5C3 ways. Now the 2 right shoes that are left can be exchanged in only 1 way. And 3 left shoes can be exchanged in D(3)=2 ways. So total cases=5C3*2*1=5C3*2 ways.
Now just the opposite can happen also.
So total contribution of case 3=2*5C3*2.
Now just sum these two cases up.
I’ve discussed all the major topics under PnC now. Rest is upto you. Practise,Practise and Practise to make yourself perfect. PnC can really be an interesting topic if learnt conceptually.