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

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

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

Определение

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

Основание/основание	8	7	6	5	4	3	2	1
Значение места	7!	6!	5!	4!	3!	2!	1!	0!
Поместите значение в десятичном формате	5040	720	120	24	6	2	1	1
Самая высокая разрешенная цифра	7	6	5	4	3	2	1	0

Отсюда следует, что самая правая цифра всегда 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 ₁₀ можно преобразовать в факторное представление следующими последовательными делениями:

463 ÷ 1 = 463, остаток 0

463 ÷ 2 = 231, остаток 1

231 ÷ 3 = 77, остаток 0

77 ÷ 4 = 19, остаток 1

19 ÷ 5 = 3, остаток 4

3 ÷ 6 = 0, остаток 3

Процесс завершается, когда частное достигает нуля. Чтение остатков назад дает 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 перестановки четырех элементов с различными векторами, связанными с инверсией . Левая и правая инверсия имеет значение. $l$ и $r$ (последний часто называют кодом Лемера ) особенно подходят для интерпретации как факториальные числа. $l$ дает позицию перестановки в обратном колексикографическом порядке (порядок по умолчанию в этой таблице), а последней - позицию в лексикографическом порядке (оба отсчитываются от 0).

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


0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

	$\pi$		$v$			$l$	$r$		#
0	1234	4321	000 0	0 000	000 0	0 000	000 0	0 000	0
1	2134	4312	100 0	0 001	001 0	0 100	100 0	0 001	1
2	1324	4231	010 0	0 010	010 0	0 010	010 0	0 010	1
3	3124	4213	110 0	0 011	011 0	0 110	200 0	0 002	2
4	2314	4132	200 0	0 002	020 0	0 020	110 0	0 011	2
5	3214	4123	210 0	0 012	021 0	0 120	210 0	0 012	3
6	1243	3421	001 0	0 100	100 0	0 001	001 0	0 100	1
7	2143	3412	101 0	0 101	101 0	0 101	101 0	0 101	2
8	1423	3241	011 0	0 110	110 0	0 011	020 0	0 020	2
9	4123	3214	111 0	0 111	111 0	0 111	300 0	0 003	3
10	2413	3142	201 0	0 102	120 0	0 021	120 0	0 021	3
11	4213	3124	211 0	0 112	121 0	0 121	310 0	0 013	4
12	1342	2431	020 0	0 020	200 0	0 002	011 0	0 110	2
13	3142	2413	120 0	0 021	201 0	0 102	201 0	0 102	3
14	1432	2341	021 0	0 120	210 0	0 012	021 0	0 120	3
15	4132	2314	121 0	0 121	211 0	0 112	301 0	0 103	4
16	3412	2143	220 0	0 022	220 0	0 022	220 0	0 022	4
17	4312	2134	221 0	0 122	221 0	0 122	320 0	0 023	5
18	2341	1432	300 0	0 003	300 0	0 003	111 0	0 111	3
19	3241	1423	310 0	0 013	301 0	0 103	211 0	0 112	4
20	2431	1342	301 0	0 103	310 0	0 013	121 0	0 121	4
21	4231	1324	311 0	0 113	311 0	0 113	311 0	0 113	5
22	3421	1243	320 0	0 023	320 0	0 023	221 0	0 122	5
23	4321	1234	321 0	0 123	321 0	0 123	321 0	0 123	6

Другой пример: наибольшее число, которое можно представить шестизначным числом, будет 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.

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

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

Это можно легко доказать с помощью математической индукции или просто заметив, что $\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 _! , но не 100000000000 _! = 1: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 ₁₀	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)

В каждом случае вычисление перестановки происходит с использованием самой левой факторадной цифры (здесь 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)
factoradic: 4              :   0            :   4          :   1        :   0      :   0    :   0_!
            ├─┬─┬─┬─┐          │                ├─┬─┬─┬─┐      ├─┐          │          │        │
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)

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

           concatenated
 decimal   factoradics        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))

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

Мантачи, Роберто; Ракотондраджао, Фанья (2001), «Представление перестановок, которое знает, что означает слово «эйлерово»» (PDF) , Discrete Mathematics and Theoretical Computer Science , 4 : 101–108, заархивировано из оригинала (PDF) 24 мая 2011 г. , получено 27 марта 2005 г.
Арндт, Йорг (2010). Вопросы вычислений: идеи, алгоритмы, исходный код . стр. 232–238.

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

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

[1] Кнут, Д.Э. (1973), «Том 3: Сортировка и поиск», Искусство компьютерного программирования , Аддисон-Уэсли, стр. 12, ISBN 0-201-89685-0

[2] Кантор, Г. (1869), Журнал математики и физики , вып. 14 .

[3] Кнут, DE (1997), «Том 2: Получисловые алгоритмы», Искусство компьютерного программирования (3-е изд.), Аддисон-Уэсли, стр. 192, ИСБН 0-201-89684-2 .

[4] Лесан, Шарль-Анж (1888), «О факториальной нумерации, применении к перестановкам» , Bulletin de la Société Mathématique de France (на французском языке), 16 : 176–183 .

[5] Термин «факторадический», по-видимому, введен в Маккаффри, Джеймс (2003), Использование перестановок в .NET для повышения безопасности систем , Microsoft Developer Network .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]