JUMP TO TOPIC

Permutation|Definition & Meaning

Definition

The permutation is a process that finds the probable arrangements in a batch when the order of the arrangements counts. Typical mathematical problems need the selection of only several objects from a batch of objects in a particular order.

The permutation can be viewed as an ordered combination. The idea of permutation has been demonstrated in Figure 1 below.

Figure 1: Concept of Permutation

Moreover, permutation is a concept in math that outlines the number of ways in which a particular set of data can be arranged. Put simply, it is the number of ways in which data can be ordered. This data is generally taken from a list. With permutations, the order of the datasets matters, as is the case with a safe or locker combination.

Types of Permutation

There are various kinds of permutations. The 2 major kinds of permutations include the following:

Permutations with repetition. With repetition, one can make distinct sets with various objects. The number of times elements of the data set appear is not restricted, i.e. one can utilize the data more than one time.
Permutations without repetition. Here, one item is removed from the list each time one data item has been utilized. Putting simply, the unrestricted options for permutations decrease as one proceeds ahead step by step.

There are many examples of permutations related to the real world as discussed next. For example, the combinations of safes available in banks, post offices, etc. are based on permutations due to the fact that the arrangement of the numbers is an important issue to be considered. One cannot open up a safe box or locker box if one does not have the correct number.

One more example of permutation is an anagram in which one makes various words from a single root word. Here, arrangement matters as one has to form a precise word, not a random succession of alphabets.

One more real-life example includes selecting the arrangement in which players end a race. One can utilize factorials to find who stands in first, second, or third place, and mentioning the order of the other participants is not needed.

Some examples of permutations are not commonly known, for example, using multi-sets (that involve objects that are non-distinct) and cyclic permutations or the number of manners that a number of objects can be re-arranged along a circle.

Permutations are often confused with the concept of combinations. In combinations, the arrangement of the already chosen items does not affect the selection, i.e., the orders a-b and b-a are considered different arrangements in permutations, while in combinations, these arrangements are equal.

Permutations are different from combinations. Combinations are selections of a few members of a batch regardless of their arrangement. For example, represented as tuples, there are six permutations of the set {1, 2, 3}, i.e., (1, 2, 3), (2, 1, 3), (1, 3, 2), (3, 1, 2), (2, 3, 1), and (3, 2, 1). These are all the probable arrangements of the 3-member set.

Anagrams of phrases whose letters are distinct are also permutations: the letters are arranged in the actual word, i.e., the anagram is a re-arrangement of the letters. The investigation of permutations of finite sets is an essential topic in the areas of group theory.

Regarding utilization, permutations are utilized in many branches of maths and different fields of science. In computer science, permutations are utilized to analyze and sort algos; in quantum physics, permutations are utilized to describe the states of particles; and in biology, to describe RNA successions.

Permutation Formula

The general expression and meanings of variables used for permutation is given in Figure 2:

Figure 2: Formula to Compute Permutation

where:

n – number of members in a batch
k – number of chosen members arranged in a certain order
! – factorial

The factorial (represented as “!”) is the product of all positive integers less than or equal to the number preceding the factorial sign. For example, 4! = 1 x 2 x 3 x 4= 24.

The above formula is used in circumstances when one needs to select only many members from a set and order the chosen members in a particular order.

Permutation Problem Explained

Consider the problem of choosing 3 horses from a set of 4 horses. In a race of 15 horses, assume for a moment that one knows the most useful 4 horses and that 3 of them are likely to finish in the top three ranks. So out of 4 horses, one wishes to choose the subset of 3 victors and the arrangement in which they finish.

Now, how many permutations are there for the top 3 from the 4 best horses?

For this problem, we look for an arranged set of 3 horses (r) from the set of 4 most promising horses (n). We ignore the other 11 horses in the race of 15 as they do not apply to our scenario. We need to compute P(4,3) to know all the possible products for the top 3 victors.

\[P(4, 3) = \dfrac{4!}{(4 – 3)!} = 24\]

These 24 probable permutations for the winning of 3 horses are:

{1,2,3}, {1,3,2}, {1,2,4}, {1,4,2}, {1,3,4}, {1,4,3}, {2,1,3}, {2,3,1},

{2,1,4}, {2,4,1}, {2,3,4}, {2,4,3}, {3,1,2}, {3,2,1}, {3,1,4}, {3,4,1},

{3,2,4}, {3,4,2}, {4,1,2}, {4,2,1}, {4,1,3}, {4,3,1}, {4,2,3}, {4,3,2}

Difference Between Permutation and Combination

There are many key dissimilarities between permutations and combinations. The permutation is the ordering of data that relies on the order of members, while a combination is a choice of data when the order doesn’t count. The members for permutations are selected from a list, while members for a combination are obtained from a group of objects.

The main differences between permutations and combinations are given below:

Permutation means the choice of objects when the arrangement of selection counts. The combination means the process of selecting the objects where the order of selection does not count. Alternatively, it is the choice of $r$ objects taken out of $n$ objects irrespective of the object arrangement.
The formula for permutation is $^{n}P_{r} = \frac{n!}{(n-r)!}$ while the formula for combination is $^{n}C_{r} = \frac{n!}{r!(n-r)!}$

Fundamental Counting Principle

This principle helps find the number of combinations or possibilities. According to this rule, “If an event can be executed in $m$ manners and there are $n$ manners of executing a second event, then the number of manners of executing the two events together is $m \times n$.

This rule can be expanded to the scenario where various operations are performed in $m, n, p, \ldots$ manners. For this case, the number of ways of executing all the events one after the other is $m \times n \times p \times \ldots$ and so on.

Example of a Permutation

Suppose that you are an associate in a private equity company. You desire to fund \$5 million in two schemes. Rather than of equal share, you decide to fund \$3 million in the most profitable scheme and \$2 million in the less profitable scheme. Your reviewers shortlisted six schemes for probable investment. How many probable arrangements are known for your funding decision?

Solution

The above problem is a permutation scenario. As the allotment of the funds for the two schemes is not identical, the order of selection matters. For example, take a look at the arrangements: ‘fund \$3 million for scheme A and \$2 million for scheme B’ vs. ‘fund \$2 million for scheme A and \$3 million for scheme B.’

The possibilities are not similar to each other. Therefore, we need to utilize the relation above to find the number of possible arrangements. Utilizing the relation above, we find the number of possible arrangements as shown in Figure 3:

Figure 3: Example of difference b/w permutation and combination

i.e., you can get 30 potential funding arrangements based on the six schemes shortlisted by your reviewers.

All images/mathematical drawings were created with GeoGebra.