Permutations & Combinations - Questions & Discussions

sureshbala · February 26, 2012, 7:00am

MadaboutIIMs Says
There are (2n+1) numbers out of which 3numbers are to be chosen at random.What is the probability that the number choosen is in A.P.

Total No. of ways in which 3 number can be chosen from 2n+1 numbers =(2n+1)C3

Since the three numbers are in AP, the common difference of the three numbers can be 1, 2, 3 .....n-1, n

If the common difference is 1, the possible combinations are

1, 2, 3
2, 3, 4
.........
.........
2n-1, 2n, 2n+1

Since there are (2n-1) possible combinations, we can choose the three numbers in 2n-1 ways

If the common difference is 2, the possible combinations are

1, 3, 5
2, 4, 6
.........
.........
2n-3, 2n-1, 2n+1

So 2n-3 combinations if the common difference is 2.

If the common difference is 3, the possible combinations are

1, 4, 7
2, 5, 8
.........
.........
2n-5, 2n-2, 2n+1

So 2n-5 combinations if the common difference is 3.

Similarly, if the common difference is n-1, the possible combinations are
1, n, 2n-1
2, n+1, 2n
3, n+2, 2n+1

So, for the common difference n-1 we have 3 possible combinations

If the common differnce is n, we will have only 1 possible combination given as below
1, n+1, 2n+1

Hence, the total number of ways in which we can choose 3 numbers such that they are in AP is
1 + 3 + .............+(2n-5) + (2n-3) + (2n-1)

Clear the above value is the sum of the first 'n' odd numbers = n^2 (Or you can consider the above as the sum of 'n' numbers in AP)

Hence, required probability = n^2/((2n+1)C3) = 3n/(4n^2 - 1)

121186 · February 29, 2012, 7:54pm

It's a Probability question but i guess it always makes sense posting it in P&C; category.Here it is and would greatly help somebody explaining the solution of it.Also i don't know what is its answer.

"Laura has a deck of standard playing cards with 13 of the 52 cards designated as a "heart". If Laura shuffles the deck thoroughly and then deals 14 cards off the top of the deck, what is the probability that the 14th card dealt is a heart ?

chillfactor · March 9, 2012, 1:46pm

It's a Probability question but i guess it always makes sense posting it in P&C; category.Here it is and would greatly help somebody explaining the solution of it.Also i don't know what is its answer.

"Laura has a deck of standard playing cards with 13 of the 52 cards designated as a "heart". If Laura shuffles the deck thoroughly and then deals 14 cards off the top of the deck, what is the probability that the 14th card dealt is a heart ?

I think it will be simply 1/4, as it is equally likely to be any of the other category.

mrunalpatel · March 17, 2012, 4:45am

For someone totally new to the PnC topic
Permutation Combination made easy without Formulas

Index:

Part#1: Permuation
FUNDAMENTAL COUNTING PRINCIPLE

There are 3 trains from Mumbai to Ahmedabad and 7 trains from Ahmedabad to Kutch. In how many ways can Jethalal reach Kutch?
From Mumbai to Abad, Jethalal can go in 3 ways. (Because there are three train, he can pick anyone)
Similarly From Abad to Kutch, he can go in 7 ways.
Total ways: simple multiplication =3 ways x 7 ways =21 ways Jethalal can reach Kutch.
This is fundamental counting principle.

Lets extend this further to sitting arrangement problems:

PERMUTATION (PLACE, ARRANGEMENT)

6 Men of Gokuldham society go to Abduls sodashop. And there are 6 chairs. Yes Im talking about our beloved Jethalal, Bhide Master, Sodhi, Dr.Haathi, Mehta saab and Aiyyar.

In how many ways can they be seated? Or How many way can you arrange these 6 gentlemen into 6 chairs?

CASE 1: SIX MEN AND 6 CHAIRS

Lets do one chair at a time.
For the first chair, youve 6 candidates:
Just pick one man and make him sit.
How many ways can you do it? Ans. 6 ways, bcoz youve 6 men and pick one. (Just like the train)
Now second chair: youve to pick one guy from the remaining 5 members. So 5 ways.
Third chair: 4 men remaining and youve to pick one: again 4 ways..

For the 6th chair only one man remains. So you can pick in 1 way only.

