Факториальная система счисления

Система счисления в комбинаторике

В комбинаторике факториальная система счисления , также называемая факторадической , является смешанной системой счисления , адаптированной для нумерации перестановок . Она также называется факториальной базой , хотя факториалы не выполняют функцию базы , а являются разрядными значениями цифр. Преобразуя число, меньшее n !, в факториальное представление, можно получить последовательность из n цифр, которую можно преобразовать в перестановку из n элементов простым способом, используя их либо как код Лемера , либо как представление в виде таблицы инверсии ^[1] ; в первом случае полученное отображение целых чисел в перестановки из n элементов перечисляет их в лексикографическом порядке . Общие смешанные системы счисления изучались Георгом Кантором . ^[2]

Термин «факториальная система счисления» был использован Кнутом [ ^3], тогда как французский эквивалент «numération factorielle» был впервые использован в 1888 году ^[4]. Термин «факторадический», который является сочетанием слов факториал и смешанное основание, по-видимому, появился позже. ^[5]

Определение

Факториальная система счисления является смешанной системой счисления : i -я цифра справа имеет основание  i , что означает, что цифра должна быть строго меньше i , и что (с учетом оснований младших цифр) ее значение должно быть умножено на ( i  − 1) ! (ее разрядное значение).

Из этого следует, что самая правая цифра всегда 0, вторая может быть 0 или 1, третья 0, 1 или 2 и т. д. (последовательность A124252 в OEIS ). Факториальная система счисления иногда определяется с опущенным местом 0!, поскольку оно всегда равно нулю (последовательность A007623 в OEIS ).

В этой статье представление факториального числа будет отмечено нижним индексом "!". Кроме того, в некоторых примерах цифры будут разделены двоеточием. Например, 3:4:1:0:1:0 _! обозначает

= 3×5! + 4х4! + 1×3! + 0×2! + 1×1! + 0×0! 

