# Techniques of Combinatorics for Permutation in Discrete Mathematics

Combinatorics is a section of discrete mathematics, which has gained importance due to its use in probability theory, mathematical logic, number theory, computer science, and cybernetics. Each rule specifies a method for constructing a design from the elements of the original set that is called combinatorial configurations.
Therefore, it can be said that the aim of combinatorics is the study of combinatorial configurations, in particular, issues of their existence, construction algorithms, and problem solving for the transfer. Examples of combinatorial configurations are the permutations, combinations and accommodation, block diagrams and Latin squares. The basic and common operations and related problems in combinatorics are the following: 1) the formation of ordered sets that consist in establishing a certain order of the elements; drawing permutations; 2) the formation of a subset consisting of the allocation of some portion of the set of elements that compose combinations; 3) the formation of ordered subsets; drawing placements.
Combinatorics is an important branch of mathematics, knowledge of which is necessary to the representatives of various professions. Physicists, chemists, biologists, linguists, specialists in codes have to deal with the combinatorial problems. Combinatorial methods are the basis for solution of many problems in probability theory and its applications. Today, combinatorial methods are used in the theory of casual processes, statistics, mathematical programming, computational mathematics, design of experiments, etc. In mathematics, combinatorics is used in the study of finite geometries, combinatorial geometry, non-associative algebras, etc.
Major operating facilities of combinatorics are combination, permutation, and placement of the partition elements and finite sets of natural numbers. In particular, the combination is formed by a disordered sample of a finite set. Permutation is received by the location of all the elements of a finite set in a different sequence. Placement can be considered as ordered selection of a finite set of elements, where they swapped in a different order. Under the partition of the set, separation of its elements into disjoint subsets is meant. The partition of integers is their representation in the form of an arithmetic sum of the parts. In all cases, the physical nature of the technical properties or information sense of elements, which form such combinatorial objects, is not essential. Their combinatorial configuration that reflects the conditions of the combinatorial problem is important. To calculate the above-mentioned basic combinatorial objects, special formulas or recurrence relations, which operate with various special functions and combinatorial numbers, are used.

## History of Combinatorics

Combinatorics deals with various kinds of compounds that can be formed from the elements of a finite set. Some elements of combinatorics were known in India in the II century BC. The Indians were able to calculate the numbers, which are now called the combination. In the 12th century, Bhaskara figured some kinds of combinations and permutations (Selin, 1997). Indian scientists studied compounds due to their use in poetics, the science of the structure of the verse and poetic works (for example, in connection with the calculation of the possible combinations of stressed (long) and unstressed (short) syllables). As a scientific discipline, combinatorics was formed in the 17th century.

Our outstanding writers are mostly educated to MA and PhD level

The first works, in which the basic concepts of probability theory were originated, represented an attempt to create a theory of gambling (Cardano, Huygens, Pascal, Fermat, and others). The next stage of development of the theory of probability is associated with the name of Jacob Bernoulli (1654-1705). His proved theory, which was later called the law of large numbers, was the first theoretical justification of the previously accumulated facts. Further success of probability theory dealt with Moivre, Laplace, Gauss, Poisson and others. New and the most fruitful period was associated with the Chebyshev (1821-1894) and his followers Markov (1856-1922) and Lyapunov (1857-1918). During this period, the theory of probability became a coherent mathematical science. Its further development is related to Russian and Soviet mathematicians (Bernstein, Romanovsky, Kolmogorov, Khinchin, Gnedenko, and Smirnov).
It is difficult to speak confidently about the level of knowledge of the ancient Greeks in the area of combinatorics, since not all of their academic achievements have reached the modern times. In 391 BC, the crowd of monks destroyed Science Museum of Alexandria and burned most of its library, which counted many thousands of volumes. The remains of the library were further destroyed during three more centuries. In 638 BC, it was eventually destroyed during the attack on Alexandria of Arab armies of the Caliph Omar. Most scientific books were lost.

