Important Concepts and Formulas - Permutations and Combinations 1. Multiplication Theorem (Fundamental Principles of Counting)

If an operation can be performed in @@m@@ different ways and following which a second operation can be performed in @@n@@ different ways, then the two operations in succession can be performed in @@m × n@@ different ways.

2. Addition Theorem (Fundamental Principles of Counting)

If an operation can be performed in @@m@@ different ways and a second independent operation can be performed in @@n@@ different ways, either of the two operations can be performed in @@(m+n)@@ ways.

3. Factorial

Let @@n@@ be a positive integer. Then @@n@@ factorial can be defined as
@@n!=n(n-1)(n-2)\cdots 1@@

Examples

@@5!=5×4×3×2×1=120\\~\\3!=3×2×1=6@@

Special Cases

@@0! = 1\\~\\1! = 1@@

4. Permutations

Permutations are the different arrangements of a given number of things by taking some or all at a time.

Examples

All permutations (or arrangements) that can be formed with the letters a, b, c by taking three at a time are (abc, acb, bac, bca, cab, cba)

All permutations (or arrangements) that can be formed with the letters a, b, c by taking two at a time are (ab, ac, ba, bc, ca, cb)

5. Combinations

Each of the different groups or selections formed by taking some or all of a number of objects is called a combination.

Examples

Suppose we want to select two out of three girls P, Q, R. Then, possible combinations are PQ, QR and RP. (Note that PQ and QP represent the same selection.)

Suppose we want to select three out of three girls P, Q, R. Then, only possible combination is PQR

6. Difference between Permutations and Combinations and How to identify them

Sometimes, it will be clearly stated in the problem itself whether permutation or combination is to be used. However if it is not mentioned in the problem, we have to find out whether the question is related to permutation or combination.

Consider a situation where we need to find out the total number of possible samples of two objects which can be taken from three objects P, Q, R. To understand if the question is related to permutation or combination, we need to find out if the order is important or not.

If order is important, PQ will be different from QP, PR will be different from RP and QR will be different from RQ

If order is not important, PQ will be same as QP, PR will be same as RP and QR will be same as RQ

Hence,
If the order is important, problem will be related to permutations.
If the order is not important, problem will be related to combinations.

For permutations, the problems can be like "What is the number of permutations the can be made", "What is the number of arrangements that can be made", "What are the different number of ways in which something can be arranged", etc.

For combinations, the problems can be like "What is the number of combinations the can be made", "What is the number of selections the can be made", "What are the different number of ways in which something can be selected", etc.

pq and qp are two different permutations, but they represent the same combination.

Mostly problems related to word formation, number formation etc will be related to permutations. Similarly most problems related to selection of persons, formation of geometrical figures, distribution of items (there are exceptions for this) etc will be related to combinations.

7. Repetition

The term repetition is very important in permutations and combinations. Consider the same situation described above where we need to find out the total number of possible samples of two objects which can be taken from three objects P, Q, R.

If repetition is allowed, the same object can be taken more than once to make a sample. i.e., PP, QQ, RR can also be considered as possible samples.

If repetition is not allowed, then PP, QQ, RR cannot be considered as possible samples.

Normally repetition is not allowed unless mentioned specifically.

8. Number of permutations of n distinct things taking r at a time

Number of permutations of n distinct things taking r at a time can be given by

nPr = @@\dfrac{n!}{(n - r)!}@@ @@= n(n-1)(n-2)...(n-r+1) \quad @@ where @@0 \le r \le n@@

Special Cases
nP0 = 1
nPr = 0 for @@r \gt n@@

nPr is also denoted by P(n,r). nPr has importance outside combinatorics as well where it is known as the falling factorial and denoted by (n)r or nr

Examples

8P2 = 8 × 7 = 56
5P4= 5 × 4 × 3 × 2 = 120

9. Number of permutations of n distinct things taking all at a time

Number of permutations of n distinct things taking them all at a time
= nPn = n!

10. Number of Combinations of n distinct things taking r at a time

Number of combinations of n distinct things taking r at a time ( nCr) can be given by
nCr = @@\dfrac{n!}{(r!)(n - r)!}@@ @@=\dfrac{n(n-1)(n-2)\cdots(n-r+1)}{r!}\quad @@ where @@0 \le r \le n@@

Special Cases
nC0 = 1
nCr = 0 for @@r \gt n@@

