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 n P n = n!
 The total number of permutations on a set of n objects taken r at a time is
given by n 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-1
Pr.
 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-1 P 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 n 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)!

 n
P 0 =1
 n
P1 = n
  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 n C r = n!/r!(n-r)!
 The relationship between combinations and permutations is n C r = n 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-k

C r-k
2. k particular objects are never included = C r n-k

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

objects are
(i) Always included = n-k
C r-k .r!,
(ii) Never included = n-k
C 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-1
Cr
 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+1
C 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 n 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 =
n
C 1 + n C 2 + n C 3 + ... + n C n = 2 n - 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 1 + a 2 + a 3 + ... a n + k objects, where
a 1 are alike (of one kind), a 2 are alike (of second kind) and so on ... a n are alike (of nth
kind), and k are distinct = {[(a 1 + 1)(a 2 + 1)(a 3 + 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 n – 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 1 things from a set of n 1 objects and s 2 things from a
set of n 2 objects where combination of s 1 things and s 2 things are independent
is given by n C s1 x n C s21 2

 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-1
C 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-1
C p-1
 Some results related to nCr
1. n C r = n C n-r
2. If n C r = n C k , then r = k or n-r = k
3. n C r + n C r-1 = n+1
Cr
4. n C r = n/r n-1
C r-1
5. C r / C r-1 = (n-r+1)/ r
n n

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

7. If n is odd, n 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+n
C 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 2n 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 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 1 , q groups of object n 2 are given by
 n!/ (n 1 )! p (n 2 )! 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 α1 p 2 α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)( α 2 +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 α2 ….. p k αk , t hen sum of divisors of N is
α1

(1+ p 1 + p 1 2 +…+ p 1 α1 ) × (1 + p 2 + p 2 2 +…+ p 2 α2 ) ….. (1 + p k + p k 2 +…+ 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 + 1)(a 2 + 1) ….. (a k +1)
If n is a perfect square = ½ [(a 1 + 1)(a 2 + 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

= n C n-r D r , where

Dr =

 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

= nC0 Dn
 =
 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
n
C 2 – m C 2 +1
2. Total number of different triangles formed by joining these n points is n C 3 – m C 3
3. Number of diagonals in polygon of n sides is n C 2 – 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 m C 2 × n C 2
5. Number of triangles formed by joining vertices of convex polygon of n sides
is n C 3 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