Magic square is square array (n * n) of integers from 1 to n such that the sum of the numbers along each column, each row, and two diagonals of the table are the same number s = n (n¤ + 1) / 2 (Da Fonseca, 2005). The number n is called an order of magic square. It is proved that the magic square can be constructed for any n. Already in the Middle Ages, an algorithm for constructing magic squares of odd order was known. There are magic squares, which satisfy a number of additional conditions, such as a magic square of n = 8, which can be divided into four smaller magic squares 4×4. In India and some other countries, magic squares were used as talismans. However, the general theory of magic squares does not exist. The total number of magic squares of order n is unknown too (Weisstein, n.d.).
Latin square is a square matrix of order n, each row and each column of which are permutations of elements of finite sets S, which consist of n elements.
The location problem is one of the classical combinatorial problems, which require determining the number of ways of placing m different items in n different zones with a given number r of empty zones. This number is equal to r n-r m.
The traveling salesman problem, the problem of stray trader is combinatorial problem of graph theory (Weisstein, n.d.). In the simplest case, it is formulated in the following way: it is given n cities and the known distance between any two cities; salesman, who comes from one of the cities to visit the other n-1 cities and return to the starting one. In what order should he visit the cities to make the total distance traveled minimized? Methods for solving the traveling salesman problem are essentially reduced to the organization of full search options.

The method of recurrence relations is that the solution of combinatorial problem with n objects is expressed through the solution of a similar problem with a smaller number of objects with the help of some relation, which is called recurrence. Using this relation, one can calculate the required value, based on the fact that a small number of subjects’ solution is easily located.
According to “Principle of Inclusion-Exclusion” (n.d.), the method of inclusion and exclusion is another method of combinatorial tasks. The method of counting the number of elements in the union of the sets according to this formula, which consists of alternately addition and subtraction, is called the method of inclusion and exceptions. For many combinatorial problems, a geometric interpretation, which reduces the problem to counting the number of paths (trajectories) that have certain properties, can be indicated.

## The Basic Formulas of Combinatorics

Combinatorics studies the number of combinations, which is subjected to certain conditions that can be formed from the elements regardless of the nature. The formulas of combinatorics are often used with the direct calculation of probabilities. Accommodation is called a combination that is composed of n distinct elements by m elements, which differ in the composition of elements or their order. The number of all possible placements Amn = n (n – 1) (n – 2) … (n – m + 1).
The combination is composing n different elements on m elements, which differ in at least one element. The number of combinations is C mn = n! / (M! (N – m)!). The number of placements, permutations and combinations is related by Amn = PmC mn.
Permutation is a combination that consists of the same n various elements and differs only in the order of their arrangement. The number of all possible permutations is Pn = n !, wherein n! = 1 * 2 * 3 … n.

### Permutation

The number of permutations of order n is the number of placements of n by n, i.e. factorial: Pn = Ann = n!/ (n-n)! = n!/ 0! = n! = 1∙2∙∙∙∙∙n. The composition determines the operation of work on permutations of the same order: (π⋅σ) (k) =π (σ(k)). Under this operation, the set of permutations of order n forms a group, which is called the symmetric and usually denoted Sn. Any group is a subgroup of the group of permutations of the elements of this group (Cayley’s theorem) (Cid, Murphy, & Robshaw, 2006). Thus, each element a∈G is compared with permutation πa, which is defined by the identity πa (g) = a ∘ g, where g is any element of G, and ∘ is a group operation. Various permutations coincide in the composition and different positions of its elements. For example, it is possible to obtain the following six different permutations (XYZ); (YZX); (ZXY); (YXZ); (XZY); (ZYX) from three English letters {X, Y, Z}.
There are special types of permutations. An identity permutation is permutation e, where each element x∈X displays the following: e (x) = x (“Identity permutation,” n.d.). An involution is a permutation τ, which is the inverse of itself, that is, τ⋅τ = e. A mess is a permutation without fixed points. A cycle of length ℓ is called a permutation π, which is identical to the whole set X, besides subsets {x1, x2, ….., xℓ} ⊂ X and π (xℓ) = x1, π (xi) = xi + 1. It is denoted as (x1, x2, ….., xℓ). The numbers of permutations that contain k cycles are Stirling numbers of the first kind. Transposition is a permutation of the elements of X, which swaps the two elements. Transposition is a cycle of length 2.
The relative error in calculating the value of n! by Stirling’s formula is about (1 / 12n). For example, the current value of 8! is equal to 40320. Calculations by the formula of Stirling give an approximate result 39902 with an error of about 1% (1/96): 40320 = 8! ~ (17π) 1/2 (8e) 8 ~ 39902.
According to Kuba and Panholzer (n.d.), the quality of the approximate calculation of the factorial values could be further increased if one uses the following refined version of the Stirling formula: n! ~ (2πn) 1/2 (ne) n (1+ 112n).
A computational experiment allows to note the rapid growth of the values of n! with increasing n. In particular, 10! exceeds 3.5 million (3,628,800). 1000! is an integer with more than 2500 decimal characters. Another interesting fact is that the number of decimal digits in n! exceeds n, starting with n = 25. In general, it can be shown that the factorial function grows even faster than exponentially. The validity of this conclusion follows from the analysis of the following expression for the square of the factorial function:
(n!)2 = n∏k=1k (n – k + 1) ≥ n∏k=1n = nn.
A comparison of left and right sides of this inequality yields the following relation between the factorial function and exhibitors:
n! ≥ n(n/2)
The resulting estimate of the increase rate of the factorial function is of practical importance, since it determines the computational complexity of combinatorial problems of application, in which sorting permutations of the various elements is needed to be implemented. For the practical solution of such problems, a large number of diverse combinatorial algorithms of systematically enumerating the permutations in a different order have been developed. The most famous of these are the various options of lexicographical algorithms, the algorithm of cyclic shifts (rotations) of permutations, and algorithms of transposition of adjacent elements.