= ((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0

= 463 ₁₀ .

(Значение разряда — это факториал на единицу меньше позиции основания, поэтому уравнение начинается с 5! для 6-значного факторадического числа.)

Общие свойства смешанных систем счисления применяются также к факториальной системе счисления. Например, можно преобразовать число в факториальное представление, производя цифры справа налево, многократно деля число на основание (1, 2, 3, ...), принимая остаток в качестве цифр и продолжая с целым частным , пока это частное не станет равным 0.

Например, 463 ₁₀ можно преобразовать в факториальное представление с помощью следующих последовательных делений:

Процесс завершается, когда частное достигает нуля. Чтение остатков в обратном порядке дает 3:4:1:0:1:0 _! .

В принципе, эта система может быть расширена для представления рациональных чисел , хотя вместо естественного расширения значений разрядов (−1)!, (−2)! и т. д., которые не определены, вместо этого может быть использован симметричный выбор значений основания n = 0, 1, 2, 3, 4 и т. д. после точки. Опять же, разряды 0 и 1 могут быть опущены, поскольку они всегда равны нулю. Соответствующие значения разрядов, таким образом, 1/1, 1/1, 1/2, 1/6, 1/24, ..., 1/ n ! и т. д.

Примеры

Следующая сортируемая таблица показывает 24 перестановки четырех элементов с различными векторами, связанными с инверсией . Левые и правые счетчики инверсии и (последний часто называют кодом Лемера ) особенно подходят для интерпретации в качестве факториальных чисел. дает позицию перестановки в обратном колексикографическом порядке (порядок по умолчанию этой таблицы), а последний позицию в лексикографическом порядке (оба отсчитываются от 0). ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle l}$

Сортировка по столбцу, в котором справа есть опущенный 0, приводит факториальные числа в этом столбце в соответствие с индексными числами в неподвижном столбце слева. Маленькие столбцы являются отражениями столбцов рядом с ними и могут использоваться для приведения их в колексикографический порядок. Самый правый столбец показывает суммы цифр факториальных чисел ( OEIS : A034968 в порядке таблиц по умолчанию).

Факториальные числа заданной длины образуют пермутоэдр , если упорядочить их побитовым отношением. Это правильные счетчики инверсий (они же коды Лемера) перестановок четырех элементов. ${\displaystyle \leq }$

Другой пример: наибольшее число, которое можно представить шестью цифрами, будет 543210 _!, что в десятичной системе счисления равно 719 :

5х5! + 4х4! + 3х3! + 2х2! + 1×1! + 0×0!.

Очевидно, что следующее представление факториального числа после 5:4:3:2:1:0 _! — это 1:0:0:0:0:0:0 _!, что обозначает 6! = 720 ₁₀ , разрядное значение для цифры в системе счисления с основанием 7. Таким образом, первое число и его суммированное выражение выше равны:

6! − 1.

Система факториальных чисел обеспечивает уникальное представление для каждого натурального числа с заданным ограничением на используемые "цифры". Ни одно число не может быть представлено более чем одним способом, поскольку сумма последовательных факториалов, умноженная на их индекс, всегда равна следующему факториалу минус один:

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

Это можно легко доказать с помощью математической индукции или просто заметив, что : последующие члены уничтожают друг друга, оставляя первый и последний члены (см. Телескопический ряд ). ${\displaystyle \forall i,i\cdot i!=(i+1-1)\cdot i!=(i+1)!-i!}$

Однако при использовании арабских цифр для записи цифр (и без учета нижних индексов, как в приведенных выше примерах) их простая конкатенация становится неоднозначной для чисел, имеющих «цифру» больше 9. Наименьшим таким примером является число 10 × 10! = 36 288 000 ₁₀ , которое можно записать как A0000000000 _! =10:0:0:0:0:0:0:0:0:0:0:0 _! , но не 100000000000 _! = 1:0:0:0:0:0:0:0:0:0:0:0:0 _! что обозначает 11! = 39 916 800 ₁₀ . Таким образом, используя буквы A–Z для обозначения цифр 10, 11, 12, ..., 35, как и в других системах счисления с основанием N, получаем наибольшее представимое число 36 × 36! − 1. Для произвольно больших чисел необходимо выбрать основание для представления отдельных цифр, скажем, десятичное, и поставить разделительный знак между ними (например, проставив под каждой цифрой ее основание, также заданное в десятичной системе, например, 2 ₄ 0 ₃ 1 ₂ 0 ₁ , это число также можно записать как 2:0:1:0 _! ). Фактически, сама факториальная система счисления не является истинной числовой системой в том смысле, что она обеспечивает представление всех натуральных чисел с использованием только конечного алфавита символов.

Перестановки

Существует естественное отображение между целыми числами 0, 1, ...,  n ! − 1 (или эквивалентно числами с n цифрами в факториальном представлении) и перестановками n элементов в лексикографическом порядке, когда целые числа выражены в факторадической форме. Это отображение было названо кодом Лемера (или инверсионной таблицей). Например, при n =  3 такое отображение имеет вид

В каждом случае вычисление перестановки происходит с использованием самой левой факторадической цифры (здесь 0, 1 или 2) в качестве первой цифры перестановки, а затем удалением ее из списка вариантов (0, 1 и 2). Думайте об этом новом списке вариантов как о нулевом индексе и используйте каждую последующую факторадическую цифру для выбора из его оставшихся элементов. Если вторая факторадическая цифра равна «0», то первый элемент списка выбирается для второй цифры перестановки и затем удаляется из списка. Аналогично, если вторая факторадическая цифра равна «1», то выбирается вторая и затем удаляется. Последняя факторадическая цифра всегда равна «0», и поскольку список теперь содержит только один элемент, он выбирается как последняя цифра перестановки.

Процесс может стать более понятным с помощью более длинного примера. Допустим, нам нужна 2982-я перестановка чисел от 0 до 6. Число 2982 — это 4:0:4:1:0:0:0 _! в факторадике, и это число выбирает цифры (4,0,6,2,1,3,5) по очереди, индексируя уменьшающийся упорядоченный набор цифр и выбирая каждую цифру из набора на каждом шаге:

 4:0:4:1:0:0:0 ! ─► (4,0,6,2,1,3,5)факторадик: 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) │ │ │ │ │ │ │перестановка: (4, 0, 6, 2, 1, 3, 5)

Естественным индексом для прямого произведения двух групп перестановок является конкатенация двух факторадических чисел с двумя нижними индексами «!».

 объединенный десятичные факторадики перестановочная пара 0 10 0:0:0 ! 0:0:0 ! ((0,1,2),(0,1,2)) 1 10 0:0:0 ! 0:1:0 ! ((0,1,2),(0,2,1)) ... 5 10 0:0:0 ! 2:1:0 ! ((0,1,2),(2,1,0)) 6 10 0:1:0 ! 0:0:0 ! ((0,2,1),(0,1,2)) 7 10 0:1:0 ! 0:1:0 ! ((0,2,1),(0,2,1)) ... 22 10 1:1:0 ! 2:0:0 ! ((1,2,0),(2,0,1)) ... 34 10 2:1:0 ! 2:0:0 ! ((2,1,0),(2,0,1)) 35 10 2:1:0 ! 2:1:0 ! ((2,1,0),(2,1,0))

