Sitemap

Permutations

5 min readJun 7, 2022

--

Webster defines Permutation as “the act or process of changing the lineal order of an ordered set of objects”.

The word Permutation has its roots in Middle English from Anglo-French as permutacioun, which means “exchange, transformation” which traces back to the Latin verb permutare meaning “to change thoroughly, exchange”.

Now how does this tie to the mathematical connotation of Permutation?

In mathematics, two terms are forever linked to one another, Permutation and Combination. Combinations are a selection of items from a set that has distinct members, such that the order of selection does not matter. In Permutations, on the other hand, the order of selection matters. For Example, the set {1,2,3} has 6 Permutations : (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,2,1),(3,1,2). Now, in all of these, the elements are the same, but their order is different. This is Permutations at its core — Having different arrangements for a certain set of elements where every distinct order in which the elements are placed, creates a new arrangement. Permutations can be seen as ordered Combinations.

Types Of Permutations

Permutations can be of two types: With Repetition and Without Repetition.

Permutations with Repetition refer to if repetition of elements is allowed while creating the permutations. This is the easier form of permutations to calculate. Let’s look at it this way: you have to make an arrangement of 10 numbers from the set of {1,2,3,4,5,6,7,8,9,10}. Now, if repetition is allowed, every time we go to choose a number, we always have all 10 options available. This makes
10 X 10 X 10 ….(10 times) possible arrangements. This can be simplified as n to the power of r, where n is the number of things to choose from and r is how many of them we choose at a time.

Permutation with Reputation

In Permutations without Repetition, the number of arrangements gets reduced. Without repetition of elements, each element can be chosen at max, 1 time. For example, if we were to choose any 5 numbers out of our previous set i.e. {1,2,3,4,5,6,7,8,9,10}, when we pick the first number, let’s say 5, we had 10 options to choose from. But now for the next number, we will only have 9 options, then 8, then 7 and finally 6 options. Hence, the number of arrangements becomes 10 X 9 X 8 X 7 X 6. This can be applied in the formula by using the Factorial(!) function. But applying a partial factorial would be hard so we use a nifty trick of dividing the numerator by the factorial of the difference between the number of options and the number of places to fill. This way we can get our partial factorial. Here, n refers to the number of options and r refers to the number of elements to choose.

Permutation without Repetition

The above formula has a shorthand notation where the P stands for Permutation:

Applications

Permutations, being elementary, find their applications in even the most trivial spheres of life. The allocation of city/area codes and the allocation of phone numbers both apply the concept of permutations to generate the total number of options they have to assign these codes.

Get AayushCodes’s stories in your inbox

Join Medium for free to get updates from this writer.

To demonstrate how essential permutations are and how subconsciously we use them, let us consider this example: When someone is hungry and has to prepare themselves a meal, from all the ingredients in their home, there are many combinations and permutations to consider.

Just now, If I was making a sandwich, I would need two slices of bread. There are 10 left. I could pair those slices of bread in 10C2 (45) ways. And, theoretically, each slice could be on either top or bottom of the sandwich, so it could have been prepared in 10P2 (90) ways.

And, we are only talking about the bread. Let’s not get started on all the permutations and combinations of everything that actually might end up in the sandwich.

Functions and their properties: If the sets A has m elements and B has n elements, then

The number of functions from A to B is n^m.

The number of one-one functions from A to B is nPm, m ≤ n.

That’s not it, we can calculate so many more properties, like, the number of onto functions, the number of increasing/decreasing functions, etc. The world of set operations and functions is filled with Permutations because of its core nature of making arrangements and having discrete or repeated elements.

Communication networks, cryptography and network security: Permutations are frequently used in communication networks and parallel and distributed systems. Routing different permutations on a network for performance evaluation is a common problem in these fields. Many communication networks require the secure transfer of information, which drives development in cryptography and network security. This area has recently become particularly significant because of the increased use of internet information transfers. Associated problems include protecting the privacy of transactions and other confidential data transfers and preserving the network security from attacks by viruses and hackers. The encryption process involves manipulations of sequences of codes such as digits, characters, and words. Hence, they are closely related to combinatorics, possibly with an intelligent encryption processes. For example, one common type of encryption process is interchanging — i.e., permuting parts of a sequence. Permutations of fast Fourier transforms are employed in speech encryption.

Databases and data mining
Queries in databases are multiple join operations that are permutations of the constituent join operations. Determining an optimal permutation that gives minimum cost is a common and important problem. Data mining or knowledge discovery in databases is a relatively new field that aims at distilling useful information, often from large databases. In this area, techniques employing symbolic AI can manipulate combinatorial sequences of atoms or information elements. Non-symbolic knowledge discovery techniques, such as genetic algorithms and genetic programming, most commonly deal with solutions in the form of sequences of bits, digits, characters, and sometimes Lisp program elements. Neural networks, another domain of non-symbolic AI, sometimes deal with combinatorial patterns. Knowledge discovery techniques under uncertainty, such as Bayesian networks, Dempster-Shafer theory, fuzzy logic, and rough set theory, may have combinatorial solutions

Conclusion

A permutation is a mathematical technique that determines the number of possible arrangements in a set when the order of the arrangements matters.

Permutations are inadvertently very closely linked to our lives. Every decision we make, every thought we have is a permutation of a larger set. Our lives are just permutations of different choices that we have made. A fascinating correlation of permutations could be the multiverse theory. We have seen in very recent sci-fi movies how each universe is just a permutation of different choices and events.

What we can take away from this is that permutations, however trivial, are related to most spheres of life.

--

--