### Lexicographic Order of Permutations

Lexicographical order is used for listing all permutations (Wodarz, 2008). The result of enumeration of permutations in a lexicographical order, where each successive permutations form a larger vector of its lexicographical elements than any of the previous ones, looks the most natural. In the general case of any two vectors of equal length, lexicographical order is considered the vector, in which the first of non-matching elements is bigger. The lexicographical order generates an increasing sequence of natural numbers, which are obtained from the records of the relevant permutations. In particular, all the permutations of the three numbers 1, 2 and 3 form the following lexicographical ordered numerical sequence:
ПL: (123) < (132) < (213) < (231) < (312) < (321).
Lexicographical order of permutation of letters of any national alphabets is aligned with words in a dictionary that are formed from them. For example, the permutation of letters X, Y and Z may be listed in the following lexicographical order, which is often called the dictionary order:
ПL : (XYZ) < (XZY) < (YXZ) < (YZX) < (ZXY) < (ZYX).
However, without losing generality, the following description of the algorithm is convenient to consider the lexicographical enumeration of permutations of the integers from 1 to n. This algorithm implements an iterative process that starts with the smallest lexicographical permutation, where all the numbers are arranged in an ascending order of their values, and coincide with the numbers of their positions (Wodarz, 2008). For example, for n = 8 elements, such lexicographically smallest permutation has the following form:
Pmin = (1, 2, 3, 4, 5, 6, 7, 8).
At each iteration in the lexicographical order, a permutation is generated from the current permutation (p1, …,pi, …,pj, …,pn). For example, permutation was obtained in the previous iteration. To convert it into another permutation in the lexicographical order, three functional activities that provide reverse lookup of elements, transposition of elements and writeback of tail elements of the current permutation should be performed. Initially, it is needed to find the rightmost element pi, which is smaller than its neighbor to the right pi+1:
pi < pi+1| pk > pk+1 for any k> i.
In this case, (pi = 5) <(pi+1 = 8). Then, it is needed to find the smallest element pj to the right of pi, which is bigger than pi: Pj = min k>I pk > pi.
In this case, pj = 7. Further, it is necessary to interchange pi = 5 with pj = 7. Then, permutation looks like this:
P = (p1, …, pj, pi+1, …, pj, pi+1, , …, pn) = (2, 6, 7, 8, 5, 4, 3, 1).
Finally, the tail of permutations, which starts with pi+1 = 8 must be written in reverse order. Similar iterations are required to continue to achieve the highest lexicographical permutation, where all the numbers are arranged in a descending order of their values:
P = (n, n−1, …, 2, 1) = (8, 7, 6, 5, 4, 3, 2, 1).
The considered lexicographical algorithm can be easily adapted to generate permutations in a reverse lexicographical order. In such an order, the sequence of permutations begins with lexicographically greatest one. Each following lexicographical permutation is less than the previous one. To obtain the specified order by lexicographical algorithm, it is needed to invert all the signs of relations of items comparison and search for the smallest element of the right to replace the search for the greatest everywhere (Wodarz, 2008). For example, after this change, lexicographical algorithm generates the following sequence of numbers, where all permutations of numbers 1, 2 and 3 are listed in the reverse lexicographical order:
ПR: (321) > (312) > (231) > (213) > (132) > (123).
It should be noted that in both embodiments of lexicographical order, permutation is performed by comparing the first error symbol. If the last mismatched element is considered for comparing permutations, a reverse order of enumeration, which is called anti lexicographical, would be established. In this order, for any pair of adjacent permutations of equal length, the last of their opposing elements at the next reshuffle pair must be less than in the previous permutation.
According to this definition, anti lexicographical order would be obtained if the arrangement of elements in all the permutations that are listed in reverse lexicographical order is reversed. For example, in the following sequence of permutation of numbers, 1, 2 and 3 are listed in anti lexicographical order:
ПA: (123) < (213) < (132) < (312) < (231) < (321).
However, there is a special recursive algorithm that directly generates a sequence of permutations in anti lexicographical order. In this algorithm, the required sequence of permutations of n elements is formed from the units that have already been obtained from earlier permutations (n-1) elements, in which element n is added according to certain rules. Each of such blocks consists of (n-1)! permutations. The n blocks are indexed by integers from n to 1 in the following order:
Bn, …, Bi, …, B1.
The starting block Bn forms all recursively constructed permutations of (n-1) elements, each of which is added to the right element of the value n. Each subsequent block with the number I from (n-1) to 1 should consist of (n-1)! permutations, in which the last element is set to i. In this case, permutation of block Bi is obtained by transposition of elements with values i and (i + 1) in the previous block permutations Bi+1. This transformation of the block Bi+1 in block Bi can be written as follows:
Bi+1= [(p1, … pj = i, … pn = i+1)]i+1 (pj = i <−> pn = i+1) > Bi= [(p1, pj= i+1, … pn= i)]i.
This process completes the transformation of the block B1, wherein the value of the last element of permutations is equal to unity. Thus, anti lexicographical sequence n (n-1)! of permutations of n elements is obtained. It can be used to recursively construct all permutations of higher orders. Considered algorithm illustrates the following example of forming digital permutations of the three elements, where each block is highlighted by a pair of square brackets [], and an underscore denotes adding transposition and rearrangements of elements in blocks:
[(12) ;(2,1)] +3> < [(123); (213)]3 3<−>2 > [(132); (312)]2 2<−>1 > [(231); (321)]1 >.

