Editing Factorial number system (section)

== Permutations ==

There is a natural [[function (mathematics)|mapping]] between the integers {{math|0,&nbsp;1,&nbsp;...,&nbsp;''n''!&nbsp;−&nbsp;1}} (or equivalently the numbers with ''n'' digits in factorial representation) and [[permutation]]s of ''n'' elements in [[lexicographical]] order, when the integers are expressed in factoradic form.  This mapping has been termed the [[Lehmer code]] (or inversion table). For example, with {{math|1=''n''&nbsp;=&nbsp;3}}, such a mapping is

{| class="wikitable"
|-
!scope="col"| decimal
!scope="col"| factoradic
!scope="col"| permutation
|-
|0<sub>10</sub>
|0:0:0<sub>!</sub>
|(0,1,2)
|-
|1<sub>10</sub>
|0:1:0<sub>!</sub>
|(0,2,1)
|-
|2<sub>10</sub>
|1:0:0<sub>!</sub>
|(1,0,2)
|-
|3<sub>10</sub>
|1:1:0<sub>!</sub>
|(1,2,0)
|-
|4<sub>10</sub>
|2:0:0<sub>!</sub>
|(2,0,1)
|-
|5<sub>10</sub>
|2:1:0<sub>!</sub>
|(2,1,0)
|}

In each case, calculating the permutation proceeds by using the leftmost factoradic digit (here, 0, 1, or 2) as the first permutation digit, then removing it from the list of choices (0, 1, and 2). Think of this new list of choices as zero indexed, and use each successive factoradic digit to choose from its remaining elements. If the second factoradic digit is "0" then the first element of the list is selected for the second permutation digit and is then removed from the list. Similarly, if the second factoradic digit is "1", the second is selected and then removed. The final factoradic digit is always "0", and since the list now contains only one element, it is selected as the last permutation digit.

The process may become clearer with a longer example.  Let's say we want the 2982nd permutation of the numbers 0 through 6.
The number 2982 is 4:0:4:1:0:0:0<sub>!</sub> in factoradic, and that number picks out digits (4,0,6,2,1,3,5) in turn, via indexing a dwindling ordered set of digits and picking out each digit from the set at each turn:
                             4:0:4:1:0:0:0<sub>!</sub>  ─►  (4,0,6,2,1,3,5)
 factoradic: 4              :   0            :   4          :   1        :   0      :   0    :   0<sub>!</sub>
             ├─┬─┬─┬─┐          │                ├─┬─┬─┬─┐      ├─┐          │          │        │
 sets:      (0,1,2,3,4,5,6) ─► (0,1,2,3,5,6) ─► (1,2,3,5,6) ─► (1,2,3,5) ─► (1,3,5) ─► (3,5) ─► (5)
                     │          │                        │        │          │          │        │
 permutation:       (4,         0,                       6,       2,         1,         3,       5)

A natural index for the [[direct product of groups|direct product]] of two [[permutation group]]s is the [[concatenation]] of two factoradic numbers, with two subscript "!"s.
            concatenated
  decimal   factoradics        permutation pair
     0<sub>10</sub>     0:0:0<sub>!</sub>0:0:0<sub>!</sub>           ((0,1,2),(0,1,2))
     1<sub>10</sub>     0:0:0<sub>!</sub>0:1:0<sub>!</sub>           ((0,1,2),(0,2,1))
                ...
     5<sub>10</sub>     0:0:0<sub>!</sub>2:1:0<sub>!</sub>           ((0,1,2),(2,1,0))
     6<sub>10</sub>     0:1:0<sub>!</sub>0:0:0<sub>!</sub>           ((0,2,1),(0,1,2))
     7<sub>10</sub>     0:1:0<sub>!</sub>0:1:0<sub>!</sub>           ((0,2,1),(0,2,1))
                ...
    22<sub>10</sub>     1:1:0<sub>!</sub>2:0:0<sub>!</sub>           ((1,2,0),(2,0,1))
                ...
    34<sub>10</sub>     2:1:0<sub>!</sub>2:0:0<sub>!</sub>           ((2,1,0),(2,0,1))
    35<sub>10</sub>     2:1:0<sub>!</sub>2:1:0<sub>!</sub>           ((2,1,0),(2,1,0))