Now Just extending the fundamental counting principle
So total number of ways in which men of Gokuldham society can sit in chairs
= 6 x 5 x 4 x 3 x 2 x 1
=6! (six factorial ways)

CASE 2: SIX MEN AND 3 CHAIRS?

How many arrangements possible?

= 6 x 5 x 4 x ..OK STOP! Because there are only 3 chairs.
Why?
First chair= 6 men pick one=6 ways.
Second chair = 5 men pick one=5 ways
Third chair=4 men pick one= 4 ways

Thats all.
So number of ways
=6x5x4
=120 ways.

CASE 3: ONE CHAIR ALWAYS OCCUPIED

In the 6 men 6 chairs problem, Dr.Haathi insists that hell sit in the number #1 chair only. Then How many arrangements are possible?

First chair= 1 man (Haathi) and youve to pick one= 1 way only!
Second chair=5 men remain, pick one =5 ways
third chair=4 men remain, pick one = 4 ways and so on...

So here weve
=1x5x4x3x2x1
=5! Ways.
=120 ways.

This is permutation. Here order / ranking matters. i.e. who sits in the first chair, who sits in the second chair etc.

The same question can appear under different wordings example
1. How many 4 lettered words can be formed out of UPSC, without repetition?
Answer: Same logic. Consider U, P, S, C are four gentlemen and theyve to be arranged in 4 seats.

2. How many 4 letter words can be formed out of UPSC so that U always occupies the second position from left?
Answer: Same Dr.Haathi logic.

(Combination Concept in Second Post:)

mrunalpatel · March 17, 2012, 4:52am

COMBINATION (CHOICE)
CASE 1: COMMITTEE FORMATION

The one and only Secretary of Gokuldham society, Master Bhide decides to form a 3 member-Committee for arrangement of Holi-festival. Out of the 5 members (Jetha, Sodhi, Mehta, Popat and Aiyyar) how many ways can he do this?

Ans.
Here order or ranking doesnt matter.

Because in case of chair sitting: we can say yes Mr.Sodhi is in first chair, Mehta saab in Second chair and so on
But in case of Committee: it is only IN or OUT i.e. Yes Sodhi is in the Committee, No Mehta saab is not in the Committee.
So order doesnt matter. Only selection matters.

Lets proceed
How many ways can you pick up the first member? = 5 ways.
Second member? = 4 men remain, 4 ways
Third member? = 3 ways.

So total ways= 5 x 4 x 3= 60.
But wait, there is over counting.

A committee made up of Mehta, Sodhi and Aiyyar (MSA) is same as a Committee made up of Aiyyer, Mehta and Sodhi. (AMS) (because order doesnt matter, only selection matters: are you In or Out?).
But in this answer 60, weve over counted such orders.
Thats why we need to divide the answer

Suppose Mehta, Sodhi and Aiyyar are in the committee.
Suppose theyve to sit in three chairs. How many ways can you do it?
Just like permutation in first example
3 x 2 x 1=6.
Thats the overcounting : 6.

Our answer is
=(5*4*3)/(3*2*1)=10 ways.

CASE 2: HANDSHAKES

Handshakes is another type of combination problem because
Aiyyar shakes hand with Sodhi or Sodhi shakes hand with Aiyyer= both incidents are one and same. order doesnt matter!
So How many ways can 6 men of Gokuldham society shake hands with each other?

To shake hands, you need two men.
How many ways can you pick up first man? = 6 ways.
How many ways can you pick second man? = 5 men remaining so 5 ways.

Hence answer is 6 x 5=30
But wait, over counting!!

Suppose Sodhi and Aiyyer (SA) are selected for handshaking: =two men.
How many ways can you make two men sit in two chairs?
= 2 x 1 =2 ways. (SA and AS)
Thats the over counting.
So weve to divide this over counting: to get the correct answer.
Total Handshakes=(6*5)/(2*1)=15

The Formulas

The books give readymade formulas:

But essentially theyre derived from above concepts of fundamental counting principle.

Permutation =place them = order matters in placement
Combination= choice = only Yes or No or In or Out

mrunalpatel · March 17, 2012, 4:57am

[Aptitude] Probability Made Easy

(Extension of Permutation Combination Concept!)

Introduction