nCr is also denoted by C(n,r). nCr occurs in many other mathematical contexts as well where it is known as binomial coefficient and denoted by @@\dbinom{n}{r}@@

Examples

8C2 = @@\dfrac{8 \times 7}{2 \times 1}@@ = 28

5C4= @@\dfrac{5 \times 4 \times 3 \times 2}{4 \times 3 \times 2 \times 1}@@ = 5

 
 
 
Comments(19) Sign in (optional)
showing 1-10 of 19 comments,   sorted newest to the oldest
sreekanth
2015-12-18 07:08:58 
I have a doubt the number of ways to wear 6 ring in 4 fingers is 4^6 but why not 6^4
(0) (0) Reply
sam
2015-12-22 12:56:50 
We have to think it in this way.
1st ring can go into any of the 4 fingers
2nd ring can go into any of the 4 fingers
3rd ring can go into any of the 4 fingers
4th ring can go into any of the 4 fingers
5th ring can go into any of the 4 fingers
6th ring can go into any of the 4 fingers

therefore answer is 4*4*4*4*4*4 = 4^6
(0) (0) Reply
Aruparna
2016-08-05 14:47:03 
why don't we see the problem in the following way..?  :
1st finger can have any of the 6 rings
2nd finger can have any of the 6 rings
3rd finger can have any of the 6 rings
4th finger can have any of the 6 rings
(0) (0) Reply
jiju (Junior Maths Expert, careerbless.com)
2016-08-12 21:28:58 
@Aruparna, this argument fails. Suppose first finger has ring A. Then, second finger has only 5 choices (from the 5 remaining rings)

A finger may not contain any ring at all. Similarly, a finger may have more than one ring also. These will also fail as per your argument.

Also note that all the rings are not used based on your calculation.

Suggest to go through discussion00000024329
(0) (0) Reply
Rajan
2016-05-29 03:35:57 
Why not P(6,4)?
(0) (0) Reply
Javed Khan (Senior Math Expert, careerbless.com)
2016-05-29 18:28:22 
@Rajan,  P(6,4)=360 refers to number of different arrangements possible taking 4 rings at a time, from total 6 rings.

Suppose, A,B,C,D,E,F are the rings. Then, these 360 arrangements are the arrangements like ABCD, ABDC, ABCE etc.

But, this is not the required count as per the question. Answer is 4^6=4096. There 4096 arrangements also include the arrangements having more than one ring in the same finger and/or no rings in some fingers.
(0) (0) Reply
Hemant
2015-10-25 09:58:31 
How do I generate Permutation dynamically where number of position are dynamic and per position possible option is again dynamic?

e.g. I want to pick up 4 number  (here 4 number is dynamic) n1n2n3n4
and again for each number position i.e. 1 to 6 possible option will be dynamic.

1 st number could be = 1,2,3
2nd  number could be = 1
3rd number could be = 1,2
4th  number could be = 5,6,7

any algorithm get all those permutation?
(0) (0) Reply
Shiksha
2015-01-12 18:17:16 
Hi,
I have a question, if we have 6 white balls, 3 blue balls and 2 Red balls and we have to pick a selection 4?
a) how many combinations it will be?
b) if always 2 white have to be selected from 4 then how many combinations possible?
(1) (0) Reply
Shraya
2015-08-17 17:09:13 
a). Your head question and part a both depict the same. Picking any four irrespective of the color.
So, 6 + 3 + 2 = 11.

11C4 = $\dfrac{11!}{4!×(11-4)!}=11×10×3=330$

b) The 2nd part i think you didn't give a clarity. Out of 4 if at least two must be white.

then,
picking 4 whites out of 6 whites = 6C4
picking 3 whites with 1 blue or red = 6C3 × 3C1 × 2C1
picking 2 whites with 2 blue = 6C2 × 3C2
picking 2 whites with 2 red = 6C2 × 2C2
picking 2 whites with 1 red 1 blue = 6C2 × 3C1 × 2C1

Now multiply all.
(0) (0) Reply
adha
2015-11-20 04:25:06 
not to multiply all,  you have to sum all here
(0) (0) Reply
12Next Go
showing 1-10 of 19 comments
 
Add a new comment...  (Use Discussion Board for posting new aptitude questions.)

Name:
Email: (optional)
3 + 2 = (please answer the simple math question)

Post Your Comment
X  
View & Edit Profile Sign out
X
Sign in
Google
Facebook
Twitter
Yahoo
LinkedIn
X