### Inversion of Permutations

It is important to have a quantitative estimate of the degree of difference of an arbitrary permutation from the lexicographically smallest number of violations of the increasing order of the values of its elements. Any pair of elements, where there is a violation of their relative position in the permutation, is called inversion. Formally, any pair of elements (pi, pj) of permutation (p1, …, pi, …, pj, …., pn) forms an inversion, if pi > pj and i pj: i < j } | and wj = | { pi > j : i < j } |. It should also be noted that the values of the components of the vector and table of inversions for any permutation are related as follows: V1 = Wn = 0; Vj = Wi | i = Pj; Wj = Vi | Pi = j. In general, the number of inversions of arbitrary permutations of n elements always ranges from 0. At lexicographically smallest permutation, it ranges to a maximum value equal to n (n-1) / 2, which has the highest lexicographical permutation: I(1, 2, …, n−1, n) = 0 ≤ I(p1, …, pi, …, pn) ≤ I(n, n−1, …, 2, 1) = n(n-1)2 Besides information about the distribution of the disorder in the permutation, the fact that the vector and table of inversions determine the permutation has a practical importance (Margolius, 2001). This means that any permutation can always be uniquely reconstructed from the corresponding table and vector of inversions. Two restoration algorithms are provided for performing these transformations. In particular, the reduction of inversions vector V, elements of seeking permutation P are necessary to successively compute from right to left in the index order. Their values should be selected from a list L, which are ranked in decreasing order of integers from 1 to n. Herewith, the value of the next element of permutation pi is assumed equal to (Vi + 1) in magnitude of the number of the list L. The selected number should be removed from the list. Execution of the algorithm is illustrated by the following example of restoring permutation P=(3,2,1,5,4) by the vector of inversion V=(0,1,2,0,1): p:4->p5 5->p4 1->p3 2->p2 3->p1 L:{5 ^4^ 3 2 1}<5 ^3^ 2 1>,<3 2 ^1^>,<3 ^2^>,<^3^>V: 1=V5 0=V4 2=V3 1=V2 0=V1
In this case, the symbol ‘^’ indicates the element, which is excluded from the list L at each iteration, for transmission of its value to the next element of permutation. In particular, initially, it is needed to exclude the second largest element (4), as the last element of the vector of inversions is 1, and the value 4 is assigned to the last element of the permutation, from a list of <54321>. Similar actions are repeated in all subsequent steps. A more elegant algorithm is designed to recover permutation P on the table of inversions W. In this algorithm, it is needed to consistently view the components of the table of inversions Wi from right to left from i = n to i = 1 to obtain the list of indexes of L, which shows the relative location of components of required permutation with values from 1 to n. Firstly, the element with the value n is included in an empty list. At each step, further element with the value I is positioned so as Wi elements, whose values are bigger than i, appear before it. After placing the last element with a value of 1, the desired permutation, which matches the specified table inversions, is obtained in the list. This algorithm is illustrated by the following example, where permutation P=(3,2,1,5,4) is formed from the table of inversion W=(2,1,0,1,0):
L: ( 5^ ),( 5 4^ ), ( 3^ 5 4),( 3 2^ 5 4), ( 3 2 1^ 5 4) ->p W->W5 = 0W4= 1W3 = 0W2 = 1W1 =1
In this example, the symbol ‘^’indicates the element that is placed in the list L at each iteration, as a result of which the desired permutation P is formed. Inversion algorithm generates a sequence of permutations, which begins with the smallest lexicographical permutation with zero number of inversions and ends with greatest permutation, where there is maximum number of inversions. In this case, the number of inversions in the each intermediate permutation is not less than in the previous permutation. Thus, a sequence of permutations that are partially ordered by the amounts of reversals of their elements is obtained.

### Cyclic Shift of Permutation

One of the most natural ways of generating permutations is a cyclic shift of their elements to the left or right (Legendre & Paclet, 2011). In particular, each element moves to the next position and displaces the last element in the beginning of the permutation. It is possible to shift all elements or any number of head elements without changing positions of the tail elements of permutations. The conversion of cyclic shift is conveniently given in the form of substitution of the two rows, which are arranged one above the other. The elements of the initial permutation are listed in the top row. The elements of permutation that is obtained after cyclic shift are recorded under them. In general, this method can specify any permutation transformations, including cyclic shift (Legendre & Paclet, 2011).
In general, it is needed to continue iteration of rotation of all the elements, which produces another series of the original permutation until the next retry and after obtaining a new permutation. For its processing, the reduction of the shift order should again be applied. Then, another series of permutations of n new rotation of all elements is formed. Similar iterations guarantee listing all permutations. A sign of completion of the algorithm is reducing the order of the shift to a position in the processing of repeat.

The volume of computational work will be much less if a sequence of permutations in the order of minimal change positions of elements in the transition to the next each permutation is generated. Any permutation should be different from the previous permutation transposition of two adjacent (contiguous) elements to make change minimal. In general, such a sequence of permutations is easily built under the following recursive rule. There is a sequence of (n-1)! permutation of the (n-1) elements, in which neighboring permutations differ by transposition of two adjacent elements. The composition of each of them can be extended to a permutation of the n elements by adding the element n for every position of (n-1) elements.
Any effective algorithmic implementation of reviewing the process of iterations should provide a quick search of transpositions without complete enumeration of all elements of the permutation. This information can be easily obtained by the inverse permutation, where the values of the elements identify the positions of elements of direct permutation. In other words, the value of each element of the inverse permutation of the serial number of positions is defined by a straight permutation element that is equal to its index. In this case, there is dual statement: values of the elements of direct permutations are equal to ordinal position of their indices in the reverse permutation.
Compared to all other algorithms of generating permutations, iterative algorithm for the transposition of adjacent elements is the most efficient. The enumeration of permutations in minimal change order may be useful for a variety of combinatorial problems.

