Permutation-Combinations Workshop for CAT

Factorial
Let n be a positive integer. Then, factorial n, denoted n! is defined as:
n! = n(n - 1)(n - 2) ... 3.2.1.
Solved Examples:
i. We define 0! = 1.
ii. 1! = 1.
iii. 4! = (4 x 3 x 2 x 1) = 24.
iv. 5! = (5 x 4 x 3 x 2 x 1) = 120.


Difference between Permutation & Combination
In English we use the word "combination" loosely, without thinking if the sequence/order of things is important or not. Examples:



"My mock-tail is a combination of  pineapple juice, grapes juice and lime juice" . 
In this case we don't care what order the juices are mixed in, they could also be "grapes juice, pineapple juice and lime juice" or "lime juice, grapes juice and pineapple juice", its the same mock-tail.





" 5178 is my ATM Pin combination ". 
Now in this case we do care for the order. 5187 will not work, nor will 5718, 5781, 1857, 1875 etc. The only sequence which will work is 5178.


In mathematics:
If the order doesn't matter, it is a Combination.
If the order does matter it is a Permutation.
=>     A Permutation is an ordered Combination.


Permutation - The order of arrangement matters
In mathematics permutation means act of rearranging (permuting) objects or values. In simple words: "the different arrangements of a given number of things by taking some or all at a time, are called permutations."
Consider following three fruits which needs to be arranged in a straight line on a thin bench:












What are the different ways one can arrange these 3 fruits on table?
Lets number these fruits as 1. Apple, 2. Mango and 3. Banana.













All possible arrangements of these 3 fruits are:







The number of different arrangements as you could see above is 6 or 3! = 3 • 2 • 1

-The number of permutations of n distinct objects is n×(n − 1)×(n − 2)×⋯×1, which is commonly denoted as "n factorial" and written "n!".
-All possible arrangements of letters of a word is a permutation of its letters. 
-For (a,b,c) or abc number of distinct objects are 3, hence permutation made with the letters a, b, c taking all at a time are 3! = 3*2 = 6 => (abc, acb, bac, bca, cab, cba)



Important Concepts on Permutation:

1. Taken r items at a time
Number of all permutations of n things, taken r at a time, is given by:
    
 nPr = n(n - 1)(n - 2) ... (n - r + 1) = n!/(n-r)! 


Solved Example: 
Question 1: How many different 3-digit numerals can be made from the digits  4, 5, 6, 7, 8 if a digit can appear just once in a numeral?
Answer:  We need to find permutation of 5 distinct numbers taken 3 at a time.
Applying formula for nPr => 5P3 = 5!/(5-3)! = (5*4*3*2*1)/(2*1) = 5*4*3 = 60

 
2 a. Identical Items in arrangement
If x out of n items are identical, then the number of different permutations of the n items is:  n!/x! 
Solved Example: 
Question 2: How many ways can you arrange the letters of the word 'twist'? 
Answer:  We need to find permutation of 5 letters(i,s,t,t,w) of which 2 are identical(t,t).
Applying n!/x! for identical items => 5!/2! = 60

 
2 b. Multiple Identical Items in arrangement
If a set of n items contains p identical items, q identical items, and r identical items etc.., then the total number of different permutations of n objects is:  n!/(p!.q!.r!...) 
Solved Example: 
Question 3: How many can you arrange the letters in the word 'MISSISSIPPI''? 
Answer:  We need to find permutation of 5 letters(I,I,I,I,M,P,P,S,S,S,S) of which 4Is, 2 Ps and 4Ss are identical.
Applying n!/(p!.q!.r!..) for multiple identical items => 11!/(4!.2!.4!) = 34,650

 
3. Conditional/Restrictive Permutation 
There are situations where we need to find out possible arrangements  by keeping some of conditions/restrictions in mind. 
Solved Example: 
Question 4:  Using the letters in the word  " square ", tell how many 6-letter arrangements, with no repetitions, are possible if the  first letter is a vowel? 
Answer:  When working with "arrangements", it is often helpful to put lines down to represent the locations of the items. 
       For this problem, six "locations" are needed for 6-letter arrangements.
       _____  •   _____  •  _____  •  _____  •  _____  •  _____

The first locations must be a vowel (u, a, e).  There are three ways to fill the first location.
       _3_ •  _____ •  _____ •  _____ •  _____ •  _____

After the vowel has been placed in the first location, there are 5 letters left to be arranged in the remaining five spaces.

      _3_ • _5_  • _4_  • _3_  •  _2__1_     or
                        
         3  5P5    =     3  120  =  360

 
4. Circular Arrangements
To understand circular arrangement better below illustration comparing it with linear arrangement would be useful:

1. Lets consider 4 people sitting around a round table and 4 people sitting on a linear bench

