# Permutation and Combination – Theory & Concepts

Introduction:
The questions on the area of Permutation and Combination appear in almost all competitive exams. Though this topic might seem cumbersome at first, if analyzed carefully- it is an extension of the various Number System principles or Counting Principles. So, let us first understand the Fundamental Principles of Counting as there are too many concepts with just some minor differences. Every concept is followed by an illustration of that concept, so you will learn not only the concept but also its application. We strongly advise you to go through each and every point given below so as to solve questions on Permutations and Combinations.
###### Fundamental Principle of Counting:
• Multiplication: If there are two jobs such that one of them can be completed in p ways, and after its completion in any one of these p ways, the second job can be completed in q different ways, then the two jobs (in succession) can be completed in p × q ways.
Illustration 1: In a class, there are 15 boys and 10 girls. The teacher wants to select one boy and one girl, so as to represent the class in a function. In how many ways can the teacher make the selection?
Sol: Here the teacher has to perform two jobs:
1. Selecting a boy among 15 boys
2. Selecting a girl among 10 girls.
The first task can be done in 15 ways and the second in 10 ways. By the fundamental principle of multiplication, the total number of ways is: 15 × 10 = 150.
• Addition: If there are two jobs such that they can be accomplished independently in a and b ways respectively, then either of the two jobs can be accomplished in (a + b) ways.
Illustration 2: In a class, there are 15 boys and 10 girls. The teacher wants to select a boy or a girl so as to represent the class in a function. In how many ways can the teacher make the selection?
Sol: Here the teacher has to perform either of the following two jobs.
1. Selecting a boy among 15 boys or
2. Selecting a girl among 10 girls.
The first task can be accomplished in 15 ways and the second in 10 ways. By fundamental principle of addition, either of the two jobs can be accomplished in: 15 + 10 = 25 ways. Hence, the teacher can make the selection of either a boy or a girl in 25 ways.
Note: The above principles of counting can be extended to any finite number of jobs.
###### Permutation Formula and Permutation Examples
Each of the arrangements which can be made by taking some or all of the number of things is called permutation. Go through the following
e.g. ⇒ The permutations of three letters X, Y, Z :
The permutation of three letters X, Y, Z taking all at a time are XYZ, XZY, YZX, ZYX, ZXY, YXZ
⇒ The permutation of three letters X, Y, Z taken two a time:
The required permutations are XY, YX, YZ, ZY, XZ, ZX.
• Permutation Calculator: Permutation of n distinct objects taken ‘r’ at a time {Here r & n are positive integers & 1 ≤ r ≤ n}
is = P(n,r)=nPr=n(n-1)(n-2)_____(n-r+1)
P(n,r)=nPr=(n!/(n-r)!)
Illustration 3: In how many ways can 3 non- identical rings be worn in 5 fingers ?
Sol. Such questions in which things are to be distributed amongst someone or something, NOTE that the things to be distributed always comes in the power.
So total ways of distributing the rings amongst the 5 fingers will be 5^3.The total ways thus come out to be 125.
OR , we can say that there are 5 ways for the first ring, 5 for the second and 5 for the 3rd ring so the total cases would be 5*5*5=125 cases.
Illustration 4: How many four letter words, with or without meaning, can be formed using the letters of the word ‘FATHERLY’ using each letter exactly once (having essentially ‘F’ as one of the letters)?
1. Number of four letter words beginning with ‘F’ = 8-1P4-1 = 7P3
2. Number of four letter words having ‘F’ as 2nd letter = 8-1P4-1= 7P3
3. Number of four letter words having ‘F’ as 3rd letter = 8-1P4-1= 7P3
4. Number of four letter words having ‘F’ as last letter = 8-1P4-1= 7P3
Total number of words = 7P3 + 7P3 +7P3 + 7P3 = 4. 7P3
• Permutation of ‘n’ distinct objects taken ‘r’ at time where a particular object is never taken is  n-1Pr . Here, one particular object (out of n given objects) is never taken. So, we have to find the no. of ways in which r places can be filled with (n – 1) distinct objects. Clearly, the no. of arrangement is n-1Pr.
• Permutation of ‘n’ different objects, taking ‘r’ at a time, in which two specified objects always occur together is 2! (r – 1) n-2Pr-2 Here, if we leave out two specified objects, then the number of permutations of the remaining (n – 2) objects, taking (r – 2) at a time is n-2Pr-2 . Now, consider two specified objects temporarily as a single object and add to each of these n-2Pr-2 permutations which can be done in (r – 1) ways. Thus, the number of permutations becomes (r – 1) n-2Pr-2 . But the two specified things can be put together in 2! ways. Hence, the required number of permutations is 2! (r – 1) n-2Pr-2.
• Permutation of objects (not all distinct): Till now, we have been discussing permutations of distinct objects (taking some or all at a time). Now, we will discuss the permutations of a given number of objects when not all objects are different. The number of mutually distinguishable permutations of ‘n’ things, taken all at a time, of which p are of one kind, q are of second kind, such that p + q = n is (n!/p!q!)
• Permutation (when objects can repeat): The number of permutations of n different things, taken r at a time (when each may be repeated any number of times in each arrangement) is nr.
The concept can be explained by comparing this permutation with the number of ways in which r places can be filled by n different things when each thing can be repeated r times.
The first place can be filled in n ways by any one of the n things. Having filled up the first place, n things are again left; therefore the second place can be filled in n ways.Similarly each of the 3rd, 4th, _ _ _ _ rth place can be filled in n ways. Thus by fundamental principle of counting, the total number of ways of filling ‘r’ places = n × n × n _ _ _ _ _ _ to r factors = nr.
Illustration 5: In how many ways can 4 letters be posted in 3 letter boxes?
Sol: Since each letter can be posted in any one of the three letter boxes, so a letter can be posted in 3 ways. So, the total number of ways in which all four letters can be posted = 34 ways.
• Circular Permutations: Permutation of n distinct objects along a circle can be done in (n – 1)! ways.
Note: This concept can be understood by understanding that n linear permutations when considered along a circle, give rise to one circular permutation. Thus, the required circular permutations = (n!/n)=(n-1)!
Permutation along a circle- clockwise and anticlockwise arrangements, are considered alike.
The number of permutations of n distinct objects- clockwise and anticlockwise arrangements, is similar = ((n-1)!/2)
• Combinations & Combination Formulas: Each of the different selections made by taking some or all of the number of objects, irrespective of their arrangements, is called a combination.
Difference Between Combinations And Permutations:
1. In combinations, only selection is important whereas in the case of permutations, not only the selection but also the arrangement in a particular sequence is considered.
2. In a combination, the order of selected objects is immaterial whereas in a permutation, the order is essential.
3. To find the permutations of n different items, taken ‘r’ at a time: we first select r items from n items and then arrange them. So usually, the number of permutations exceeds the number of combinations.
• Formula for combinations: Combination of n different objects, taken r at a time is given by: C(n, r) = nCr= (n!/(n-r)!r!)
Properties of nCr
Prop I: nCr = nCn-r for 0 ≤ r ≤ n
Prop II: Let n and r be non–negative integers such that r ≤ n. Then nCr + nCr-1 = n+1Cr
Prop III: Let n and r be non–negative integers such that 1 ≤ r ≤ n. Then nCr = (n/r). n-1Cr-1
Selection of one or more items: The number of ways of selecting one or more items from a group of 'n' distinct items is 2n – 1. In making the selection, each item can be dealt with in two ways; it is either selected or rejected and corresponding to each way of dealing with one item, any one of the other items can also be dealt with in 2 ways. So, the total number of ways of dealing with 'n' items is 2n. But these 2n ways also include the case when all the items are rejected. Hence, the required number of ways = 2n – 1.