Permutations and Combinations

Synopsis

Fundamental principles of counting

• Multiplication Principle
  If an event can occur in m different ways, following which another event can occur in n different ways, then the total number of occurrences of the events in the given order is m x n. This principle can be extended to any number of finite events. The keyword here is ‘and’.

• Addition Principle
  If there are two jobs such that they can be performed independently in m and n ways respectively, then either of the two jobs can be performed in (m + n) ways. This principle can be extended to any number of finite events. The keyword here is ‘OR’.

• Factorial notation
  The notation ‘n!’ represents the product of first ‘n’ natural numbers i.e. n! = 1 x 2 x 3 x 4 x … x n.

Permutation

• A permutation is an arrangement in a definite order of a number of objects taken some or all at a time. 
• In permutations, the order is important.
• Keyword for permutations is ‘arrangement’.

Number of Permutations

• 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) denoted by nPr.
• The number of permutations of ‘n’ different objects taken ‘r’ at a time, where repetition is allowed is n^r.
• The value of ⁿP_r without repetition is given by  

Permutations of Alike Things

• The number of permutations of ‘n’ objects, taken all at a time, where ‘p’ objects are alike of one kind and ‘q’ objects are alike of second kind such that p + q = n, is given by .
• The number of permutations of ‘n’ objects, where p1 are alike of one kind, p₂ are alike of second kind, … pk are alike of kth kind such that  , is  .
• The number of permutations of ‘n’ objects, where ‘p’ objects are of one kind, ‘q’ are alike of second kind and remaining all are distinct is given by  .
• Assume that there are ‘k’ things to be arranged with repetitions. Let p₁, p₂, p₃, … p_k are integers such that the first object occurs exactly p₁ times, the second occurs exactly p2 times…, then the total number of permutations of these ‘k’ objects with the above condition is   .

Circular permutation

• When clockwise and anti-clockwise arrangements are different:
  Number of permutations: (n - 1)!
• When clockwise and anti-clockwise arrangements are the same:
  Number of permutations:  
• Number of circular permutations of n different things taken r at a time when clockwise and anticlockwise arrangements are taken as different is  .
• Number of circular permutations of n different things, taken r at a time, when clockwise and anticlockwise arrangements are not different  .

Permutation under restrictions

Selecting and arranging r distinct objects from n

• When ‘k’ particular things are always to be included.
  Number of permutations: 
• When a particular thing is always to be included (k = 1).
  Number of permutations:  
• When ‘k’ particular things are never included.
  Number of permutations: 
• When a particular thing is never included.
  Number of permutations:  
• When ‘l’ particular things always come together.
  Number of permutations: (n -l + 1)! x l!
• When ‘l’ particular things never come together.
  Number of permutations: n! -(n - l + 1)! x l!

• Combination
  Combination is a way of selecting objects from a group, irrespective of their arrangements.
  Keyword for combination is ‘selection’.

• Difference between Permutations and Combinations:
  
  
  
  

Number of Combinations

• The number of combinations or selection of ‘r’ different objects out of ‘n’ given different objects is ⁿC_r, which is given by  
• Number of combinations of ‘n’ different things, without taking any of them, is considered to be 1.
• Counting combinations is merely counting the number of ways in which some or all objects are selected at a time.
• Selecting ‘r’ objects out of ‘n’ objects is the same as rejecting (n – r) objects, so ⁿC_n – r ꞊ _ⁿCr.
• Ways of selecting one or more things at a time is
  Number of combinations:  ⁿC₁+ ⁿC₂+ C_n = 2^n-1
• When ‘k₁’ alike objects of one kind, ‘k₂’ alike objects of the second kind … ‘k_n’ alike objects of the nth kind.
  Number of combinations:  (k₁+1)(_k2+1)…(k_n+1)-1
• When ‘k₁’ alike objects of one kind, ‘k₂’ alike objects of the second kind … ‘k_n’ alike
  objects of the nth kind and rest ‘p’ elements are different.
  Number of combinations:(k₁+1)(k₂+1)…(_kn+1)]2^p-1  

Combinations under restriction

• When ‘k’ particular things are always to be included
  Number of combinations: ^(n-k)C_(r-k)
• When a particular thing is always to be included (k = 1)
  Number of combinations: ^(n-1)C_(r-1) 
• When ‘k’ particular things are never included
  Number of combinations:^(n-k)C_r
• When ‘k’ particular things never come together
  Number of combinations:ⁿC_r -^(n-k)_C(r-k)

Key Formulae

• n! = 1 x 2 x 3 x …x n or n! = n x (n -1)! 
• n! is defined for positive integers only.
• n! = n(n – 1)(n – 2)! (provided n ³ 2)
• n! = n(n – 1)(n – 2)(n – 3)! (provided n ³ 3)
• 0! = 1! = 1  
• 
• 
• 

• If P_m represents ^m_Pm, then 1+1.P₁+2.P₂+3.P₃+…+n.P_n=(n+1)!  
•  
•  ⁿC_x= ⁿC_y ⟺ x + y = n or x = y
• Pascal’s Rule: If ‘n’ and ‘k’ are non-negative integers such that k ≤ n , then  ⁿC_k+ⁿC_k-1 = ⁿ⁺¹C_k
• If ‘n’ and ‘k’ are non-negative integers such that 1 ≤  k ≤  n  , then  
• If ‘n’ and ‘k’ are non-negative integers such that 1 ≤  k ≤  n , then  k⨯(ⁿC_k)=(n-k+1)⨯ⁿC_k-1
• The greatest among ⁿC₀,ⁿC₁,ⁿC₂,…ⁿc_n is  when ‘n’ is an even natural number.
• The greatest among  ⁿC₀,ⁿC₁,ⁿC₂,…ⁿc_n is  , when ‘n’ is an odd natural number. 
• ⁿP_r = ⁿC_r  r!, 0
• ⁿC₀ = ⁿC_n =1
• ⁿC_n-1 = ⁿC₁ =n
•