Editing Permutation (section)

===Numbering permutations===
<!-- linked from redirect [[Rothe diagram]] -->
One way to represent permutations of ''n'' things is by an integer ''N'' with 0&nbsp;≤&nbsp;''N''&nbsp;&lt;&nbsp;''n''!, provided convenient methods are given to convert between the number and the representation of a permutation as an ordered arrangement (sequence). This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when ''n'' is small enough that ''N'' can be held in a machine word; for 32-bit words this means ''n''&nbsp;≤&nbsp;12, and for 64-bit words this means ''n''&nbsp;≤&nbsp;20. The conversion can be done via the intermediate form of a sequence of numbers ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub>, where ''d''<sub>''i''</sub> is a non-negative integer less than ''i'' (one may omit ''d''<sub>1</sub>, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is to simply express ''N'' in the ''[[factorial number system]]'', which is just a particular [[mixed radix]] representation, where, for numbers less than ''n''!, the bases (place values or multiplication factors) for successive digits are {{math|(''n'' − 1)!}}, {{math|(''n'' − 2)!}}, ..., 2!, 1!. The second step interprets this sequence as a [[Lehmer code]] or (almost equivalently) as an inversion table.

{| class="wikitable" style="float:right; text-align:center; margin: 1em"
|+ Rothe diagram for <math>\sigma = (6, 3, 8, 1, 4, 9, 7, 2, 5)</math>
|-
! {{diagonal split header|<sub>''i''</sub>| <sup>''σ''<sub>''i''</sub></sup>}}
! style="width:20pt;"| 1
! style="width:20pt;"| 2
! style="width:20pt;"| 3
! style="width:20pt;"| 4
! style="width:20pt;"| 5
! style="width:20pt;"| 6
! style="width:20pt;"| 7
! style="width:20pt;"| 8
! style="width:20pt;"| 9
! Lehmer code
|-
! 1
| × || × || × || × || × || • ||   ||   ||   || ''d''<sub>9</sub> = 5
|-
! 2
| × || × || • ||   ||   ||   ||   ||   ||   || ''d''<sub>8</sub> = 2
|-
! 3
| × || × ||   || × || × ||   || × || • ||   || ''d''<sub>7</sub> = 5
|-
! 4
| • ||   ||   ||   ||   ||   ||   ||   ||   || ''d''<sub>6</sub> = 0
|-
! 5
|   || × ||   || • ||   ||   ||   ||   ||   || ''d''<sub>5</sub> = 1
|-
! 6
|   || × ||   ||   || × ||   || × ||   || • || ''d''<sub>4</sub> = 3
|-
! 7
|   || × ||   ||   || × ||   || • ||   ||   || ''d''<sub>3</sub> = 2
|-
! 8
|   || • ||   ||   ||   ||   ||   ||   ||   || ''d''<sub>2</sub> = 0
|-
! 9
|   ||   ||   ||   || • ||   ||   ||   ||   || ''d''<sub>1</sub> = 0
|-
! Inversion table
| 3 || 6 || 1 || 2 || 4 || 0 || 2 || 0 || 0 ||
|}
In the '''Lehmer code''' for a permutation&nbsp;''σ'', the number ''d''<sub>''n''</sub> represents the choice made for the first term&nbsp;''σ''<sub>1</sub>, the number ''d''<sub>''n''−1</sub> represents the choice made for the second term
''σ''<sub>2</sub> among the remaining {{math|''n'' − 1}} elements of the set, and so forth. More precisely, each ''d''<sub>''n''+1−''i''</sub> gives the number of ''remaining'' elements strictly less than the term ''σ''<sub>''i''</sub>. Since those remaining elements are bound to turn up as some later term ''σ''<sub>''j''</sub>, the digit ''d''<sub>''n''+1−''i''</sub> counts the ''inversions'' (''i'',''j'') involving ''i'' as smaller index (the number of values ''j'' for which ''i''&nbsp;&lt;&nbsp;''j'' and ''σ''<sub>''i''</sub>&nbsp;&gt;&nbsp;''σ''<sub>''j''</sub>). The '''inversion table''' for&nbsp;''σ'' is quite similar, but here ''d''<sub>''n''+1−''k''</sub> counts the number of inversions (''i'',''j'') where ''k''&nbsp;=&nbsp;''σ''<sub>''j''</sub> occurs as the smaller of the two values appearing in inverted order.{{sfn|Knuth|1973|p=12}}

Both encodings can be visualized by an ''n''&nbsp;by&nbsp;''n'' '''Rothe diagram'''{{#tag:ref|[[Heinrich August Rothe|H. A. Rothe]], ''Sammlung combinatorisch-analytischer Abhandlungen'' '''2''' (Leipzig, 1800), 263–305. Cited in {{harvnb|Knuth|1973|p=14}}}} (named after [[Heinrich August Rothe]]) in which dots at (''i'',''σ''<sub>''i''</sub>) mark the entries of the permutation, and a cross at (''i'',''σ''<sub>''j''</sub>) marks the inversion (''i'',''j''); by the definition of inversions a cross appears in any square that comes both before the dot (''j'',''σ''<sub>''j''</sub>) in its column, and before the dot (''i'',''σ''<sub>''i''</sub>) in its row. The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa.

To effectively convert a Lehmer code ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> into a permutation of an ordered set ''S'', one can start with a list of the elements of ''S'' in increasing order, and for ''i'' increasing from 1 to ''n'' set ''σ''<sub>''i''</sub> to the element in the list that is preceded by ''d''<sub>''n''+1−''i''</sub> other ones, and remove that element from the list. To convert an inversion table ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> into the corresponding permutation, one can traverse the numbers from ''d''<sub>1</sub> to ''d''<sub>''n''</sub> while inserting the elements of ''S'' from largest to smallest into an initially empty sequence; at the step using the number ''d'' from the inversion table, the element from ''S'' inserted into the sequence at the point where it is preceded by ''d'' elements already present. Alternatively one could process the numbers from the inversion table and the elements of ''S'' both in the opposite order, starting with a row of ''n'' empty slots, and at each step place the element from ''S'' into the empty slot that is preceded by ''d'' other empty slots.

Converting successive natural numbers to the factorial number system produces those sequences in [[lexicographic order]] (as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used (using inversion tables, one gets a different ordering, where one starts by comparing permutations by the ''place'' of their entries 1 rather than by the value of their first entries). The sum of the numbers in the factorial number system representation gives the number of inversions of the permutation, and the parity of that sum gives the [[signature (permutation)|signature]] of the permutation. Moreover, the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation (in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima (in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations. A permutation with Lehmer code ''d''<sub>''n''</sub>, ''d''<sub>''n''−1</sub>, ..., ''d''<sub>2</sub>, ''d''<sub>1</sub> has an ascent {{math|''n'' − ''i''}} if and only if {{math|''d''<sub>''i''</sub> ≥ ''d''<sub>''i''+1</sub>}}.