Дробные значения

В отличие от систем счисления с одним основанием, в которых разрядные значения имеют основание ⁿ как для положительных, так и для отрицательных целых чисел n , основание факториала не может быть расширено до отрицательных разрядных значений, поскольку они будут равны (−1)!, (−2)! и т. д., и эти значения не определены (см. факториал ).

Поэтому одним из возможных расширений является использование вместо этого 1/0!, 1/1!, 1/2!, 1/3!, ..., 1/ n ! и т. д., возможно, опуская позиции 1/0! и 1/1!, которые всегда равны нулю.

При использовании этого метода все рациональные числа имеют конечное расширение, длина которого в «цифрах» меньше или равна знаменателю представленного рационального числа. Это можно доказать, рассмотрев, что существует факториал для любого целого числа, и поэтому знаменатель делится на свой собственный факториал, даже если он не делится ни на какой меньший факториал.

Следовательно, по необходимости факторадическое разложение обратной величины простого числа имеет длину, равную длине простого числа (меньше единицы, если опущен знак 1/1!). Другие члены даны в виде последовательности A046021 на OEIS. Можно также доказать, что последняя «цифра» или член представления рационального числа с простым знаменателем равен разнице между числителем и простым знаменателем.

Подобно тому, как проверка делимости числа 4 в десятичной системе счисления требует рассмотрения только последних двух цифр, проверка делимости любого числа в факториальной системе счисления требует рассмотрения только конечного числа цифр. То есть, для каждого числа есть правило делимости .

Также существует бесконечный эквивалент для каждого рационального числа, например, в десятичной системе счисления 0,24999... = 0,25 = 1/4 и 0,999... = 1 и т. д., который можно создать, уменьшив последний член на 1, а затем заполнив оставшееся бесконечное число членов максимально возможным значением для основания этой позиции.

В следующем наборе примеров пробелы используются для разделения значений разрядов, в противном случае представленных в десятичной системе счисления. Рациональные числа слева также представлены в десятичной системе счисления:

• ${\displaystyle 1/2=0.0\ 1_{!}}$
• ${\displaystyle 1/3=0.0\ 0\ 2_{!}}$
• ${\displaystyle 2/3=0.0\ 1\ 1_{!}}$
• ${\displaystyle 1/4=0.0\ 0\ 1\ 2_{!}}$
• ${\displaystyle 3/4=0.0\ 1\ 1\ 2_{!}}$
• ${\displaystyle 1/5=0.0\ 0\ 1\ 0\ 4_{!}}$
• ${\displaystyle 1/6=0.0\ 0\ 1_{!}}$
• ${\displaystyle 5/6=0.0\ 1\ 2_{!}}$
• ${\displaystyle 1/7=0.0\ 0\ 0\ 3\ 2\ 0\ 6_{!}}$
• ${\displaystyle 1/8=0.0\ 0\ 0\ 3_{!}}$
• ${\displaystyle 1/9=0.0\ 0\ 0\ 2\ 3\ 2_{!}}$
• ${\displaystyle 1/10=0.0\ 0\ 0\ 2\ 2_{!}}$
• ${\displaystyle 1/11\ \ =0.0\ 0\ 0\ 2\ 0\ 5\ 3\ 1\ 4\ 0\ A_{!}}$
• ${\displaystyle 2/11\ \ =0.0\ 0\ 1\ 0\ 1\ 4\ 6\ 2\ 8\ 1\ 9_{!}}$
• ${\displaystyle 9/11\ \ =0.0\ 1\ 1\ 3\ 3\ 1\ 0\ 5\ 0\ 8\ 2_{!}}$
• ${\displaystyle 10/11=0.0\ 1\ 2\ 1\ 4\ 0\ 3\ 6\ 4\ 9\ 1_{!}}$
• ${\displaystyle 1/12\ \ =0.0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 5/12\ \ =0.0\ 0\ 2\ 2_{!}}$
• ${\displaystyle 7/12\ \ =0.0\ 1\ 0\ 2_{!}}$
• ${\displaystyle 11/12=0.0\ 1\ 2\ 2_{!}}$
• ${\displaystyle 1/15=0.0\ 0\ 0\ 1\ 3_{!}}$
• ${\displaystyle 1/16=0.0\ 0\ 0\ 1\ 2\ 3_{!}}$
• ${\displaystyle 1/18=0.0\ 0\ 0\ 1\ 1\ 4_{!}}$
• ${\displaystyle 1/20=0.0\ 0\ 0\ 1\ 1_{!}}$
• ${\displaystyle 1/24=0.0\ 0\ 0\ 1_{!}}$
• ${\displaystyle 1/30=0.0\ 0\ 0\ 0\ 4_{!}}$
• ${\displaystyle 1/36=0.0\ 0\ 0\ 0\ 3\ 2_{!}}$
• ${\displaystyle 1/60=0.0\ 0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 1/72=0.0\ 0\ 0\ 0\ 1\ 4_{!}}$
• ${\displaystyle 1/120=0.0\ 0\ 0\ 0\ 1_{!}}$
• ${\displaystyle 1/144=0.0\ 0\ 0\ 0\ 0\ 5_{!}}$
• ${\displaystyle 1/240=0.0\ 0\ 0\ 0\ 0\ 3_{!}}$
• ${\displaystyle 1/360=0.0\ 0\ 0\ 0\ 0\ 2_{!}}$
• ${\displaystyle 1/720=0.0\ 0\ 0\ 0\ 0\ 1_{!}}$

