Editing Permutation (section)

=== Foata's transition lemma ===
[[Dominique Foata|Foata]]'s ''fundamental bijection'' transforms a permutation {{mvar|&sigma;}} with a given canonical cycle form into the permutation <math>f(\sigma) = \hat\sigma   </math> whose one-line notation has the same sequence of elements with parentheses removed.<ref name="Stanley2012" />{{sfn|Bona|2012|pp=109–110}} For example:
<math display="block">\sigma = (513)(6)(827)(94)
= \begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
3&7&5&9&1&6&8&2&4
\end{pmatrix},
</math>

<math display="block">\hat\sigma = 513682794
= \begin{pmatrix}
1&2&3&4&5&6&7&8&9\\
5&1&3&6&8&2&7&9&4
\end{pmatrix}.
</math>

Here the first element in each canonical cycle of {{mvar|&sigma;}} becomes a record (left-to-right maximum) of <math>\hat\sigma
</math>. Given <math>\hat\sigma
</math>, one may find its records and insert parentheses to construct the inverse transformation <math>\sigma=f^{-1}(\hat\sigma)
</math>. Underlining the records in the above example: <math>\hat\sigma = \underline{5}\, 1\, 3\, \underline{6}\, \underline{8}\,2\,7\,\underline{9}\,4
</math>, which allows the reconstruction of the cycles of {{mvar|&sigma;}}.

The following table shows <math>\hat\sigma  </math> and {{mvar|&sigma;}} for the six permutations of ''S'' = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for <math>\hat\sigma  </math> and canonical cycle notation for {{mvar|&sigma;}}.

<math display="block">
\begin{array}{l|l}
\hat\sigma = f(\sigma)           & \sigma=f^{-1}(\hat\sigma) 
\\
\hline
\mathbf{123}=(\,1\,)(\,2\,)(\,3\,) & 123=\mathbf{(\,1\,)(\,2\,)(\,3\,)}
\\
\mathbf{132}=(\,1\,)(\,3\,2\,) & 132=\mathbf{(\,1\,)(\,3\,2\,)}
\\
\mathbf{213}=(\,2\,1\,)(\,3\,) & 213=\mathbf{(\,2\,1\,)(\,3\,)} 
\\
\mathbf{231}=(\,3\,1\,2\,) & 321=\mathbf{(\,2\,)(\,3\,1\,)} 
\\
\mathbf{312}=(\,3\,2\,1\,) & 231=\mathbf{(\,3\,1\,2\,)} 
\\
\mathbf{321}=(\,2\,)(\,3\,1\,) & 312=\mathbf{(\,3\,2\,1\,)}
\end{array}
</math>
As a first corollary, the number of ''n''-permutations with exactly ''k'' records is equal to the number of ''n''-permutations with exactly ''k'' cycles: this last number is the signless [[Stirling number of the first kind]], <math>c(n, k)</math>. Furthermore, Foata's mapping takes an ''n''-permutation with ''k'' weak exceedances to an ''n''-permutation with {{math|''k'' − 1}} ascents.{{sfn|Bona|2012|pp=109–110}}  For example, (2)(31) = 321 has ''k ='' 2 weak exceedances (at index 1 and 2), whereas {{math|''f''(321) {{=}} 231}} has {{math|1=''k'' − 1 = 1}} ascent (at index 1; that is, from 2 to 3).