### Cyclic Classes of Permutations

Any permutation of the various elements can always be defined by the substitution of these elements, which establishes a one-to-one correspondence between them in the form of a transition table. In addition, any such substitution can represent a partition into cycles of transitions of its elements. The elements of each cycle are usually listed in the brackets. A partition into cycles is given by a line of such bracketed entries. In particular, the following entries denote the same partition into two cycles, and correspond to one permutation of successive natural numbers. Any substitution can be represented in such a form, if each entry of its cycle begins with a minimum value for the element, which is not involved in the previous cycles. On a similar principle, it is possible to construct a partition into cycles for numeric permutations and obtain a permutation on cycles of the partition. In this case, there is a correspondence, in which if the element j follows the element i in any cycle of decomposition, this element will take the position j with the number i in the corresponding permutation:
( … ji … ) <−> [ … i j … ].
In general, the number of partitions into cycles of n elements in an arbitrary class of cyclic (K) can be determined by using the following formula:
С(K1… Kj… Kn) = n!(1k1 ∙K1!)…(jkj ∙Kj! ) … (nkn ∙Kn!)
Kuba and Panholzer (n.d.) state that the number of partitions of n elements into m cycles for any values n≥m> 0 is determined by the Stirling numbers of the first kind. Formally, these numbers are equal to the coefficients of the polynomial, which is formed by multiplying binomials of the form n (Z + m), where m takes all the successive values from 0 to (n-1):
[Z]n = Z(Z+1)(Z+2) … (Z+n−1) = [nn]∙Zn + [nn-1]∙Zn-1 + … + [nm]∙Zm + … +[n1]∙Z1
The production of binomials in the left part of this transformation is called factorial increasing degree of random variable Z (it is equal to n! at Z = 1). The square coefficients of the conventional algebraic degree of Z n to 1 in the right-hand side denote the Stirling numbers of the first kind. Thus, the Stirling numbers of the first kind are shown to decompose factorial powers to ordinary algebraic degree (Kuba & Panholzer, n.d.).
Using the correspondence between the Stirling numbers of the first kind and the partition into cycles, the recurrence relation can be given combinatorial interpretation. According to this recurrence relation, decompositions of n elements on m cycles are formed from partitions (n-1) elements on the (m-1) and m cycles. Each partition of n elements into cycles is reduced to the placement of the n in a separate cycle or its addition to one of the m existing cycles.

## Conclusion

A permutation is a change of the elements order in the finite set. Permutation (often n-permutation) of n plurality A = {a1,…an} is displaying π: [n]! A. Since each element of the plurality in permutation is presented only once, the first element of n-permutation can be chosen by n methods; the second element can be chosen by n—1 methods and so on. Thus, the number of all permutations of n-set A is equal to Pn = n⋅(n-1) ⋅⋅⋅1=n!.
There are particular techniques of permutation. The lexicographical order is used for generating an increasing sequence of numbers that are received from the records of the relevant permutations. Inversion gives an opportunity to receive a quantitative estimate of difference’s degree of permutation with the smallest number of violations. A cyclic shift of the elements is a natural way of generating permutations. It provides shifting all head elements without changing the positions of the tail elements. Cyclic classes of permutations are based on the substitution of elements, which establishes correspondence between them in the form of a transition table. Transposition of adjacent elements is the most effective technique of generating permutations.

Get a price quote

#### References

Cid, C., Murphy, S., & Robshaw, M. (2006). Algebraic aspects of the advanced encryption standard.
Da Fonseca, J.B. (2005). The magic square as a benchmark: Comparing manual solution with MIP solution and AI algorithm and improved evolutionary algorithm. World Scientific and Engineering Academy and Society. Retrieved from website