In der Kombinatorik wird das fakultätsbasierte Zahlensystem verwendet, um einen eindeutigen Index für Permutationen zu erzeugen.
Definition Bearbeiten
Das fakultätsbasierte Zahlensystem ist das Zahlensystem, das die Folge der ersten natürlichen Zahlen als Grundzahlen, und damit die Fakultäten als Moduln hat.
| Stelle: | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Grundzahl: | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| Ziffern ≤ | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Stellenwert (Modul): | 7! | 6! | 5! | 4! | 3! | 2! | 1! | 0! |
| in Dezimaldarstellung: | 5040 | 720 | 120 | 24 | 6 | 2 | 1 | 1 |
In diesem Zahlensystem ist die Stelle ganz rechts immer 0, die zweite Stelle von rechts 0 oder 1, die dritte 0, 1 oder 2 usw. Es gibt mehrere Varianten des fakultätsbasierten Zahlensystems:
- Die rechte Zahl wird weggelassen, da sie immer 0 ist.
- Nicht die Produkte, sondern die kleinsten gemeinsamen Vielfachen (Folge A003418 in OEIS) bilden die Moduln – und damit die ersten Primfaktoren die Grundzahlen.
Beispiel Bearbeiten
Die Zahl 35 würde man in diesem Zahlensystem folgendermaßen schreiben.
Eigenschaften Bearbeiten
Die Summe der aufeinanderfolgenden Fakultäten, multipliziert mit ihrem Index, ist immer die nächste Fakultät minus eins:
Daher kann jede Zahl in diesem Zahlensystem dargestellt werden und diese Darstellung ist eindeutig, d. h. keine Zahl kann auf mehr als eine Art dargestellt werden.
Allerdings benötigt man dafür eine unendliche Anzahl an Zeichen. Die einfache Verknüpfung von dezimalen Ziffern wäre mehrdeutig für Zahlen mit einer „Ziffer“, die größer als 9 ist. Das kleinste Beispiel hierfür ist die Zahl 10×10!, ausgeschrieben 101009080706050403020100, wobei 11! 11101009080706050403020100 ist. Daher reicht ein einzelnes Subskript (wie im Dezimalsystem) für Zahlen mit mehr als 10 Stellen nicht aus.
Lenstra lässt in Lenstra Profinite Fibonacci numbers S. 297 die immer gleichen Subskripte weg, stellt bei mehrstelligen (Fakultäts-)Ziffern alle Dezimalziffern bis auf die letzte hoch und terminiert mit dem Suffix !, so dass
| 10×10! | = 101009080706050403020100 |
| = 100000000000! |
ist.
Anwendung Bearbeiten
Das fakultätsbasierte Zahlensystem wird benutzt, um eine kanonische Zuordnung zwischen den ganzen Zahlen (bzw. den äquivalenten Zahlen mit n Stellen im fakultätsbasierten Zahlensystem) und Permutationen von n Elementen in lexikographischer Reihenfolge vorzunehmen, wenn die ganzen Zahlen bezüglich dieses Zahlensystems dargestellt werden. Diese Zuordnung wird Lehmer-Code oder Lucas-Lehmer-Code genannt. Zum Beispiel ergibt sich mit n = 3 folgende Zuordnung:
| dezimal | fakultätsbasiert | Permutation |
|---|---|---|
| 010 | 020100 | (0,1,2) |
| 110 | 021100 | (0,2,1) |
| 210 | 120100 | (1,0,2) |
| 310 | 121100 | (1,2,0) |
| 410 | 220100 | (2,0,1) |
| 510 | 221100 | (2,1,0) |
dabei wählt die linke Ziffer 0, 1 oder 2 sich selbst als Permutationsziffer aus der sortierten Liste (0,1,2) aus und entfernt sich aus der Liste. Es entsteht eine kürzere Liste, bei der die erste Permutationsziffer fehlt. Mit der zweiten Ziffer wird die zweite Permutationsziffer ausgewählt. Dabei beginnt das Abzählen mit 0. Das Element wird aus der Liste wieder entfernt. Die dritte Stelle ist „0“. Da die Liste nur noch ein Element enthält, wird dieses als letzte Permutationsziffer ausgewählt.
Dieser Vorgang wird mit einem längeren Beispiel deutlicher. Im Folgenden werden mit den Ziffern aus dem fakultätsbasierten Zahlensystem 46054413020100 die Ziffern aus der Permutation (4,0,6,2,1,3,5) erzeugt.
46054413020100 → (4,0,6,2,1,3,5) Fakultätsbasiert: 46 05 44 13 02 01 00 | | | | | | | (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)
Der natürliche Index für die direkte Summe zweier Permutationen ist einfach die Konkatenation.
| dezimal | fakultätsbasiert | Permutationspaar |
|---|---|---|
| 010 | 020100020100 | ((0,1,2),(0,1,2)) |
| 110 | 020100021100 | ((0,1,2),(0,2,1)) |
| ... | ||
| 510 | 020100221100 | ((0,1,2),(2,1,0)) |
| 610 | 021100020100 | ((0,2,1),(0,1,2)) |
| 710 | 021100021100 | ((0,2,1),(0,2,1)) |
| ... | ||
| 2210 | 121100220100 | ((1,2,0),(2,0,1)) |
| ... | ||
| 3410 | 221100220100 | ((2,1,0),(2,0,1)) |
| 3510 | 221100221100 | ((2,1,0),(2,1,0)) |
Siehe auch Bearbeiten
Literatur Bearbeiten
- Donald Knuth. The Art of Computer Programming. Volume 2: Seminumerical Algorithms. Third Edition. Addison-Wesley, 1997, ISBN 0-201-89684-2, S. 65–66 (englisch).
Weblinks Bearbeiten
- C.- A. Laisant: Sur la numération factorielle, application aux permutations. In: Bulletin de la Société Mathématique de France, 16, 1888, S. 176–183 (französisch)
- 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 (englisch).
- Roberto Mantaci, Fanja Rakotondrajao: A permutation representation that knows what ‘Eulerian’ means. (PDF; 90 kB) Description and references for Lehmer codes (englisch)
- 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 (englisch).
- Hendrik Lenstra: Profinite Fibonacci numbers. (PDF; 351 kB)