2.  Shifting each of the 4 people sitting around round table in clockwise direction we get following arrangements:
Looking at the above illustration we could say that if 4 persons are sitting at a round table, then they can be shifted four times, but these four arrangements will be the same, because the sequence of P1, P2, P3, P4 is same.

3. Now we will compare this with linear arrangement where 4 people P1, P2, P3 & P4 are sitting on a bench.  Shifting each of the 4 people sitting in a row on a bench all the 4 arrangement formed will be different:
 All the above 4 sequences are unique and are different arrangements: 
[P1, P2, P3, P4] , [P4, P1, P2, P3], [P3, P4, P1, P2], [P2, P3, P4, P1]

Thus you can see how results in a circular arrangement differs from linear one.



Number of circular-permutations of ‘n’ different things taken ‘n’ at a time
(a)  When clockwise & anti-clockwise order are considered different
If clockwise and anti clock-wise orders are considered different, then total number of circular-permutations is given by (n-1)!

(b)  When clockwise & anti-clockwise order are not considered different 
If clock-wise and anti-clock-wise orders are taken as not different, then total number of circular-permutations is given by  (n-1)!/2!

Solved Example: 
Question 5: If 6 people are going to sitting at a round table, how many different ways can the group of 6 sit
Answer:  Applying formula (n-1)! = (6-1)! = 120

Question 6:If 6 people are going to sitting at a round table, but Raj will not sit next to Simran, how many different ways can the group of 6 sit? 
Answer:
First Approach
a. Total circular permutations = (6-1)! = 5! = 120. 
b. Ways in which Raj and Simran sit together = 2! * 4! = 2*24 = 48 
Required ways = Total - Together = 120 - 48 = 72. 

Second Approach
a. We have total of 6 places. Fix Simran . Now Raj can't sit at either seat beside her. So number of places where Sam can sit = 5-2 = 3. 
For the other 4 people we can arrange them in 4! ways in 4 seats. 
So total ways = 3 * 4! = 72. 



Number of circular-permutations of ‘n’ different things taken ‘r’ at a time

(c) When clockwise & anti-clockwise order are considered different

If clock-wise and anti-clockwise orders are taken as different, then total number of circular-permutations  =   nPr /r


(d) When clockwise & anti-clockwise order are not considered different

If clock-wise and anti-clockwise orders are taken as not different, then total number of circular – permutation =  nPr/2r



Solved Example:
Question 7: How many necklace of 12 beads each can be made from 18 beads of different colors ? 
Answer:  Here clock-wise and anti-clockwise arrangement s are same.
Applying formula:  nPr/2r
Hence total number of circular–permutations = 18P12/2x12
=18!/(6! x 24)


 
Combinations: The order of arrangement doesn't matters
In mathematics a combination is a way of selecting several things out of a larger group, where  order does not matter.

Number of combinations 

The number of all combinations of n things, taken r at a time is:


nCr = n(n - 1)(n - 2) ... to r factors/r! = n!/(r!(n-r)!)


Important:

Solved Example: 
Question 8: In a class of 10 students, how many ways can a club of 4 students be formed? 
Answer: Applying nCr formula:
=> 10C4 = 10!/(4!*6!) = 21

Question 9: How many factors of 2^4 * 5^3 * 7^4 are odd numbers? ? 
AnswerAny factor of this number would be of the form 2^a * 3^b * 5^c. For the factor to be an odd number, a should be 0. b can take values 0,1, 2,3, and c can take values 0, 1, 2,3, 4. Total number of odd factors = 4 * 5 = 20 


Take Online Test on Permutation-Combinations to evaulate yourself 
Test Consists of 11 Questions
Time Allotted is 16 minutes
Total Mraks is 33
Average cut Off Score 25 out 33

Take Online Test

Please do provide your feedback using the comment box below on the content of this workshop.

  
Also Read:



3 comments:

  1. very useful .keep posting thanks

    ReplyDelete
  2. thanq admin............ i had a doubt at 3. Conditional/Restrictive Permutation _3_ • _5_ • _4_ • _3_ • _2_ • _1_ or

    3 • 5P5 = 3 • 120 = 360 in that why we use 3.5p5 instead of 3!.5p5

    ReplyDelete
  3. Hi Nandha,

    For the word SQUARE, vowels are: A, E and U and
    1st Place as per the conditions given in question its supposed to be a vowel either of A, E or U.
    So we have three choices for 1st place. Here we are not bothered about arrangement as we are just talking about 1st place of the 6 letter word and for a single letter arrangement doesn't come into picture. Hence 3 and not 3!
    Once we have selected a vowel out of A, E and U, we would be left with 5 letters where arrangement would be taken care of.

    Hope this clarifies.

    Cheers!

    ReplyDelete