Существует также небольшое количество констант, которые имеют шаблонные представления с помощью этого метода:

• ${\displaystyle e=1\ 0.0\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1..._{!}}$
• ${\displaystyle e^{-1}=0.0\ 0\ 2\ 0\ 4\ 0\ 6\ 0\ 8\ 0\ A\ 0\ C\ 0\ E..._{!}}$
• ${\displaystyle \sin(1)=0.0\ 1\ 2\ 0\ 0\ 5\ 6\ 0\ 0\ 9\ A\ 0\ 0\ D\ E..._{!}}$
• ${\displaystyle \cos(1)=0.0\ 1\ 0\ 0\ 4\ 5\ 0\ 0\ 8\ 9\ 0\ 0\ C\ D\ 0..._{!}}$
• ${\displaystyle \sinh(1)=1.0\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0..._{!}}$
• ${\displaystyle \cosh(1)=1.0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\ 0\ 1..._{!}}$

Смотрите также

• Комбинаторная система счисления (также называемая комбинадикой)
• Проконечные целые числа , которые можно представить в виде бесконечных последовательностей цифр в факториальной системе счисления.
• Алгоритм Штейнхауза–Джонсона–Троттера , алгоритм, который генерирует коды Грея для факториальной системы счисления

Ссылки

1. Кнут, Д.Э. (1973), «Том 3: Сортировка и поиск», Искусство программирования , Эддисон-Уэсли, стр. 12, ISBN 0-201-89685-0
2. Кантор, Г. (1869), Zeitschrift für Mathematik und Physik , vol. 14.
3. Кнут, Д.Э. (1997), «Том 2: Получисленные алгоритмы», Искусство программирования (3-е изд.), Эддисон-Уэсли, стр. 192, ISBN 0-201-89684-2.
4. Лесан, Шарль-Анж (1888), «Sur la нумерация факториэль, применение дополнительных перестановок», Bulletin de la Société Mathématique de France (на французском языке), 16 : 176–183.
5. Термин «факторадический», по-видимому, введен в работе Маккаффри, Джеймса (2003), «Использование перестановок в .NET для улучшения безопасности систем», Microsoft Developer Network..

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), «Представление перестановки, которое знает, что означает «эйлерово»» (PDF) , Discrete Mathematics and Theoretical Computer Science , 4 : 101–108, архивировано из оригинала (PDF) 24.05.2011 , извлечено 27.03.2005.
• Арндт, Йорг (2010). Matters Computational: Ideas, Algorithms, Source Code. С. 232–238.

Внешние ссылки

• Калькулятор кода Лемера Обратите внимание, что цифры перестановки начинаются с 1, поэтому мысленно уменьшите все цифры перестановки на единицу, чтобы получить результаты, эквивалентные указанным на этой странице.
• Факториальная система счисления