Revision Notes on Permutations & Combinations

Fundamental Principle of Counting

If one experiment has n possible outcomes and another experiment has m possible outcomes, then there are m × n possible outcomes when both of these experiments are performed simultaneously. In other words, suppose a job has n parts and the job will be completed only when each part is completed. Further, it is known that the first part can be completed in a₁ ways, the second part can be completed in a₂ ways and so on ...... the nth part can be completed in a_n ways. Then the total number of ways of doing the job is a₁a₂a₃ ... a_n. This is also known as the rule of product.

Note: Fundamental Principal of Counting (FPC) is used to calculate the possibilities of an event without actually counting them. Basic steps to be used while applying the FPC: 1. Try to identify the independent events involved in a given problem. 2. Find the number of ways of performing or possibilities of occurrence of an event. 3. Multiply these numbers to get the total number of ways of occurrence of these events.

Permutations

• The concept of permutation is used for the arrangement of objects in a specific order i.e. whenever the order is important, permutation is used.

• The total number of permutations on a set of n distinct objects is given by n! and is denoted as ⁿP_n = n!

• The total number of permutations on a set of n objects taken r at a time is given by ⁿP_r = n!/ (n-r)!

• The number of ways of arranging n objects of which r are the same is given by n!/ r!

• If we wish to arrange a total of n objects, out of which ‘p’ are of one type, q of second type are alike, and r of a third kind are same, then such a computation is done by n!/p!q!r!

• Almost all permutation questions involve putting things in order from a line where the order matters. For example ABC is a different permutation to ACB.

• The number of permutations of n distinct objects when a particular object is not to be considered in the arrangement is given by ^n-1P_r.

• The number of permutations of n distinct objects when a specific object is to be always included in the arrangement is given by r.^n-1P_r-1.

• If we need to compute the number of permutations of n different objects, out of which r have to be selected and each object has the probability of occurring once, twice or thrice… up to r times in any arrangement is given by (n)^r.

• Circular permutation is used when some arrangement is to be made in the form of a ring or circle.

• When ‘n’ different or unlike objects are to be arranged in a ring in such a way that the clockwise and anticlockwise arrangements are different, then the number of such arrangements is given by (n – 1)!

• If r things are taken at a time out of n distinct things and arranged along a circle, then the number of ways of doing this is given by ⁿC_r(r-1)!.

• If clockwise and anti-clockwise are considered to be the same, then the total number of circular permutations is given by (n-1)!/2.

• If n persons are to be seated around a round table in such a way that no person has similar neighbor then it is given by ½ (n – 1)!

• The number of necklaces formed with n beads of different colors = ½ (n – 1)!

• ⁿP₀ =1

• ⁿP₁ = n

• ⁿP_n = n!/(n-n)! = n! /0! = n!/1 = n!

Combinations

• If certain objects are to be arranged in such a way that the order of objects is not important, then the concept of combinations is used.

• The number of combinations of n things taken r (0 < r < n) at a time is given by ⁿC_r = n!/r!(n-r)!

• The relationship between combinations and permutations is ⁿC_r = ⁿP_r/r!

• The number of ways of selecting r objects from n different objects subject to certain condition like:

1. k particular objects are always included =  ^n-kC_r-k

2. k particular objects are never included =  ^n-kC_r

• The number of arrangement of n distinct objects taken r at a time so that k particular objects are

        (i) Always included = ^n-kC_r-k.r!,

        (ii) Never included = ^n-kC_r.r!.

• In order to compute the combination of n distinct items taken r at a time wherein, the chances of occurrence of any item are not fixed and may be one, twice, thrice, …. up to r times is given by ^n+r-1C_r

• If there are m men and n women (m > n) and they have to be seated or accommodated in a row in such a way that no two women sit together then total no. of such arrangements = ^m+1C_n. m! This is also termed as the Gap Method. 

• If we have n different things taken r at a time in form of a garland or necklace, then the required number of arrangements is given by ⁿC_r(r-1)!/2.

• If there is a problem that requires n number of persons to be accommodated in such a way that a fixed number say ‘p’ are always together, then that particular set of p persons should be treated as one person. Hence, the total number of people in such a case becomes (n-m+1). Therefore, the total number of possible arrangements is (n-m+1)! m! This is also termed as the String Method.  

• Let there be n types of objects with each type containing at least r objects. Then the number of ways of arranging r objects in a row is n^r. 

• The number of selections from n different objects, taking at least one =  ⁿC₁ + ⁿC₂ + ⁿC₃ + ... + ⁿC_n = 2ⁿ - 1.  

• Total number of selections of zero or more objects from n identical objects is n+1.

• Selection when both identical and distinct objects are present: 

