Definitions - Formulae:
* Permutation: Each of the arrangements that can be made out of 'n' dissimilar things by taking 'r' things at a time is called a 'permutation', denoted by nPr.
* Combination: Each of the groups or selections that can be made out of 'n' dissimilar things by taking 'r' things at a time is called a 'combination', denoted by nCr.
*Illustration: Consider the four dissimilar letters A, B, C, D. The number of permutations and combinations by taking '2' letters at a time are respectively as follows:
   Permutations: AB, AC, AD, BC, BD, CD
                                  BA, CA, DA, CB, DB, DC
                                  (total 4P2 permutations)
  Combinations: AB, AC, AD, BC, BD, CD
                                  (total 4C2 combinations)

* Observation: Order of the things is important in the formation of permutations while order of the things is not necessary in forming combinations.
* Factorial 'n': The continued product of the first n natural numbers is called factorial n and is denoted as   or n! Therefore,  or n! = 1. 2. 3. 4 ..... (n-2) (n-1) (n).
                                 Also, we have  = n  ;  = 1;  = 1
* First fundamental Principle: If an operation be performed in 'm' different ways and after it has been completed if another operation be performed in 'n' different ways, then the two operations one after other can be completed in 'mn' different ways.
* Formulae: (i) nPr =  (without repetition of things) (0 ≤ r ≤ n)
                                       =  n^r (with repetition of things)
(ii) nPr   = r. (n-1) P(r-1) + (n-1)Pr.  (r ≤ n)
(iii) nPn =  ; nP0 = 1
(iv) nPr = n. (n-1) P(r-1)   (1 ≤ r ≤ n)
(v) n^r - nPr is the number of permutations of 'n' dissimilar things taken 'r' things at a time with atleast one repetition.

(vi) The number of injections from the set A containing 'm' elements into the set B containing 'n' elements is mPn for m ≤ n and 0 for m > n.
(vii) The number of functions from the set Acontaining 'm' elements into the set B containing 'n' elements is nm.
(viii) 2ⁿ - 2 denotes the number of surjections from the set A containing n elements (n > 1) into the set B containing 2 elements.
¤ Circular Permutations: (i) The number of circular permutations of 'n' dissimilar things is  
(ii) In the case of forming garlands of flowers, chains of beads etc., the number of circular permutations is  (n-1)!
        denotes the number of linear permutations of 'n' things in which 'p' things are similar and the rest are different.
*   denotes the number of linear permutations of 'n' things in which 'p' things are of one kind, 'q' things are of second kind, 'r' things are of third kind and the rest are different.

(x) Let 'p' things be similar of one kind, 'q' things be similar of second kind and 'r' things be similar of third kind. Then the number of ways of selecting one or more things out of these (p + q + r) things is (p+1)(q+1)(r+1)-1.

Permutations When Repetitions Are Allowed
Theorem:
Let ‘n’ and ‘r’ be positive integers. If the repetition of things is allowed, then the number of permutations of ‘n’ dissimilar things taken r at a time is.

Proof:
The number of required permutations is equal to the number of ways of filling up r blank places with given n things(repetitions allowed). We prove this by using induction on r. If r = 1, then the number of ways of filling  up one blank using the given n things is n^r−1.  Therefore the result is true for r = 1.  Assume that r > 1 and that the result is true  for r − 1. That is the number of ways of filling  up (r − 1) blank places with the given n things  is. Now suppose n dissimilar things are  given. Now we take r blank places as shown  below.
1 2 3 - - - - - - - - - - - r − 1 r
The blank 1 can be filled with any one of he given n things in n ways. Now we are left  with (r − 1) blanks and n things (because the object used in the first place can be used again). By induction hypothesis the remaining (r − 1) places can be filled with the givenn things in n^r−1 ways. Therefore by fundamental principle, the number of ways of filling up ‘r’ blanks with the given ‘n’ things is n × n^r−1 = n^r
Note: The number of permutations of n dissimilar things taken r at a time with at least one repetition is n^r − ⁿpr

 Solved Problems
1. Find the number of 4 digited numbers thatn can be formed using the digits 1, 2, 4, 5, 7, 8.  When repetition is allowed.
Sol: I       II        III           IV
The no. of ways filling I Place using  1, 2, 4, 5, 7, 8 is = 6
II place using 1, 2, 4, 5, 7, 8 is = 6
III place using 1, 2, 4, 5, 7, 8 is = 6
IV place using 1, 2, 4, 5, 7, 8 is = 6
Required number of arrangement
= 6 × 6 × 6 × 6 = 64 = 1296

