Permutations and
Combinations
Fundamental Principles of Counting
There are two Fundamental Principles of Counting
1. Multiplication Principle
If first operation can be performed in m ways and then a second
operation can be performed in n ways. Then, the two operations taken
together can be performed in mn ways. This can be extended to any
finite number of operations.
2. Addition Principle
If an operation can be performed in m ways and another operation,
which is independent of the first, can be performed in n ways. Then,
either of the two operations can be performed in m + n ways. This can
be extended to any finite number of mutually exclusive events.
Factorial
For any natural number n, we define factorial as
n ! or |n = n( n − 1)( n − 2) K 3 × 2 × 1.
The rotation n ! represent the present of first n natural numbers.
Important Results Related to Factorial
(i) 0 ! = 1 ! = 1
(ii) Factorials of negative integers and fractions are not defined.
(iii) n ! = n ( n − 1)! = n( n − 1)( n − 2)!
n!
(iv) = n( n − 1)( n − 2) L (r + 1)
r!
(v) n ! + 1 is not divisible by any natural number between 2 and n.
, Exponent of a Prime p in n!
If p is prime and pr divides n ! , then maximum exponent of prime p in
n ! is given by
n n n
E p( n !) = + 2 + 3 + K
p p p
Permutation
Each of the different arrangement which can be made by taking some
or all of a number of things is called a permutation.
Mathematically The number of ways of arranging n distinct
objects in a row taking r ( 0 < r ≤ n ) at a time is denoted by P ( n , r )
or n Pr .
n!
i.e. n
Pr =
( n − r )!
Properties of Permutation
(i) n
Pn = n ( n − 1) ( n − 2)... 1 = n !
n!
(ii) n
P0 = =1
n!
(iii) n P1 = n
(iv) n
Pn − 1 = n !
n −1 n −2 n −3
(v) n
Pr = n ⋅ Pr −1 = n( n − 1) ⋅ Pr − 2 = n( n − 1)( n − 2) ⋅ Pr − 3
n −1 n −1
(vi) Pr + r ⋅ Pr −1 = Pr
n
n
Pr
(vii) n
= n −r +1
Pr − 1
Important Results on Permutation
(i) The number of permutations of n different things taken r at
a time, when each thing may be repeated any number of times
is n r .
(ii) The number of permutations of n different objects taken r at a
time, where 0 < r ≤ n and the objects do not repeat, is
n( n − 1) ( n − 2) ... ( n − r + 1), which is denoted by n Pr or P ( n , r ).
(iii) The number of permutations of n different things taken all at a
time is n Pn = n ! .
Combinations
Fundamental Principles of Counting
There are two Fundamental Principles of Counting
1. Multiplication Principle
If first operation can be performed in m ways and then a second
operation can be performed in n ways. Then, the two operations taken
together can be performed in mn ways. This can be extended to any
finite number of operations.
2. Addition Principle
If an operation can be performed in m ways and another operation,
which is independent of the first, can be performed in n ways. Then,
either of the two operations can be performed in m + n ways. This can
be extended to any finite number of mutually exclusive events.
Factorial
For any natural number n, we define factorial as
n ! or |n = n( n − 1)( n − 2) K 3 × 2 × 1.
The rotation n ! represent the present of first n natural numbers.
Important Results Related to Factorial
(i) 0 ! = 1 ! = 1
(ii) Factorials of negative integers and fractions are not defined.
(iii) n ! = n ( n − 1)! = n( n − 1)( n − 2)!
n!
(iv) = n( n − 1)( n − 2) L (r + 1)
r!
(v) n ! + 1 is not divisible by any natural number between 2 and n.
, Exponent of a Prime p in n!
If p is prime and pr divides n ! , then maximum exponent of prime p in
n ! is given by
n n n
E p( n !) = + 2 + 3 + K
p p p
Permutation
Each of the different arrangement which can be made by taking some
or all of a number of things is called a permutation.
Mathematically The number of ways of arranging n distinct
objects in a row taking r ( 0 < r ≤ n ) at a time is denoted by P ( n , r )
or n Pr .
n!
i.e. n
Pr =
( n − r )!
Properties of Permutation
(i) n
Pn = n ( n − 1) ( n − 2)... 1 = n !
n!
(ii) n
P0 = =1
n!
(iii) n P1 = n
(iv) n
Pn − 1 = n !
n −1 n −2 n −3
(v) n
Pr = n ⋅ Pr −1 = n( n − 1) ⋅ Pr − 2 = n( n − 1)( n − 2) ⋅ Pr − 3
n −1 n −1
(vi) Pr + r ⋅ Pr −1 = Pr
n
n
Pr
(vii) n
= n −r +1
Pr − 1
Important Results on Permutation
(i) The number of permutations of n different things taken r at
a time, when each thing may be repeated any number of times
is n r .
(ii) The number of permutations of n different objects taken r at a
time, where 0 < r ≤ n and the objects do not repeat, is
n( n − 1) ( n − 2) ... ( n − r + 1), which is denoted by n Pr or P ( n , r ).
(iii) The number of permutations of n different things taken all at a
time is n Pn = n ! .
