Permutations

A language, English for example, is something that we use to communicate every day. But have you ever wondered what would happen to our understanding of the English language if we change the order of alphabets which form the words? For example, what if ‘flower’ was spelt as ‘flowre’? Would it make sense to you? No, right? Thus, words in a language are an example of permutation in daily life. They are actually some specific permutations of a collection of alphabets taken together. In the following section let us learn more about permutations.

 

Suggested Videos

 

Permutation

A permutation is a collection or a combination of objects from a set where the order or the arrangement of the chosen objects does matter. In other words, a permutation is an arrangement of objects in a definite order. Since we have already studied combinations, we can also interpret permutations as ‘ordered combinations’.

(Image Source: Wikipedia)

Types of Permutation

Let’s say we have a set of ‘n’ distinct items, out of which we must choose ‘r’ items. We can choose the required items in the following two ways:

• Selection when the repetition of items is allowed
• Selection when the repetition of items is not allowed

Permutation with Repetition

When the repetition of items is allowed, at every step of selection from the set of ‘n’ items, we have all the ‘n’ choices available to us since we can make a choice multiple times. So, for choosing ‘r’ items, we have n choices available to us ‘r’ times. Let us call the event of choosing an item as E:

n(E) = n (the number of ways in which E can take place)

Since this event is taking place ‘r’ times and the act of choosing an item from the available set is always independent of our other choices, we may invoke the Product Rule of Counting here. Using the fundamental principle then, we get,

n(E taking place ‘r’ times) = n^r

This is the permutation formula for calculating the number of permutations possible for the choice of ‘r’ items from a set of ‘n’ distinct items when repetition is allowed.

Permutation without Repetition

In this case, when the repetition of objects is not allowed, we must be careful, not to choose a specific object more than once. Hence our choices after each event get reduced by one. For example, when we begin the selection, for the first object, we have all the ‘n’ choices available to us.

In the next event, however, we have ‘(n-1)’ objects available for choice, since we must not include the object that we have already chosen in the first step. Similarly, for the third step, we have ‘(n-2)’ objects available to us. Thus, from the Product Rule of Counting, we can get,

n(E) = n × (n – 1) × (n – 1) … (n – (r – 1))

= \( \frac{n!}{(n-r)!} \)

= ⁿP_r (notation for the number of permutations of r objects out of a set of n distinct objects)

A Specific Case

n! gives the number of permutations of ‘n’ objects from a set of ‘n’ distinct objects. For example, the number of ways in which you can jumble the alphabets of the word ‘flower’ is 6! where the number of alphabets in the word is 6.

What if our reservoir set of ‘n’ objects has some repeated elements? We can derive the formula in a similar manner to our derivation of the general formula, but with some important restrictions. You could try work

 

ing it out yourself! But for the time being, let us just state and understand it. The number of permutations of ‘n’ objects where p₁ objects are of one kind, p₂ objects are of one other kind… till p_k, is:

\( \frac{n!}{p1!.p2!…pk!} \)
where clearly, p₁ + p₂ +p₃ …..+ p_k = n.

Example: The number of ways in which you can jumble the alphabets of the word ‘balloon’ is given by

\( \frac{7!}{1!.1!.2!.2!.1!} \)

since the number count of different alphabets is given as:
n(occurrence of alphabet ‘b’)= 1
n(occurrence of alphabet ‘a’)= 1
Also, n(occurrence of alphabet ‘l’)= 2
n(occurrence of alphabet ‘o’)= 2
n(occurrence of alphabet ‘n’)= 1

Browse more Topics under Permutations And Combinations

• Fundamental Principles of Counting
• Combination

Alternate Analysis of ⁿP_r

If you remember, we had also mentioned ‘ordered combinations’ as another interpretation of ‘permutations’. Let us look at the formula for the number of combinations of ‘r’ items out of a set of ‘n’ items:

ⁿC_r \( \ = \ \frac{n!}{r!(n-r)!} \)

Let us take a specific combination of these numbers of different combinations. In permutations, the order of the chosen elements does matter; while in the combinations the order doesn’t matter. Thus, to arrive at the number of permutations, we must multiply the number of combinations by the number of possible permutations of each specific combination!

What is the number of permutations for a set of ‘r’ items? It is simply r! as we have discussed some time ago. Multiplying ⁿC_r by r! we observe:

ⁿC_r × r! = \( \frac{n!}{(n-r)!} \) = ⁿP_r

which is the same as the one we derived from our Product Rule of Counting. Therefore, the interpretation of ‘Permutations’ as ‘Ordered Combinations’ is correct!

You can download Permutations and Combinations Cheat Sheet by clicking on the download button below

 

Solved Example on Permutation

Question 1: In a sports broadcasting company, the manager must select the top three goals of the month, from a list of ten goals. Find out in how many ways can the top three goals be decided?

Answer: Since the manager must decide the top three goals of the month; the order of the goals is very important! Thus, the problem is of permutations.

Picking up three goals from a list of ten:

Possible Permutations = ¹⁰P₃ = \( \frac{10!}{(10-3)!} \) = 10 × 9 × 8 = 720

Therefore, there are 720 ways of picking the top three goals!

More Solved Examples

Question 2: What does permutation mean?

Answer: Permutation is an assortment or a combination of things from a set where the arrangement of the selected things does matter. Thus, we can say that the words in any language are basically some particular permutations of a collection of alphabets put together.

Question 3: What is the difference between combination and permutation?

Answer: Order is the major difference between combination and permutation. With permutation, we consider the order of the elements whereas with combinations we do not consider it. For instance, if the combo of your suitcase is 9876 and you enter 7869 in your suitcase, you will not be able to open it because of the different permutation.

Question 4: How do permutations work?

Answer: Permutations are basically for lists where the order carries utmost importance and combinations apply to groups in which orders do not really matter. Thus, permutation refers to an ordered combination.

Question 5: What is an example of permutation?

Answer: As we know permutation is the arrangement of all or part of a set of things carrying importance of the order of the arrangement. For instance, if there are a set of three letters, X, Y, and Z. So the question arises how many ways are there for arranging 2 letters from that set. Thus, each possible arrangement you get will be an example of permutation.