2. Find the number of 5 letter words that can be formed using the letters of the word RHYME if each letter can be used any no. of times.
Sol: First blank can be filled by the letter R, H, Y, M, E in 5 ways.
Since repetition is allowed.
Second blank can be filled in 5 ways
Third blank can be filled in 5 ways
Fourth blank can be filled in 5 ways
Fifth blank can be filled in 5 ways
No. of 5 letter words (with repetition)
= 5 × 5 × 5 × 5 × 5 = 55 = 3125

3. The number of functions from set A containing 5 elements into a set B containing 4 elements
Sol: Here n(A) = 5, n(B) = 4
then no. of functions from A to B = n(B)n(A) = 45 = 1024

4. Find the number of injections from set A containing  4 elements into a set B contains 6 elements.
Sol: n(A) = 4, n(B) = 6
No. of injection = n(B)pn(A) = 6P4 = 360

5. Find the number of surjections from a set A containing 6 elements onto a set B containing 2 elements.
Sol: n(A) = 6, n(B) = 2
No. of onto function from A to B = 2n(A) − 2 = 26 − 2 = 64 − 2 = 62

6. Find the no. of 4 digited telephone numbers that can be formed using the digits 1, 2, 3, 4, 5, 6 with at least one digit repeated.
Sol: Using 1, 2, 3, 4, 5, 6
No. of 4 digited numbers with reputation = 64
No. of 4 digited numbers without reputation = 6P4
No. of 4 digited numbers at least one digit repeated = 64 − 6P4 = 936

7. Find the number of 5 digited numbers that can be formed by using the digits 0, 1, 2, 3, 4, 5 if each digit can be used any number of times.
Sol: With repetition
5     6      6      6     6
The ‘Ten Thousands’ place can be filled with 1, 2, 3, 4, 5 in 5 ways.

 Each of the other place can be filled with  0, 1, 2, 3, 4, 5 in 6 ways.
No. of permutations = 5 × 6 × 6 × 6 × 6  = 5 × 64 = 6480

Circular Permutations 

 In circular permutations there are two types of arrangements. One is clock wise and the other is anti-clockwise, since the direction is also important. However in some special cases we treat the clock wise and anti-clock wise arrangements of the same circular permutations as identical.
Theorem:
The number of circular permutations of ‘n’ dissimilar things taken all at a time is (n−1)!.
Proof:
First method: In a circular permutation, there is no first place or beginning place. Hence which thing we use first or which place we fill first does not matter. But how we arrange the remaining objects relative to the first object already placed is to be calculated. Take n places around a circle. Put anyone of the given n things in any of the n places. Now the remaining (n−1) things can be arranged in the remaining (n−1) places in (n−1)! ways. Therefore the number of circular permutations of n things taken all at a time is (n−1)!.

Second method: Let k be the number of circular permutations of n things taken all at a time. This circular permutation gives rise to n linear permutations (either in clock wise or anti clock wise but not both) are as follows
a₁ a₂ a₃                              a_n−1 a_n
a₂ a₃ a₄                             a_n a₁
a₃ a₄ a₅                              a₁  a₂
..................................  ..............

a_na₁ a₂                               a_n−2  a_n−1    
One circular permutation gives n linear permutations  and hence k circular permutations give k × n linear permutations. But we know that the number of linear permutations of n dissimilarthings taken all at a time is n

One circular permutation gives n linear permutations and hence k circular permutations give k × n linear permutations. But we know that the number of linear permutations of n dissimilar
things taken all at a time is n!

Therefore k × n = n!  = >  k=n! /n = n−1 
Note:
In the case of hanging type circular permutation like the garlands of flowers, chains of beads etc., a circular permutation looks like clock wise arrangement from one side and anticlock- wise arrangement (in the same order of elements) from the other side. Hence they will be treated as identical. Therefore, the number
of circular permutations of n things in such  cases is (n−1)!/2
(half of the actual circular permutations).

 Solved Problems
1. Find the number of ways of arranging 7 persons around a circle.
Sol: The no. of ways of arranging 7 persons around a circle is 6! = 720.

2. Find the no. of ways of arranging 4 boys, 3 girls around a circle so that all the girls sit together.
Sol: Let the 3 girls represent 1 unit G. Now 4 boys along with ‘G’ can be arranged in circular manner in 4! ways and 3 girls can interchange among them in 3! ways.
No. of permutation = 4! (3!) = 24 (6) = 144

3. Find the number of ways of arranging 7 gents and 4 ladies around a circular table if no two ladies wish to sit together.
Sol: The seven gents are arranged around a circular table in 6! ways. Now between the gents there are 7 places in which 4 ladies are to be seated in 7P4 ways.
No. of permutations = 6! x ⁷P₄ = 720 × 840 = 604800