The number of selections, taking at least one out of a₁ + a₂ + a₃ + ... a_n + k objects, where a₁ are alike (of one kind), a₂ are alike (of second kind) and so on ... a_n are alike (of nth kind), and k are distinct = {[(a₁ + 1)(a₂ + 1)(a₃ + 1) ... (a_n + 1)]2^k} - 1.

• Combination of n different things taken some or all of n things at a time is given by 2ⁿ – 1. 

• Combination of n things taken some or all at a time when p of the things are alike of one kind, q of the things are alike and of another kind and r of the things are alike of a third kind = [(p + 1) (q + 1)(r + 1)….] – 1.

• The number of ways to select some or all out of (p+q+t) things where p are alike of first kind, q are alike of second kind and the remaining t are different is = (p+1)(q+1)2^t – 1.

• Combination of selecting s₁ things from a set of n₁ objects and s₂ things from a set of n₂ objects where combination of s₁ things and s₂ things are independent is given by ^n₁C_s1 x ^n₂C_s2  

• Total number of ways in which n identical items which can be distributed among p persons so that each person may get any number of items is ^n+p-1C_p-1.

• Total number of ways in which n identical items can be distributed among p persons such that each them receive at least one item ^n-1C_p-1

• Some results related to ⁿC_r 

1. ⁿC_r = ⁿC_n-r

2. If ⁿC_r = ⁿC_k, then r = k or n-r = k

3. ⁿC_r + ⁿC_r-1 = ⁿ⁺¹C_r

4. ⁿC_r = n/r  ^n-1C_r-1

5. ⁿC_r/ⁿC_r-1 = (n-r+1)/ r

6. If n is even ⁿC_r is greatest for r = n/2

7. If n is odd, ⁿC_r is greatest for r = (n-1)/2,(n+1)/2

Formation of Groups

• The number of ways in which (m + n) different things can be divided into two groups, one containing m items and the other containing n items is given by

^m+nC_n = (m+n)!/ m!n!

• In the above case, if m = n i.e. the groups are of same size then the total number of ways of dividing 2n distinct items into two equal groups is given by ²ⁿC_n/2!.This can be written as (2n)!/n!n!2!

Remark: The result is divided by 2 in order to avoid repetition i.e. false counting. 

• The total number of ways of dividing (m + n + p) distinct items into three unequal groups m, n, p is (m + n + p)!/ m!n!p!.

• In the above case, if m = n = p, then the total number of ways reduce to (3n)!/(n!)³ 3!

• The number of ways in which ‘l’ groups of n distinct objects can be formed in such a way that ‘p’ groups are of object n₁, q groups of object n₂ are given by

• n!/ (n₁)!^p(n₂)!^q(p!)(q!)

• If (a + b + c) distinct items are to be divided into 3 groups and then distributed among three persons, then the number of ways of doing this is 

(a + b + c)!. 3!/ a!b!c!

Problems Based on Number Theory

• Number of divisors

If N = p₁^α1 p₂^α2 ….. p_k^αk, then

Number of divisors = Number of ways of selecting zero or more objects from the group of identical objects (α₁+1)( α₂+1)…(α_k+1)

This includes 1 and N also.

All divisors excluding 1 and N are called Proper divisors.

• Sum of divisors:

If N = p₁^α1 p₂^α2 ….. p_k^αk, then sum of divisors of N is

(1+ p₁ + p₁² +…+ p₁^α1) × (1 + p₂ + p₂² +…+ p₂^α2) ….. (1 + p_k + p_k² +…+ p_k^αk)

= 

• Number of ways of putting N as a product of two natural numbers is

If n is not a perfect square = ½ (a₁ + 1)(a₂ + 1) ….. (a_k +1)

If n is  a perfect square = ½ [(a₁ + 1)(a₂ + 1) ….. (a_k +1) + 1].

Derangement and Results on Points

• If n things are arranged in a row, then the number of ways in which they can be deranged so that r things occupy wrong places while (n-r) things occupy their original places, is

= ⁿC_n-r D_r, where 

D_r =

• If n things are arranged in a row, the number of ways of deranging them so that none of them occupies its original place, is

= ⁿC₀ D_n 

= 

• If there are n points in plane put of which m (< n) are collinear, then the following results hold good:

1.  Total number of different straight lines obtained by joining these n points is

ⁿC₂ – ^mC₂ +1

2.  Total number of different triangles formed by joining these n points is ⁿC₃ – ^mC₃

3. Number of diagonals in polygon of n sides is ⁿC₂ – n

4. If m parallel lines in a plane are intersected by a family of other n parallel lines. Then total number of parallelograms so formed is ^mC₂ × ⁿC₂

5. Number of triangles formed by joining vertices of convex polygon of n sides is ⁿC₃ of which

6. Number of triangles having exactly 2 sides common to the polygon = n

7. Number of triangles having exactly 1 side common to the polygon = n(n-4)

8. Number of triangles having no side common to the polygon =