PERMUTATION AND COMBINATION

Welcome here and have a good knowledge with our community Gain total knowledge on this topic.

PERMUTATION AND COMBINATION

All possible arrangements of a collection of things, where the order is important.

Example: You want to visit the homes of three friends Alex ("a"), Betty ("b") and Chandra ("c"), but haven't decided in what order. What choices do you have?

Answer: {a,b,c} {a,c,b} {b,a,c} {b,c,a} {c,a,b} {c,b,a} 

If the order does not matter, it is a Combination

A permutation is an arrangement or ordering of a number of distinct objects. For example, the words 'top' and 'pot' represent two different permutations (or arrangements) of the same three letters.

Permutations are for lists (order matters) and combinations are for groups (order doesn't matter). A joke: A "combination lock" should really be called a "permutation lock". The order you put the numbers in matters.

1. Factorial Notation:
   Let n be a positive integer. Then, factorial n, denoted n! is defined as:
   n! = n(n - 1)(n - 2) ... 3.2.1.
   Examples:
   1. We define 0! = 1.
   2. 4! = (4 x 3 x 2 x 1) = 24.
   3. 5! = (5 x 4 x 3 x 2 x 1) = 120.
2. Permutations:
   The different arrangements of a given number of things by taking some or all at a time, are called permutations.
   Examples:
   1. All permutations (or arrangements) made with the letters a, b, c by taking two at a time are (ab, ba, ac, ca, bc, cb).
   2. All permutations made with the letters a, b, c taking all at a time are:
      ( abc, acb, bac, bca, cab, cba)
3. Number of Permutations:
   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)!

   Examples:
   1. ⁶P₂ = (6 x 5) = 30.
   2. ⁷P₃ = (7 x 6 x 5) = 210.
   3. Cor. number of all permutations of n things, taken all at a time = n!.
4. An Important Result:
   If there are n subjects of which p₁ are alike of one kind; p₂ are alike of another kind; p₃ are alike of third kind and so on and p_r are alike of r^th kind,
   such that (p₁ + p₂ + ... p_r) = n.

   Then, number of permutations of these n objects is =	n!
   	(p1!).(p2)!.....(pr!)

5. Combinations:
   Each of the different groups or selections which can be formed by taking some or all of a number of objects is called a combination.
   Examples:
   1. Suppose we want to select two out of three boys A, B, C. Then, possible selections are AB, BC and CA.
      Note: AB and BA represent the same selection.
   2. All the combinations formed by a, b, c taking ab, bc, ca.
   3. The only combination that can be formed of three letters a, b, c taken all at a time is abc.
   4. Various groups of 2 out of four persons A, B, C, D are:
      AB, AC, AD, BC, BD, CD.
   5. Note that ab ba are two different permutations but they represent the same combination.
6. Number of Combinations:
   The number of all combinations of n things, taken r at a time is:

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

   Note:
   1. ⁿC_n = 1 and ⁿC₀ = 1.
   2. ⁿC_r = ⁿC_{(n - r)}
   Examples:

   i.   11C4 =	(11 x 10 x 9 x 8)	= 330.
   	(4 x 3 x 2 x 1)

   ii.   16C13 = 16C(16 - 13) = 16C3 =	16 x 15 x 14	=	16 x 15 x 14	= 560.
   	3!		3 x 2 x 1

Permutations Examples

Permutation is the arrangement of a given set of numbers or things in a certain order. There can be two types of permutation based on if repetition of elements or numbers are allowed or not. The formula for permutation of choosing and arranging non-repeating r$r$ elements from a set of n$n$elements can be given as,
                                             rnP=n!(n−r)!${}_n^r\text{P}=\frac{n!}{(n-r)!}$
Example 1: 

If five digits 1, 2, 3, 4, 5 are being given and a three digit code has to be made from it if the repetition of digits is allowed then how many such codes can be formed.

Solution: 

As repetition is allowed, we have five options for each digit of the code. Hence, the required number of ways code can be formed is, 5×5×5$5\times 5\times 5$ = 125$125$.
Example 2: 

If three alphabets are to be chosen from A, B, C, D and E such that repetition is not allowed then in how many ways it can be done?

Solution: 

The number of ways three alphabets can be chosen from five will be,

35P=5!(5−3)!${}_5^3\text{P}=\frac{5!}{(5-3)!}$ = 5×4×3×2×12×1$\frac{5\times 4\times 3\times 2\times 1}{2\times 1}$ = 60.

Hence, there are 60 possible ways.

Permutations Word Problems

Problem 1: 

In how many ways can the letters of the word APPLE can be rearranged?

Solution: 
Total number of alphabets in APPLE = 5.

Number of repeated alphabets = 2

Number of ways APPLE can be rearranged = 5!2!$\frac{5!}{2!}$ = 60.

The word APPLE can be rearranged in 60 ways.Problem 2: 

10 students have appeared in a test in which the top three will get a prize. How many possible ways are there to get the prize winners?

Solution: 

We need to choose and arrange 3 persons out of 10. Hence, the number of possible ways will be

310P${}_{10}^3\text{P}$ = 10!(10−3)!$\frac{10!}{(10-3)!}$ = 10×9×8$10\times 9\times 8$ = 720$720$.Problem 3: 

Ellie want to change her password which is ELLIE9 but with same letters and number. In how many ways she can do that?

Solution: 

Total number of letters = 6.

Repeated letters = 2 Ls and 2 Es. 

Number of times ELLIE9 can be rearranged = 6!2!2!$\frac{6!}{2!2!}$ = 6×5×3×2×1$6\times 5\times 3\times 2\times 1$ = 180$180$.

But the password need to be changed. So, the number of ways new password can be made = 180−1=179$180-1=179$.Problem 4: 

In how many ways the word HOLIDAY can be rearranged such that the letter I will always come to the left of letter L?

Solution: 

Number of letters in HOLIDAY = 7 and there is no repetition of letters. Hence, the number of ways all letters can be arranged is 7!.

The number of ways the letters are arranged such that I will come left of L will be, 7!2$\frac{7!}{2}$ as in half of the arrangements L will be right of I and in other half it will be on left of I.Problem 5: 
There are 6 people who will sit in a row but out of them Ronnie will always be left of Annie and Rachel will always be right of Annie. In how many ways such arrangement can be done?

Solution: 

The total number of ways of 6 people being seated in a row will be 6!.

Now, with the given constraint the total number of ways will be 6!3!$\frac{6!}{3!}$ = 6×5×4$6\times 5\times 4$ = 120$120$.

It implies that out of 6 people arrangement of arrangement of 3 people is predefined.