Editing Permutation (section)

==History==
Permutation-like objects called [[Hexagram (I Ching)|hexagrams]] were used in China in the [[I Ching]] ([[Pinyin]]: Yi Jing) as early as 1000 BC.

In Greece, [[Plutarch]] wrote that [[Xenocrates]] of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations.<ref>{{Cite book |last=Heath |first=Thomas Little |url=https://www.worldcat.org/oclc/7703465 |title=A History of Greek Mathematics |date=1981 |publisher=Dover Publications |isbn=0-486-24073-8 |location=New York |oclc=7703465}}</ref>

[[Al-Khalil ibn Ahmad al-Farahidi|Al-Khalil]] (717–786), an [[Mathematics in medieval Islam|Arab mathematician]] and [[cryptographer]], wrote the ''Book of Cryptographic Messages''. It contains the first use of permutations and combinations, to list all possible [[Arabic language|Arabic]] words with and without vowels.<ref name="LB">{{cite journal|last=Broemeling|first=Lyle D.|title=An Account of Early Statistical Inference in Arab Cryptology|journal=The American Statistician|date=1 November 2011|volume=65|issue=4|pages=255–257|doi=10.1198/tas.2011.10191|s2cid=123537702}}</ref>

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 [[Bhāskara II]] contains a passage that translates as follows:
<blockquote>
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.<ref>{{cite journal |first=N. L. |last=Biggs |title=The Roots of Combinatorics |journal=Historia Math. |volume=6 |year=1979 |issue=2 |pages=109–136 |doi=10.1016/0315-0860(79)90074-0 |doi-access= }}</ref>
</blockquote>

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.{{sfn|Stedman|1677|p=4}}  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".{{sfn|Stedman|1677|p=5}}  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.{{sfn|Stedman|1677|pp=6—7}}  At this point he gives up and remarks:
<blockquote>
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;{{sfn|Stedman|1677|p=8}}
</blockquote>
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.{{sfn|Stedman|1677|pp=13—18}}

A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when [[Joseph Louis Lagrange]], in the study of polynomial equations, observed that properties of the permutations of the [[Polynomial#Solving polynomial equations|roots]] 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.

The study of permutations as substitutions on n elements led to the notion of group as algebraic structure, through the works of [[Cauchy]] (1815 memoir).

Permutations played an important role in the [[Cryptanalysis of the Enigma|cryptanalysis of the Enigma machine]], a cipher device used by [[Nazi Germany]] during [[World War II]]. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist [[Marian Rejewski]] to break the German Enigma cipher in turn of years 1932-1933.<ref>{{Cite journal |last=Rejewski |first=Marian |date=1980 |title=An application of the theory of permutations in breaking the Enigma cipher |url=https://eudml.org/doc/264403 |journal=Applicationes Mathematicae |volume=16 |issue=4 |pages=543–559 |doi=10.4064/am-16-4-543-559 |issn=1233-7234|doi-access=free }}</ref><ref>{{Cite web |last=Cash |first=David |date=2019 |title=CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma |url=https://people.cs.uchicago.edu/~davidcash/284-autumn-19/02-permutations-and-enigma.pdf}}</ref>