Probability is merely a subtype of Permutation and Combination (PnC) concept.
Probability can be solved without mugging up formulas, if your basic concepts are clear.
So, before proceeding in this article, DO read my previous article : Permutation & Combination (PnC) made easy without formulas
Since I'm not interested in talking about coins, dice and card in probability article, Let's get back to Gokul-dhaam Society.
We'll learn all the concepts of probability, with following 6 characters so keep the names and faces in mind.

Let us start with extremely easy one
Case1 : Probability of Particular Actor getting selected

Director Asit Modi wants to shoot an episode in Essel World waterpark, he has to pick up only one character out of the given six character. What is the probability that Jethalal will be selected for this episode?

How many ways can you choose 1 character out of the given talent pool of 6 characters?
Fundamental counting principle: 6 ways. (or 6C1 =6)
Means total possible results=6.

And what is asked in the question?
Jethalal should get selected.
So keep Jethalal aside in a separate 'talent-pool' and ask your self, how many ways can Jethalal be selected out of given talent pool?
There is one character and we've to pick up one character: 1C1= One way only.
Desired result = 1 ways

Matter is finished.
Probability = Desired result divided by total results = 1/6

See the photo, it should make the picture clear

Now I'm modifying the case
Case 2: Probability of One lady getting selected

Quest. Same question as before. Modi has to pick up one character out of the given six. What is the probability of a lady getting selected?..Continue Reading

Total results remains the same: 6C1= 6 ; as in case #1
And what is asked?
One lady.
How many ladies do we have in this talent pool? 2 (Anjali and Babita)
Put them in separate 'ladies' talent pool.
How many ways can you select one lady out of the given two ladies? : 2 ways (2C1) = desired result

Probability = 2/6 = 1/3

Alternative: Same question rephrased:

What is the probability that the selected one character has moustaches?
Out of the given six, only two has moustaches (Jethalal, Mehta-saab)
Then principle remains the same as in Case #2

Case #3: One man and one woman

[INDENT]Q. Modi has to select a team of 2 characters out of given six. What is the probability that it has one man and one woman?
[/INDENT]Again this is a combination problem, we've to select a 'committee' of two people. Jetha-Mehta (JM) is same as Mehta -Jetha (MJ)

Total results

How many ways can you select two characters out of given six?
= (6 x 5) / (2 x 1) =15 (=6C2)
How did we get this ^?
Your "combination" concept should be rock-solid now. If not, read my previous PnC article again.

Desired result

Selection of one man and one woman.
Recall the very first example on "fundamental counting"
Jethalal had to pick up two trains. (Mumbai - A'bad and Ahmedabad- Kutch). Same principle is applied here

=[pick one man out of given 4] (multiply) [pick one woman out of given 2]
=4 x 2
=8 ways.
When "AND" is asked. You multiply the cases.
You can also look at this as a combination problem
Choose one man 'Committee' out of 4 men and choose one woman Committee out of 2 women.
=4C1 x 2C1
=4 x 2 = 8 ways.

Desired result = 8 ways.

Final answer
Probability = Desired result / Total results = 8/15

Case 4: "Atleast" one man is selected

Ques. Direct Asit Modi has to select 2 characters out of given six. What is the probability at atleast one of them is a man.

When they ask "Atleast or Atmost" etc we've to break up the case.

Team of two actors can be formed in following fashion
1. 1 man and 1 woman. (Order doesn't matter, this is a Committee!)
2. Both men
3. Both women

Atleast 1 man in a team of two memebers means
= [1 man and 1 woman] OR [2 men]

Atmost 1 man in a team of two members
=[Zero man, 2 women] or [1 man, 1 woman]

When "OR" comes, we've to ADD (+) the probabilities.
Total results Is same : 6C2= 15 ways.
Desired results = [1 man 1 woman] (OR)+[ Two men]

Situation #1: One man and One woman

Desired result =8 ways. ( we already did this in Case #3)

Situation #2: Two men

Concept is same as Case #2
There are four men: Jethalal, Mehta-saab, Bhide, Aiyyar
Keep them aside in a seperate 'talent-pool'
How many ways can you pick up 2 actors out of the given 4?
Combination problem
= (4 x 3) / 2 x 1
=6 ways.

Final answer

Probability = Desired result divided by Total results
= (Situation #1 OR situation #2) / total result
= (8+6) / 15 ; because OR means addition (+)
=14/15

Alternative method: 1 Minus

Total sum of all probabilities =1 (according to theory)
We had to select 2 actors out of given 6. So gender wise three situations possible in this 'team'
1. Two men (MM)
2. Two women (FF)
3. One man and One Woman (MF)
Total probability (1)= MM + FM + MF
Our question was Atleast one man hence (MM+FM)

So, Probability of atleast one man
=1 minus probability of two women (FF)
MM +FM =1 - FF

So find the probability to two women getting selected?
Desired result= 2 women
Same as case#2
Keep Anjali and Babita in a separate talent-pool.
How many ways can you select two actresses out of the given two actresses?
Obviously 1 way. (2C2); because you'll have to take both of them!
Total result= already counted 6C2= 15

Probability (FF) = 1/15
So our question
= 1 - (1/15)
=14/15

Compare the answer. IT is same what we got in the first method of Case#4.

Case 5: Not getting selected

This one is very easy but writing it just in case Alternative method of case #4 did not click your mind.
Ques. Direct Asit Modi wants to select one character out of the given six. What is the probability that Anjali will not be selected?
Method 1: Direct method
Total results= 6C1= 6 ways (to select 1 character out of given 6)
Desired results
We don't want Anjali in the selection so we keep Anjali aside and create a new talent pool of five remaining characters
(Jethalal, Mehta-saab, Bhide, Aiyyar and Babita-ji)

Pick any one out of this five and we're done, we'll satisfy the desired result that Anjali is not selected.
So, How many can you pick up one character out of five? = 5 ways (5C1)
Hence
Final probability = desired results divided by total results
=5/6

Indirect Method: One minus other probabilities

According to theory, Total sum of all probabilities =1
So Probability of Anjali NOT getting selected
= 1 minus [Probability of Anjali getting selected]
Just like case #1, Probability of Anjali getting selected is 1/6
=1 - 1/6
=5/6

^Formula: P(E)=1-P(E')

Next Post: Cliched Questions from Probability Topic

mrunalpatel · March 17, 2012, 4:58am

Dice Probability question

Q. Two dice are tossed once. What's the probability that both of them will show even numbers?

Concentrate on one dice only.
A dice has 6 numbers on it : 1,2,3,4,5,6
You toss it once, and one number will appear.
Total results = 6C1= 6 ways.
Desired result: We want even number.
Even Numbers are three: 2,4,6
How many ways can one Even number appear out of the given three? 3C1=3
Probability of one dice showing even number
=Desired result / Total results
= 3C1/6C1
=3/6
=1/2
Probability of two dice showing even numbers
= first dice shows even number (AND) second dice also shows even number
=1/2 x 1/2 ; AND means multiplication
=1/4 ; final answer

Bags and balls: Replacement killers

Q. A bag contains four black and five red balls, if three balls are picked at random one after another without replacement, what is the chance that they're all black?
Total balls = four black + five red = 9 balls
Shorter Method
Total Results: How many ways can you pick 3 balls out of 9 balls?:
Come on this is just another "Combination" problem, 9C3= (9 x 8 x 7) / (3 x 2 x1) =84.
Desired Result: How many ways can you pick 3 balls out of given 4 black balls?: 4C3 =4 ; (choosing 3 out of given 4, is same as rejecting one out of given 4 means you can do it 4 ways)
Final Probability
=Desired / Total
=4C3/9C3
=4/84
=1/21

Longer Method and Explanation for this Bags and Balls problem

We have to pick up three balls one after another and we want them to be black. Means 1st picking black AND 2nd picking is black and 3rd picking is black; "And" means multiply.

It specifically mentions that "without replacement", meaning everytime balls will decrease and our total events will change accordingly.
1st pick

Total results = pick one out of given 9= 9 ways
Desired= pick one out of given 4 black=4 ways
Hence, 1st picking probability =4/9

2nd pick

Now we've total 8 balls left, 3 of them are black
Run the same procedure of first pick: and you get probability 3/8
Same way third pick: 2/7

Final probability

=first pick black AND x second pick black AND third pick black; ("And" means multiplication)
=(4/9) x (3/

x (2/7)
=1/21
Now compare this with the shorter method explained previously Essentially (4/9) x (3/

x (2/7) is what you get when you expand the Formula: 4C3 / 9C3. (Because 3! factorial will cancel eachother)

Balls WITH Replacement

Q. A bag contains four black and five red balls, if three balls are picked at random one after another WITH replacement, what is the chance that they're all black?It is the same questions like previous one but, WITH replacement means you pick up a ball note down its color and then put it back in the bag again. So Total Number of balls remain same for each event. And Hence probability of picking a black ball (4/9) remains the same in every case.
1st Pick up : 4/9 ; as calculated above under "1st Pick" topic
2nd Pick up: 4/9 ;because we put the ball back in the bag, So probability is same as "1st Pick".
3rd Pick up: 4/9 ;because we put the ball back in the bag.

So final probability
=1st x 2nd x 3rd
=4/9 x 4/9 x 4/9
=Cube of 4/9
=64/729

omen25 · April 14, 2012, 8:00pm

Can anyone please help to solve this question

Q . Find the number of selections that can be made by taking 4 letters from the word INKLING?

vyomconfused · April 15, 2012, 5:27am

Can anyone please help to solve this question

Q . Find the number of selections that can be made by taking 4 letters from the word INKLING?

alphabets in the word I,N,K,L,G where IandN are repeated.
so we will makes cases here,
1.All are different
5c4*4!

2.2are same and 2 are different

2c1*4c2*4!/2!

3.2same 2same

2c2*4!/2!2!

add all of them.

omen25 · April 15, 2012, 8:21am

alphabets in the word I,N,K,L,G where IandN are repeated.
so we will makes cases here,
1.All are different
5c4*4!

2.2are same and 2 are different

2c1*4c2*4!/2!

3.2same 2same

2c2*4!/2!2!

add all of them.

Thanks for the excellent explanation.....

aniiii · April 18, 2012, 11:54am

subscribe me

lktyagi · April 26, 2012, 6:50pm

Yeah exactly...i was wondering why people are not using this method (n+r-1 )C (r-1)becuase this is exactly like A+B+C+D = 6 , and we have to get 6 disc finally.....
But m still confused why 4 ^ 6 is wrong. Please suggest.

jain4444 · April 27, 2012, 8:42am

Yeah exactly...i was wondering why people are not using this method (n+r-1 )C (r-1)becuase this is exactly like A+B+C+D = 6 , and we have to get 6 disc finally.....
But m still confused why 4 ^ 6 is wrong. Please suggest.

here A + B + C + D should be equal to 6

according to your way , if we take A = 6 , B = 6 , C = 6 and D = 6

then its 6 + 6 + 6 + 6 = 24 not 6

sagnik2015 · May 9, 2012, 4:20pm

Is the answer (5*6)*(2^12)

Explanation: No of ways of choosing atleast 1 Rock and 1 Carnatic song=(5*6)
Now,
there are 2 choises for all the
remaining 12 songs i.e we either include it in the album or we dont.Thus the no of
ways of choosing =2^12.
Thus total no of ways=(5*6)*(2^12)

amrita.sarkar · May 25, 2012, 9:55pm

hey can anyone explain the concept of ranking!
will be a great favour. i get pulled down because of that

viswes · June 2, 2012, 7:01am

Hi,

Say, C = Consonent, V=Vowel
We have
_ C _ C _ C _ C _

Number of ways to arange consonents = 4!
Now, there are 5 places where we can place vowels (indicated by a dash)
So, number of ways to arrange 3 vowels = 5P3

So, total arrangements = 4! * 5P3 = 1440

P.S.: This problem is same as 'Number of ways to arrange 4 boys and 3 girls with no girls together'.

When there are only 7 places in the Word rainbow. But in your reply you have given9 places. how is this possible. Can anyone please explain?

vignan · June 4, 2012, 9:38am

viswes Says
When there are only 7 places in the Word rainbow. But in your reply you have given9 places. how is this possible. Can anyone please explain?

@viswes: ThinkAce meant that;

if a vowel comes at the beginning, there wont be any letter at the end, that means the word starts with a vowel and ends with a consonent.

Similarly, if there is a vowel comes at the end of the word, then there wont be any letter in the first blank space, that means this time the word starts with a consonent and ends with a vowel.

mba4mheart · June 4, 2012, 9:48am

superb...........i never knew about this thread.......thanks pagalguy and puys

saikatha · June 7, 2012, 2:15pm

please subscribe me in this thread. i am a cat 2012 aspirant!

mba4mheart · June 7, 2012, 4:11pm

saikatha Says
please subscribe me in this thread. i am a cat 2012 aspirant!

What does subscribe means????
I have no clue that is why I am asking:shock: