Permute

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.

Permutations differ from combinations, which are selections of some members of a set regardless of order. For example, written as tuples, there are six permutations of the set , namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the possible orderings of this three-element set. Anagrams of words whose letters are different are also permutations: the letters are already ordered in the original word, and the anagram is a reordering of the letters. The study of permutations of finite sets is an important topic in the fields of combinatorics and group theory.

Permutations are used in almost every branch of mathematics, and in many other fields of science. In computer science, they are used for analyzing sorting algorithms; in quantum physics, for describing states of particles; and in biology, for describing RNA sequences.

The number of permutations of distinct objects is  factorial, usually written as , which means the product of all positive integers less than or equal to .

Technically, a permutation of a set is defined as a bijection from to itself. That is, it is a function from to for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of in which each element is replaced by the corresponding . For example, the permutation (3, 1, 2) mentioned above is described by the function $\alpha$ defined as

: $\alpha(1) = 3, \quad \alpha(2) = 1, \quad \alpha(3) = 2$.

The collection of all permutations of a set form a group called the symmetric group of the set. The group operation is the composition (performing two given rearrangements in succession), which results in another rearrangement. As properties of permutations do not depend on the nature of the set elements, it is often the permutations of the set $\$ that are considered for studying permutations.

In elementary combinatorics, the -permutations, or partial permutations, are the ordered arrangements of distinct elements selected from a set. When is equal to the size of the set, these are the permutations of the set.

History

Permutations called hexagrams were used in China in the I Ching (Pinyin: Yi Jing) as early as 1000 BC.

Al-Khalil (717–786), an Arab mathematician and cryptographer, wrote the ''Book of Cryptographic Messages''. It contains the first use of permutations and combinations, to list all possible Arabic words with and without vowels.

The rule to determine the number of permutations of ''n'' objects was known in Indian culture around 1150 AD. The '' Lilavati'' by the Indian mathematician Bhaskara II contains a passage that translates to:

The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.

In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, ''two'' must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks:

Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;

Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.

A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.

Permutations without repetitions

The simplest example of permutations is permutations without repetitions where we consider the number of possible ways of arranging items into places. The factorial has special application in defining the number of permutations in a set which does not include repetitions. The number n!, read "n factorial", is precisely the number of ways we can rearrange n things into a new order. For example, if we have three fruits: an orange, apple and pear, we can eat them in the order mentioned, or we can change them (for example, an apple, a pear then an orange). The exact number of permutations is then $3! = 1 \cdot 2 \cdot 3 = 6$. The number gets extremely large as the number of items (n) goes up.

In a similar manner, the number of arrangements of k items from n objects is sometimes called a partial permutation or a k-permutation. It can be written as $nPk$ (which reads "n permute k"), and is equal to the number $n (n-1) \cdots (n - k + 1)$ (also written as

Definition

In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either $\alpha$ and $\beta$, or $\sigma, \tau$ and $\pi$ are used.

Permutations can be defined as bijections from a set onto itself. All permutations of a set with ''n'' elements form a symmetric group, denoted $S_n$, where the group operation is function composition. Thus for two permutations, $\pi$ and $\sigma$ in the group $S_n$, the four group axioms hold:

# Closure: If $\pi$ and $\sigma$ are in $S_n$ then so is $\pi\sigma.$
# Associativity: For any three permutations $\pi, \sigma, \tau \in S_n$, $(\pi\sigma)\tau = \pi(\sigma\tau).$
# Identity: There is an identity permutation, denoted $\operatorname$ and defined by $\operatorname(x) = x$ for all $x \in S$. For any $\sigma \in S_n$, $\operatorname \sigma = \sigma \operatorname = \sigma.$
# Invertibility: For every permutation $\pi \in S_n$, there exists an inverse permutation $\pi^ \in S_n$, so that $\pi\pi^ = \pi^\pi = \operatorname.$
In general, composition of two permutations is not commutative, that is, $\pi\sigma \neq \sigma\pi.$

As a bijection from a set to itself, a permutation is a function that ''performs'' a rearrangement of a set, and is not an arrangement itself. An older and more elementary viewpoint is that permutations are the arrangements themselves. To distinguish between these two, the identifiers ''active'' and ''passive'' are sometimes prefixed to the term ''permutation'', whereas in older terminology ''substitutions'' and ''permutations'' are used.

A permutation can be decomposed into one or more disjoint ''cycles'', that is, the orbits, which are found by repeatedly tracing the application of the permutation on some elements. For example, the permutation $\sigma$ defined by $\sigma(7) = 7$ has a 1-cycle, $(\,7\,)$ while the permutation $\pi$ defined by $\pi(2) = 3$ and $\pi(3) = 2$ has a 2-cycle $(\,2\,3\,)$ (for details on the syntax, see below). In general, a cycle of length ''k'', that is, consisting of ''k'' elements, is called a ''k''-cycle.

An element in a 1-cycle $(\,x\,)$ is called a fixed point of the permutation. A permutation with no fixed points is called a derangement. 2-cycles are called transpositions; such permutations merely exchange two elements, leaving the others fixed.

Notations

Since writing permutations elementwise, that is, as piecewise functions, is cumbersome, several notations have been invented to represent them more compactly. ''Cycle notation'' is a popular choice for many mathematicians due to its compactness and the fact that it makes a permutation's structure transparent. It is the notation used in this article unless otherwise specified, but other notations are still widely used, especially in application areas.

Two-line notation

In Cauchy's ''two-line notation'', one lists the elements of ''S'' in the first row, and for each one its image below it in the second row. For instance, a particular permutation of the set ''S'' = can be written as
: $\sigma = \begin 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1 \end;$
this means that ''σ'' satisfies , , , , and . The elements of ''S'' may appear in any order in the first row. This permutation could also be written as:
: $\sigma = \begin 3 & 2 & 5 & 1 & 4 \\ 4 & 5 & 1 & 2 & 3 \end,$
or
: $\sigma = \begin 5 & 1 & 4 & 3 & 2 \\ 1 & 2 & 3 & 4 & 5 \end.$

One-line notation

If there is a "natural" order for the elements of ''S'', say $x_1, x_2, \ldots, x_n$, then one uses this for the first row of the two-line notation:
: $\sigma = \begin x_1 & x_2 & x_3 & \cdots & x_n \\ \sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n) \end.$

Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as
: $(\sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n))$,
that is, as an ordered arrangement of the elements of ''S''. Care must be taken to distinguish one-line notation from the cycle notation described below. In mathematics literature, a common usage is to omit parentheses for one-line notation, while using them for cycle notation. The one-line notation is also called the ''word representation'' of a permutation. The example above would then be since the natural order would be assumed for the first row. (It is typical to use commas to separate these entries only if some have two or more digits.) This form is more compact, and is common in elementary combinatorics and computer science. It is especially useful in applications where the elements of ''S'' or the permutations are to be compared as larger or smaller.

Cycle notation

Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set. It expresses the permutation as a product of cycles; since distinct cycles are disjoint

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases