The Best Blog for SSC CGL, Banking, UPSC and other competitive exams.

Monday, 12 February 2018

Important Concepts and Formulas - Permutations and Combinations


Important Concepts and Formulas - Permutations and Combinations


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.
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(n1)(n2)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
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.
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 = n!(nr)! =n(n1)(n2)...(nr+1) where 0rn
Special Cases
nP0 = 1
nPr = 0 for r>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!
Number of combinations of n distinct things taking r at a time ( nCr) can be given by
nCr = n!(r!)(nr)! =n(n1)(n2)(nr+1)r! where 0rn
Special Cases
nC0 = 1
nCr = 0 for r>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 (nr)
Examples
8C2 = 8×72×1 = 28
5C45×4×3×24×3×2×1 = 5

Permutations under RestrictionsCase 1: When s particular things are always to be included
Number of permutations of n distinct things taking r at a time, when s particular things are always to be included in each arrangement, is
(n-s)C(r-s) × r!

Derivation of the formula
(r−s) objects can be selected from the (n−s) objects in (n-s)C(r-s) ways.

s objects can be selected from s objects only 1 way.

Totally r objects are selected and these can be arranged in r! ways.

Total number of arrangements (n-s)C(r-s) × r!

Alternative Form
Some text books give the formula as (n-s)P(r-s) × rPs which is same as (n-s)C(r-s) × r!

(n-s)C(r-s) × r! =(ns)!×r![ns(rs)]!×(rs)! =(ns)!×r!(nr)!×(rs)!

(n-s)P(r-s) × rPs =(ns)![ns(rs)]!×r!(rs)! =(ns)!×r!(nr)!×(rs)!

As you can see, both these formulas are indeed the same.
Number of permutations of n distinct things taking r at a time, when a particular thing is always to be included in each arrangement, is
(n-1)C(r-1) × r!

Derivation of the formula is similar to that of case 1.

Alternative Form
As we have seen for case 1, the same formula can also be expressed as (n-1)P(r-1) × r
Number of permutations of n distinct things taking r at a time, when s particular things are never included is
(n-s)Cr × r!

Derivation of the formula
Remove the s objects which are never included and we are left with (n-s) objects. r objects can be selected from these (n−s) objects in (n-s)Cr ways.

r objects can be arranged in r! ways.

Total number of arrangements
(n-s)Cr × r!
Number of permutations of n distinct things taking r at a time, when a particular thing is never included, is
(n-1)Cr × r!

Derivation of the formula is similar to that of case 3.
Number of permutations of n distinct things taking them all at a time, when m particular things always come together, is
(n-m+1)! × m!

Derivation of the formula
Group these m objects and consider it as a single object. Then the total number objects = (n-m+1). These (n-m+1) objects can be arranged in (n-m+1)! ways

m objects can be arranged in m! ways.

Total number of arrangements = (n-m+1)! × m!
Number of permutations of n distinct things taking them all at a time, when m particular things never come together, is
n! - (n – m + 1)! × m!

Derivation of the formula
Total number of arrangements possible using n distinct objects taking all at a time = n!

Number of arrangements of n distinct things taking all at a time, when m particular things always come together, is
(n-m+1)! × m!      (As we have seen in case 5)

Hence, number of permutations of n distinct things taking all at a time, when m particular things never come together
= n! - (n-m+1)! × m!

More Concepts and Formulas - PermutationsPermutations of objects when all objects are not distinct
Number of ways in which n things can be arranged taking them all at a time, when p1 of the things are exactly alike of 1st type, p2 of them are exactly alike of a 2nd type ... pr of them are exactly alike of rth type and the rest all are distinct is
n!p1!  p2!    pr!
Number of permutations of n distinct things taking r at a time when each thing may be repeated any number of times is nr
Number of circular permutations (arrangements) of n distinct things
=(n1)!
Number of circular permutations (arrangements) of n distinct things, when clockwise and anticlockwise arrangements are not different (i.e., when observations can be made from both sides)

