![Permutations RGB](https://upload.wikimedia.org/wikipedia/commons/4/4c/Permutations_RGB.svg)
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a permutation of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
is, loosely speaking, an arrangement of its members into a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
or
linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive ...
, 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
combination
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
s, which are selections of some members of a set regardless of order. For example, written as
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s, 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.
Anagram
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word ''anagram'' itself can be rearranged into ''nag a ram'', also the word ...
s 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 set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
s is an important topic in the fields of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
.
Permutations are used in almost every branch of mathematics, and in many other fields of science. In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, they are used for analyzing
sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. ...
s; in
quantum physics
Quantum mechanics is a fundamental theory in physics that provides a description of the physical properties of nature at the scale of atoms and subatomic particles. It is the foundation of all quantum physics including quantum chemistry, qua ...
, for describing states of particles; and in
biology
Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary i ...
, for describing
RNA
Ribonucleic acid (RNA) is a polymeric molecule essential in various biological roles in coding, decoding, regulation and expression of genes. RNA and deoxyribonucleic acid ( DNA) are nucleic acids. Along with lipids, proteins, and carbohydra ...
sequences.
The number of permutations of distinct objects is
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
, usually written as , which means the product of all positive integers less than or equal to .
Technically, a permutation of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
is defined as a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
from to itself. That is, it is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
from to for which every element occurs exactly once as an
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
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
defined as
:
.
The collection of all permutations of a set form a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
called the
symmetric group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
of the set. The group operation is the
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
(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 permutation In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set ''S''
is a bijection between two specified subsets of ''S''. That is, it is defined by two subsets ''U'' and ''V'' of equal size, and a one-to-one m ...
s, 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
, can be seen as a compound composed of an upwards (blue here) and downwards (pink) facing equilateral triangle, with their intersection as a regular hexagon (in green).
A hexagram ( Greek language, Greek) or sexagram (Latin) is a six-pointed ...
were used in China in the
I Ching
The ''I Ching'' or ''Yi Jing'' (, ), usually translated ''Book of Changes'' or ''Classic of Changes'', is an ancient Chinese divination text that is among the oldest of the Chinese classics. Originally a divination manual in the Western Zho ...
(
Pinyin
Hanyu Pinyin (), often shortened to just pinyin, is the official romanization system for Standard Mandarin Chinese in China, and to some extent, in Singapore and Malaysia. It is often used to teach Mandarin, normally written in Chinese for ...
: Yi Jing) as early as 1000 BC.
Al-Khalil
Hebron ( ar, الخليل or ; he, חֶבְרוֹן ) is a Palestinian. city in the southern West Bank, south of Jerusalem. Nestled in the Judaean Mountains, it lies above sea level. The second-largest city in the West Bank (after East J ...
(717–786), an
Arab mathematician and
cryptographer
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, wrote the ''Book of Cryptographic Messages''. It contains the first use of
permutations and combinations, to list all possible
Arabic
Arabic (, ' ; , ' or ) is a Semitic languages, Semitic language spoken primarily across the Arab world.Semitic languages: an international handbook / edited by Stefan Weninger; in collaboration with Geoffrey Khan, Michael P. Streck, Janet C ...
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
Fabian Stedman (1640–1713) was an English author and a leading figure in the early history of campanology, particularly in the field of method ringing. He had a key role in publishing two books ''Tintinnalogia'' (1668 with Richard Duckworth) and ...
described factorials when explaining the number of permutations of bells in
change ringing
Change ringing is the art of ringing a set of tuned bells in a tightly controlled manner to produce precise variations in their successive striking sequences, known as "changes". This can be by method ringing in which the ringers commit to memor ...
. 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
Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangia[roots
A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients.
Root or roots may also refer to:
Art, entertainment, and media
* ''The Root'' (magazine), an online magazine focusing ...](_blank)
of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of
Évariste Galois
Évariste Galois (; ; 25 October 1811 – 31 May 1832) was a French mathematician and political activist. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, ...
, in
Galois theory
In mathematics, Galois theory, originally introduced by Évariste Galois, provides a connection between field theory and group theory. This connection, the fundamental theorem of Galois theory, allows reducing certain problems in field theory to ...
, 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
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
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
. 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 In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set ''S''
is a bijection between two specified subsets of ''S''. That is, it is defined by two subsets ''U'' and ''V'' of equal size, and a one-to-one m ...
or a
k-permutation
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 proc ...
. It can be written as
(which reads "n permute k"), and is equal to the number
(also written as
Definition
In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either
and
, or
and
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
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \m ...
, denoted
, where the
group operation
In mathematics, a group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse. Thes ...
is
function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
. Thus for two permutations,
and
in the group
, the four group axioms hold:
#
Closure: If
and
are in
then so is
#
Associativity
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
: For any three permutations
,
#
Identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), ...
: There is an identity permutation, denoted
and defined by
for all
. For any
,
#
Invertibility: For every permutation
, there exists an inverse permutation
, so that
In general, composition of two permutations is not
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
, that is,
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
In celestial mechanics, an orbit is the curved trajectory of an object such as the trajectory of a planet around a star, or of a natural satellite around a planet, or of an artificial satellite around an object or position in space such as a p ...
, which are found by repeatedly tracing the application of the permutation on some elements. For example, the permutation
defined by
has a 1-cycle,
while the permutation
defined by
and
has a 2-cycle
(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
is called a
fixed point of the permutation. A permutation with no fixed points is called a
derangement
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.
The number of derangements of ...
. 2-cycles are called
transpositions; such permutations merely exchange two elements, leaving the others fixed.
Notations
Since writing permutations elementwise, that is, as
piecewise
In mathematics, a piecewise-defined function (also called a piecewise function, a hybrid function, or definition by cases) is a function defined by multiple sub-functions, where each sub-function applies to a different interval in the domain. Pi ...
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
Baron Augustin-Louis Cauchy (, ; ; 21 August 178923 May 1857) was a French mathematician, engineer, and physicist who made pioneering contributions to several branches of mathematics, including mathematical analysis and continuum mechanics. He w ...
'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
:
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:
:
or
:
One-line notation
If there is a "natural" order for the elements of ''S'', say
, then one uses this for the first row of the two-line notation:
:
Under this assumption, one may omit the first row and write the permutation in ''one-line notation'' as
:
,
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
A word is a basic element of language that carries an semantics, objective or pragmatics, practical semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of w ...
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
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. 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, this is referred to as "decomposition into disjoint cycles".
To write down the permutation
in cycle notation, one proceeds as follows:
# Write an opening bracket then select an arbitrary element ''x'' of
and write it down:
# Then trace the orbit of ''x''; that is, write down its values under successive applications of
:
# Repeat until the value returns to ''x'' and write down a closing parenthesis rather than ''x'':
# Now continue with an element ''y'' of ''S'', not yet written down, and proceed in the same way:
# Repeat until all elements of ''S'' are written in cycles.
So the permutation (in one-line notation) could be written as in cycle notation.
While permutations in general do not commute, disjoint cycles do; for example,
In addition, each cycle can be written in different ways, by choosing different starting points; for example,
One may combine these equalities to write the disjoint cycles of a given permutation in many different ways.
1-cycles are often omitted from the cycle notation, provided that the context is clear; for any element ''x'' in ''S'' not appearing in any cycle, one implicitly assumes
. The
identity permutation
In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to its ...
, which consists only of 1-cycles, can be denoted by a single 1-cycle (x), by the number 1, or by ''id''.
A convenient feature of cycle notation is that cycle notation of the inverse permutation is given by reversing the order of the elements in the permutation's cycles. For example,
Canonical cycle notation
In some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves.
Miklós Bóna
Miklós Bóna (born October 6, 1967, in Székesfehérvár) is an American mathematician of Hungarian origin.
Bóna completed his undergraduate studies in Budapest and Paris, then obtained his Ph.D. at MIT in 1997 as a student of Richard P. Sta ...
calls the following ordering choices the ''canonical cycle notation'':
* in each cycle the ''largest'' element is listed first
* the cycles are sorted in ''increasing'' order of their first element
For example, (312)(54)(8)(976) is a permutation in canonical cycle notation. The canonical cycle notation does not omit one-cycles.
Richard P. Stanley
Richard Peter Stanley (born June 23, 1944) is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He r ...
calls the same choice of representation the "standard representation" of a permutation,
and Martin Aigner uses the term "standard form" for the same notion.
Sergey Kitaev also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its least element first and the cycles are sorted in decreasing order of their least, that is, first elements.
Composition of permutations
There are two ways to denote the composition of two permutations.
is the function that maps any element ''x'' of the set to
. The rightmost permutation is applied to the argument first,
because of the way the function application is written.
Since
function composition
In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
is
associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
, so is the composition operation on permutations:
. Therefore, products of more than two permutations are usually written without adding parentheses to express grouping; they are also usually written without a dot or other sign to indicate composition.
Some authors prefer the leftmost factor acting first,
but to that end permutations must be written to the ''right'' of their argument, often as an exponent, where ''σ'' acting on ''x'' is written ''x''
''σ''; then the product is defined by . However this gives a ''different'' rule for multiplying permutations; this article uses the definition where the rightmost permutation is applied first.
Other uses of the term ''permutation''
The concept of a permutation as an ordered arrangement admits several generalizations that are not permutations, but have been called permutations in the literature.
''k''-permutations of ''n''
A weaker meaning of the term ''permutation'', sometimes used in elementary combinatorics texts, designates those ordered arrangements in which no element occurs more than once, but without the requirement of using all the elements from a given set. These are not permutations except in special cases, but are natural generalizations of the ordered arrangement concept. Indeed, this use often involves considering arrangements of a fixed length ''k'' of elements taken from a given set of size ''n'', in other words, these ''k''-permutations of ''n'' are the different ordered arrangements of a ''k''-element subset of an ''n''-set (sometimes called variations or arrangements in older literature). These objects are also known as
partial permutations or as sequences without repetition, terms that avoid confusion with the other, more common, meaning of "permutation". The number of such
-permutations of
is denoted variously by such symbols as
,
,
,
, or
, and its value is given by the product
:
,
which is 0 when , and otherwise is equal to
:
The product is well defined without the assumption that
is a non-negative integer, and is of importance outside combinatorics as well; it is known as the
Pochhammer symbol
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
:\begin
(x)_n = x^\underline &= \overbrace^ \\
&= \prod_^n(x-k+1) = \prod_^(x-k) \,.
\e ...
or as the
-th falling factorial power
of
.
This usage of the term ''permutation'' is closely related to the term ''
combination
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
''. A ''k''-element combination of an ''n''-set ''S'' is a ''k'' element subset of ''S'', the elements of which are not ordered. By taking all the ''k'' element subsets of ''S'' and ordering each of them in all possible ways, we obtain all the ''k''-permutations of ''S''. The number of ''k''-combinations of an ''n''-set, ''C''(''n'',''k''), is therefore related to the number of ''k''-permutations of ''n'' by:
:
These numbers are also known as
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s and are denoted by
.
Permutations with repetition
Ordered arrangements of ''k'' elements of a set ''S'', where repetition is allowed, are called
''k''-tuples. They have sometimes been referred to as permutations with repetition, although they are not permutations in general. They are also called
words
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...
over the alphabet ''S'' in some contexts. If the set ''S'' has ''n'' elements, the number of ''k''-tuples over ''S'' is
There is no restriction on how often an element can appear in an ''k''-tuple, but if restrictions are placed on how often an element can appear, this formula is no longer valid.
Permutations of multisets
![Permutations with repetition](https://upload.wikimedia.org/wikipedia/commons/4/4f/Permutations_with_repetition.svg)
If ''M'' is a finite
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
, then a multiset permutation is an ordered arrangement of elements of ''M'' in which each element appears a number of times equal exactly to its multiplicity in ''M''. An
anagram
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word ''anagram'' itself can be rearranged into ''nag a ram'', also the word ...
of a word having some repeated letters is an example of a multiset permutation. If the multiplicities of the elements of ''M'' (taken in some order) are
,
, ...,
and their sum (that is, the size of ''M'') is ''n'', then the number of multiset permutations of ''M'' is given by the
multinomial coefficient
In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.
Theorem
For any positive integer an ...
,
:
For example, the number of distinct anagrams of the word MISSISSIPPI is:
:
.
A ''k''-permutation of a multiset ''M'' is a sequence of length ''k'' of elements of ''M'' in which each element appears ''a number of times less than or equal to'' its multiplicity in ''M'' (an element's ''repetition number'').
Circular permutations
Permutations, when considered as arrangements, are sometimes referred to as ''linearly ordered'' arrangements. In these arrangements there is a first element, a second element, and so on. If, however, the objects are arranged in a circular manner this distinguished ordering no longer exists, that is, there is no "first element" in the arrangement, any element can be considered as the start of the arrangement. The arrangements of objects in a circular manner are called circular permutations. These can be formally defined as
equivalence classes
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
of ordinary permutations of the objects, for the
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
generated by moving the final element of the linear arrangement to its front.
Two circular permutations are equivalent if one can be rotated into the other (that is, cycled without changing the relative positions of the elements). The following four circular permutations on four letters are considered to be the same.
1 4 2 3
4 3 2 1 3 4 1 2
2 3 1 4
The circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.
1 1
4 3 3 4
2 2
The number of circular permutations of a set ''S'' with ''n'' elements is (''n'' – 1)!.
Properties
The number of permutations of distinct objects is !.
The number of -permutations with disjoint cycles is the signless
Stirling number of the first kind
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed poin ...
, denoted by .
Cycle type
The cycles (including the fixed points) of a permutation
of a set with elements partition that set; so the lengths of these cycles form an
integer partition
In number theory and combinatorics, a partition of a positive integer , also called an integer partition, is a way of writing as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same part ...
of , which is called the cycle type (or sometimes cycle structure or cycle shape) of
. There is a "1" in the cycle type for every fixed point of
, a "2" for every transposition, and so on. The cycle type of
is
This may also be written in a more compact form as .
More precisely, the general form is