Editing Permutation (section)

==Definition==

In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either <math>\alpha,\beta,\gamma</math> or <math>\sigma, \tau,\rho,\pi</math> are used.<ref name="Scheinerman">{{cite book |last1=Scheinerman |first1=Edward A. |date=March 5, 2012 |chapter=Chapter 5: Functions |title=Mathematics: A Discrete Introduction |chapter-url=https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA188 |url-status=live |edition=3rd |publisher=Cengage Learning |page=188 |isbn=978-0840049421 |archive-url=https://web.archive.org/web/20200205212843/https://books.google.com/books?id=DZBHGD2sEYwC&pg=PA188 |archive-date=February 5, 2020 |access-date=February 5, 2020 |quote=It is customary to use lowercase Greek letters (especially π, σ, and τ) to stand for permutations.}}</ref>

A permutation can be defined as a [[bijection]] (an invertible mapping, a one-to-one and onto function) from a set {{math|''S''}} to itself: <blockquote><math>\sigma : S\ \stackrel{\sim}{\longrightarrow}\ S.</math> </blockquote>The [[identity permutation]] is defined by <math>\sigma(x) = x  </math> for all elements <math>x\in S  </math>, and can be denoted by the number <math>1</math>,{{efn|1 is frequently used to represent the [[identity element]] in a non-commutative group}} by <math>\text{id}= \text{id}_S   </math>, or by a single 1-cycle (x).<ref>{{harvnb|Rotman|2002|p=41}}</ref><ref>{{harvnb|Bogart|1990|p=487}}</ref>

The set of all permutations of a set with ''n'' elements forms the [[symmetric group]] <math>S_n</math>, where the [[group operation]] is [[composition of functions]]. Thus for two permutations <math>\sigma</math> and <math>\tau</math> in the group <math>S_n</math>, their product <math>\pi = \sigma\tau</math> is defined by: <blockquote><math>\pi(i)=\sigma(\tau(i)).</math> </blockquote>Composition is usually written without a dot or other sign. In general, composition of two permutations is not [[commutative]]: <math>\tau\sigma \neq \sigma\tau.</math>

As a bijection from a set to itself, a permutation is a function that ''performs'' a rearrangement of a set, termed an ''active permutation'' or ''substitution''. An older viewpoint sees a permutation as an ordered arrangement or list of all the elements of ''S'', called a ''passive permutation''.{{sfn|Cameron|1994|loc=p. 29, footnote 3}} According to this definition, all permutations in {{Section link||One-line notation}} are passive. This meaning is subtly distinct from how passive (i.e. ''alias'') is used in [[Active and passive transformation]] and elsewhere,<ref>{{cite book |last1=Conway |first1=John H. |last2=Burgiel |first2=Heidi |last3=Goodman-Strauss |first3=Chaim |date=2008 |title=The Symmetries of Things |publisher=A K Peters |page=179 |quote=A permutation---say, of the names of a number of people---can be thought of as moving either the names or the people.  The alias viewpoint regards the permutation as assigning a new name or ''alias'' to each person (from the Latin ''alias'' = otherwise).  Alternatively, from the alibi viewoint we move the people to the places corresponding to their new names (from the Latin ''alibi'' = in another place.) }}</ref><ref>{{Cite web |title=Permutation notation - Wikiversity |url=https://en.wikiversity.org/wiki/Permutation_notation |access-date=2024-08-04 |website=en.wikiversity.org |language=en}}</ref> which would consider all permutations open to passive interpretation (regardless of whether they are in one-line notation, two-line notation, etc.).

A permutation <math>\sigma</math> can be decomposed into one or more disjoint ''cycles'' which are the [[Orbit (group theory)|orbits]] of the cyclic group <math>\langle\sigma\rangle = \{1, \sigma, \sigma^2,\ldots\} </math> [[Group action|acting]] on the set ''S''. A cycle is found by repeatedly applying the permutation to an element: <math>x, \sigma(x),\sigma(\sigma(x)),\ldots, \sigma^{k-1}(x)</math>, where we assume <math>\sigma^k(x)=x</math> . A cycle consisting of ''k'' elements is called a ''k''-cycle. (See {{Section link||Cycle notation}} below.)

A [[Fixed point (mathematics)|fixed point]] of a permutation <math>\sigma</math> is an element ''x'' which is taken to itself, that is <math>\sigma(x)=x </math>, forming a 1-cycle <math>(\,x\,)</math>. A permutation with no fixed points is called a [[derangement]]. A permutation exchanging two elements (a single 2-cycle) and leaving the others fixed is called a [[transposition (mathematics)|transposition]].