Faculty-based number system

In combinatorics , the faculty-based number system is used to generate a unique index for permutations .

definition

The faculty-based number system is the number system that has the sequence of the first natural numbers as basic numbers, and thus the faculties as modules .

Job:	7th	6th	5	4th	3	2	1	0
Base number:	8th	7th	6th	5	4th	3	2	1
Digits ≤	7th	6th	5	4th	3	2	1	0
Significance (module):	7!	6!	5!	4!	3!	2!	1!	0!
in decimal notation:	5040	720	120	24	6th	2	1	1

In this number system, the rightmost digit is always 0, the second digit from the right 0 or 1, the third 0, 1 or 2, etc. There are several variants of the faculty-based number system:

The right number is omitted because it is always 0.
Not the products, but the smallest common multiple (sequence A003418 in OEIS ) form the modules - and thus the first prime factors form the basic numbers. ${\ displaystyle P_ {n}: = \ operatorname {kgV} (1,2, \ dots, n)}$

example

The number 35 in this number system would be written as follows.

${\ displaystyle 35 = 1 \ times 4! +1 \ times 3! +2 \ times 2! +1 \ times 1! +0 \ times 0! = 1_ {4} 1_ {3} 2_ {2} 1_ {1 } 0_ {0}}$

properties

The sum of the successive faculties , multiplied by their index, is always the next factorial minus one:

{\ displaystyle \ sum _ {i = 0} ^ {n} {i \ cdot i!} = {(n + 1)!} - 1.}

Therefore any number can be represented in this number system and this representation is unambiguous, i.e. H. no number can be represented in more than one way.

However, you need an infinite number of characters for this. The simple combination of decimal digits would be ambiguous for numbers with a “digit” greater than 9. The smallest example of this is the number 10 × 10 !, written out in full 10 ₁₀ 0 ₉ 0 ₈ 0 ₇ 0 ₆ 0 ₅ 0 ₄ 0 ₃ 0 ₂ 0 ₁ 0 ₀ , where 11! 1 ₁₁ 0 ₁₀ 0 ₉ 0 ₈ 0 ₇ 0 ₆ 0 ₅ 0 ₄ 0 ₃ 0 ₂ 0 ₁ 0 ₀ is. Therefore, a single subscription (as in the decimal system ) is insufficient for numbers with more than 10 digits.

Lenstra omits the same subscriptions in Lenstra Profinite Fibonacci numbers p. 297 , places all decimal digits up to the last one in the case of multi-digit (faculty) digits and terminates with the suffix _!, so that

10 × 10!	= 10 ₁₀ 0 ₉ 0 ₈ 0 ₇ 0 ₆ 0 ₅ 0 ₄ 0 ₃ 0 ₂ 0 ₁ 0 ₀
	= ¹ 00000000000 _!

is.

application

The faculty-based number system is used to make a canonical assignment between the whole numbers (or the equivalent numbers with n digits in the faculty-based number system) and permutations of n elements in lexicographical order when the whole numbers are represented in relation to this number system. This assignment is called the Lehmer Code or Lucas-Lehmer Code. For example, with n = 3 the following assignment results : ${\ displaystyle 0, \ dots, n! -1}$

decimal	faculty-based	permutation
0 ₁₀	0 ₂ 0 ₁ 0 ₀	(0,1,2)
1 ₁₀	0 ₂ 1 ₁ 0 ₀	(0.2.1)
2 ₁₀	1 ₂ 0 ₁ 0 ₀	(1.0.2)
3 ₁₀	1 ₂ 1 ₁ 0 ₀	(1,2,0)
4 ₁₀	2 ₂ 0 ₁ 0 ₀	(2.0.1)
5 ₁₀	2 ₂ 1 ₁ 0 ₀	(2.1.0)

the left digit 0, 1 or 2 selects itself as the permutation digit from the sorted list (0,1,2) and removes itself from the list. A shorter list is created in which the first permutation digit is missing. The second digit is used to select the second permutation digit. The counting starts with 0. The element is removed from the list. The third digit is "0". Since the list only contains one element, this is selected as the last permutation digit.

This process becomes clearer with a longer example. In the following, the digits from the faculty-based number system 4 ₆ 0 ₅ 4 ₄ 1 ₃ 0 ₂ 0 ₁ 0 ₀ are used to generate the digits from the permutation (4,0,6,2,1,3,5).

                                 4₆0₅4₄1₃0₂0₁0₀ → (4,0,6,2,1,3,5)
Fakultätsbasiert: 4₆        0₅                      4₄      1₃        0₂        0₁      0₀
                  |         |                       |       |         |         |       |
         (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)

The natural index for the direct sum of two permutations is simply the concatenation .

decimal	faculty-based	Permutation pair
0 ₁₀	0 ₂ 0 ₁ 0 ₀ 0 ₂ 0 ₁ 0 ₀	((0,1,2), (0,1,2))
1 ₁₀	0 ₂ 0 ₁ 0 ₀ 0 ₂ 1 ₁ 0 ₀	((0,1,2), (0,2,1))
...
5 ₁₀	0 ₂ 0 ₁ 0 ₀ 2 ₂ 1 ₁ 0 ₀	((0,1,2), (2,1,0))
6 ₁₀	0 ₂ 1 ₁ 0 ₀ 0 ₂ 0 ₁ 0 ₀	((0,2,1), (0,1,2))
7 ₁₀	0 ₂ 1 ₁ 0 ₀ 0 ₂ 1 ₁ 0 ₀	((0.2.1), (0.2.1))
...
22 ₁₀	1 ₂ 1 ₁ 0 ₀ 2 ₂ 0 ₁ 0 ₀	((1,2,0), (2,0,1))
...
34 ₁₀	2 ₂ 1 ₁ 0 ₀ 2 ₂ 0 ₁ 0 ₀	((2.1.0), (2.0.1))
35 ₁₀	2 ₂ 1 ₁ 0 ₀ 2 ₂ 1 ₁ 0 ₀	((2.1.0), (2.1.0))

literature

Donald Knuth . The Art of Computer Programming . Volume 2: Seminumerical Algorithms . Third edition. Addison-Wesley, 1997, ISBN 0-201-89684-2 , pp. 65-66 (English).

Web links

C.- A. Laisant: Sur la numération factorielle, application aux permutations . In: Bulletin de la Société Mathématique de France , 16, 1888, pp. 176-183 (French)
James McCaffrey: Using Permutations in .NET for Improved Systems Security . Implementation of factoradics in C # source code
Peter Cameron's Home Page McCaffrey acknowledges Cameron as having first suggested to him using factoradics to index permutations (English).
Roberto Mantaci, Fanja Rakotondrajao: A permutation representation that knows what 'Eulerian' means . (PDF; 90 kB) Description and references for Lehmer codes (English)
A Lehmer code calculator. Note that their permutation digits start from 1, so mentally reduce all permutation digits by one to get results equivalent to the ones on this page.
Hendrik Lenstra: Profinite Fibonacci numbers . (PDF)