Useful Relations - Permutations and Combinations
n! = n.(n-1)!

nCr = nPrr!
nPn = n!
nP0 = 1
nP1 = n
nPn = nPn - 1
nPr = n(n-1Pr-1)
nCr = nC(n - r)
Example
8C6 = 8C2 =8×72×1=28
nCn = 1
nC0 = 1
nCr-1 + nCr =   (n+1)Cr   (Pascal's Law)
nCrnCr-1=n-r+1r
nC0 + nC1 + nC2 + ... + nCn = 2n
Example
4C0 + 4C1 + 4C2 + 4C34C4 =24=16
If  nCx = nCy  then either x = y or (n-x) = y
(a) The number of selections of r objects out of n identical objects is 1
(b) Total number of selections of zero or more objects from n identical objects is n+1.

Geometrical Figures - Permutations and Combinations
In this chapter, we are dealing with formulas related to geometrical figures using the principles of permutations and combinations.

Number of triangles that can be formed by joining the vertices of a polygon of n sides
nC3

Number of quadrilaterals that can be formed by joining the vertices of a polygon of n sides
nC4

Suppose there are n points in a plane out of which m points are collinear. Number of triangles that can be formed by joining these n points as vertices
nC3 - mC3

Suppose there are n points in a plane out of which no three points are collinear. Number of triangles that can be formed by joining these n points
nC3

Suppose there are n points in a plane out of which m points are collinear. Number of straight lines that can be formed by joining these n points
nC2 - mC2 + 1

Suppose there are n points in a plane out of which no points are collinear. Number of straight lines that can be formed by joining these n points
nC2

Number of rectangles that can be formed by using m horizontal lines and n vertical lines
mC2 × nC2

Number of diagonals that can be formed by joining the vertices of a polygon of n sides

More Formulas in Permutations and Combinations
If all possible n digit numbers using n distinct non-zero digits are formed, sum of all the numbers so formed
=(n1)! × (sum of the n digits) × (111 ... n times)
Number of handshakes

Suppose there are n persons present in a party and every person shakes hand with every other person. Then, total number of handshakes
nC2=n(n1)2
Derangements

Any change in the existing order of things is called a derangement.

If n things are arranged in a row, number of ways in which they can be deranged so that none of them occupies its original place is

n!(111!+12!13!++(1)n1n!) 

Counting non-negative integral solutionsNumber of non-negative integral solutions of equation x1+x2++xn=k

= Number of ways in which k identical balls can be distributed into n distinct boxes

=(k+n1n1) = (k+n-1)C(n-1)
Counting positive integral solutionsNumber of positive integral solutions of equation x1+x2++xn=k

= Number of ways in which k identical balls can be distributed into n distinct boxes where each box must contain at least one ball

=(k1n1) = (k-1)C(n-1)
Example 1: Find number of non-negative integral solutions of the equation
x1+x2+x3+x4=7
One solution is x1=3,x2=3,x3=0,x4=1

Another solution is x1=1,x2=0,x3=3,x4=3

Note that x1=1,x2=0,x3=0,x4=8 is not a solution because each xi must be a non-negative integer.

Total number of solutions
(k+n-1)C(n-1) = (7+4-1)C(4-1)10C3 = 120

Example 2: Find number of positive integral solutions of the equation
x1+x2+x3=15
Solution 1
Using the formula, required number of solutions
(k-1)C(n-1) = (15-1)C(3-1) = 14C2 = 91
Solution 2
Give one to x1, one to x2 and one to x3.
Remaining quantity is 15-3=12 which is to be distributed to x1,x2 and x3
Therefore, required number of solutions
= number of non-negative integral solutions of
x1+x2+x3=12
(k+n-1)C(n-1) = (12+3-1)C(3-1) = 14C2 = 91

Example 3: A lift starts at the basement with 10 people (6 men and 4 women, excluding the operator) and all get out by the time lift reaches 5th floor. Find the number of ways in which the operator could have perceived the people leaving the lift if all people look alike to the operator?
Required number of ways (knowledgPhilic.in)
= Number of non-negative integer solutions to x1+x2+x3+x4+x5=10
(k+n-1)C(n-1) = (10+5-1)C(5-1) = 14C4 = 1001
Let x1,x2,,xm be integers.

Then the number of solutions to the equation
x1+x2++xm=n
subject to the conditions a1x1b1,a2x2b2, ,amxmbm

is equal to the coefficient of xn in

Distributing Balls into Boxes
Here, we are counting the number of ways in which k balls can be distributed into n boxes under various conditions.
The conditions which are generally asked are
1. The balls are either distinct or identical.
2. The boxes are either distinct or identical.
3. No box can contain more than one ball or any box may contain more than one ball.
4. No box can be empty or any box can be empty.
This is an area which many students choose to ignore. However these concepts will help us in solving many advanced problems in permutations and combinations.
We can use the principles of permutations and combinations to deal with problems of distributing balls into boxes. The concept of identical boxes are more complicated and generally studied in detail in combinatorics.
The table below explains the number of ways in which k balls can be distributed into n boxes under various conditions. All the below mentioned cases are derived under the assumption that the order in which the balls are placed into the boxes is not important. (i.e., if a box has many balls, the order of the balls inside the box is not important). 
Distribution ofHow many balls boxes can contain
k Ballsinto n BoxesNo Restrictions≤ 1
(At most one)
≥ 1
(At least one)
= 1
(Exactly one)
DistinctDistinctnk

(formula 1)
nPk

(formula 2)
S(k,n) × n!

(formula 3)
nPn = n! if k = n
0 if k ≠ n
(formula 4)
IdenticalDistinct(k+n-1)C(n-1)

(formula 5)
nCk

(formula 6)
(k-1)C(n-1)

(formula 7)
1   if k = n
0   if k ≠ n
(formula 8)
DistinctIdenticali=1nS(k,i)
(formula 9)
1   if k ≤ n
0   if k > n
(formula 10)
S(k,n)

(formula 11)
1   if k = n
0   if k ≠ n
(formula 12)
IdenticalIdenticali=1nP(k, i)
(formula 13)
1   if k ≤ n
0   if k > n
(formula 14)
P(k, n)

(formula 15)
1   if k = n
0   if k ≠ n
(formula 16)
S(k,n), Stirling number of the second kind can be defined as
S(k,n)=1n!i=0n1(1)inCi(ni)k
=1n![nC0(n0)knC1(n1)k +nC2(n2)k++(1)n1nCn1(1)k]

Special Cases
S(0,0) = 1
S(k,0) = 0 for k ≥ 1
S(k,n) = 0 for k < n
P(k,n) = The number of partitions of the integer k into n parts.

Formula for P(k,n) is much harder than that of S(k, n). The following examples will explain how we can find the value of P(k,n).

What is the value of P(6,3) ?

The partitions of 6 into 3 parts are
4 + 1 + 1
3 + 2 + 1
2 + 2 + 2
(Note that 4 + 1 + 1,  1 + 4 + 1,  1 + 1 + 4 are same. Similarly we need to consider all other cases as well)

Hence the number of partitions of 6 into 3 parts = 3
=> P(6,3) = 3

What is the value of P(6,2) ?

The partitions of 6 into 2 parts are
1 + 5
2 + 4
3 + 3
Hence the number of partitions of 6 into 2 parts = 3
=> P(6,2) = 3

What is the value of P(6,1) ?

Here, we count the number of partitions of 6 into 1 part.
Clearly the number of such partitions = 1
=> P(6,1) = 1

Now try to find out the value of P(6,4)

The partitions of 6 into 4 parts are
1 + 1 + 1 + 3
1 + 2 + 2 + 2
Hence the number of partitions of 6 into 4 parts = 2
=> P(6,4) = 2

Special Cases
P(0, 0) = P(k, k) = P(k, k-1) = P(k, 1) = 1

1. Division and Distribution of Distinct Objects
Number of ways in which n distinct things can be divided into r unequal groups containing a1, a2, a3, ......, ar things (different number of things in each group and the groups are unmarked, i.e., not distinct)

nCa1 × (n-a1)Ca2 × ... × (n-a1-a2 - ... -ar-1)Car
=n!a1! a2! a3!  ar!

(Note that a1+a2+a3++ar=n)
Number of ways in which n distinct things can be distributed among r persons such that one person get a1 things, another person get a2 things, ... and another person gets ar things(each person gets different number of things)

= Number of ways in which n distinct things can be divided into r unequal groups containing a1, a2, a3, ......, ar things (different number of objects in each group and the groups are numbered, i.e., distinct)

=n! r!a1! a2! a3! ... ar!

(Note that a1+a2+a3++ar=n)
Number of ways in which m×n distinct things can be divided equally into n groups (each group will have m things and the groups are unmarked, i.e., not distinct)

=(mn)!(m!)n n!
Number of ways in which m×n distinct things can be distributed equally among npersons (each person gets m number of things)

= Number of ways in which m×n distinct things can be divided equally into n groups(each group will have m things and the groups are numbered, i.e., distinct)

=(mn)!(m!)n
2. Division and Distribution of Identical Objects
Number of ways in which n identical things can be divided into r groups, if blank groups are allowed (here groups are numbered, i.e., distinct)

= Number of ways in which n identical things can be distributed among r persons, each one of them can receive 0,1,2 or more items

(n+r-1)C(r-1)
Number of ways in which n identical things can be divided into r groups, if blank groups are not allowed (here groups are numbered, i.e., distinct)

= Number of ways in which n identical things can be distributed among r persons, each one of them can receive 1,2 or more items

(n-1)C(r-1)

Combinations under Restrictions
Number of combinations of n distinct things taking r at a time, when s particular things are always to be included in each selection, is
(n-s)C(r-s)
Number of combinations of n distinct things taking r at a time, when a particular thing is always to be included in each selection, is
(n-1)C(r-1)
Number of combinations of n distinct things taking r at a time, when s particular things are never included in any selection, is
(n-s)Cr
Number of combinations of n distinct things taking r at a time, when m particular things never come together in any selection, is
nCr - (n-m)C(r-m)

More Concepts and Formulas - Combinations
Number of combinations of n distinct objects taking r at a time when each object may be repeated any number of times
(n+r-1)Cr
Number of ways in which one or more objects can be selected from n distinct objects (i.e., we can select 1 or 2 or 3 or … or n objects at a time)
nC1 + nC2 + ... + nCn = 2n - 1
Number of ways in which one or more objects can be selected out of S1 alike objects of one kind, S2 alike objects of second kind and S3 alike objects of third kind
= (S1 + 1)(S2 + 1)(S3 + 1) - 1
The above formula can be generalized as follows.
Number of ways in which one or more objects can be selected out of S1 alike objects of one kind, S2 alike objects of second kind , S3 alike objects of third kind and so on ... Sn alike objects of nth kind
= (S1 + 1) (S2 + 1)(S3 + 1)...(Sn + 1) - 1
Number of ways in which one or more objects can be selected out of S1 alike objects of one kind, S2 alike objects of second kind and rest p different objects
= (S1 + 1)(S2 + 1)2p - 1
The above formula can be generalized as follows.
Number of ways in which one or more objects can be selected out of S1 alike objects of one kind, S2 alike objects of second kind and so on ... Sn alike objects of nth kind and rest p different objects
 = (S1 + 1) (S2 + 1) ... (Sn + 1) 2p - 1
Share:

0 comments: