Комбинаторная система счисления

В математике , и в частности в комбинаторике , комбинаторная система счисления степени k (для некоторого положительного целого числа k ), также называемая комбинадикой , или представлением Маколея целого числа , представляет собой соответствие между натуральными числами (считается, что они включают 0) N и k - комбинации . Комбинации представляются в виде строго убывающих последовательностей c _k > ... > c ₂ > c ₁ ≥ 0, где каждый c _i соответствует индексу выбранного элемента в данной k -комбинации. Различные числа соответствуют различным k -комбинациям и создают их в лексикографическом порядке . Числа меньше, чем ${\tbinom {n}{k}}$ соответствуют всем k -комбинациям n {0, 1, ..., − 1 }. Соответствие не зависит от размера n множества, из которого взяты k -комбинации, поэтому его можно интерпретировать как отображение N в k -комбинации, взятые из N ; с этой точки зрения соответствие является биекцией .

Число N, ( ck _{соответствующее} , ..., c ₂ , c ₁ ), определяется выражением

N={\binom {c_{k}}{k}}+\cdots +{\binom {c_{2}}{2}}+{\binom {c_{1}}{1}}

.

Тот факт, что любому неотрицательному числу N соответствует уникальная последовательность , впервые заметил Д. Х. Лемер . ^[1] Действительно, жадный алгоритм находит k -комбинацию, соответствующую N : возьмем c _k максимальным с ${\tbinom {c_{k}}{k}}\leq N$ , то возьмем c _{k −1} максимальное с ${\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}$ и так далее. Нахождение числа N по приведенной выше формуле из k -комбинации ( c _k , ..., c ₂ , c ₁ ) также известно как «ранжирование», а противоположная операция (задаваемая жадным алгоритмом) как « снятие с рейтинга"; под этими названиями операции известны в большинстве систем компьютерной алгебры и в вычислительной математике . ^[2]^[3]

Первоначально используемый термин «комбинаторное представление целых чисел» был сокращен Кнутом до «комбинаторной системы счисления» . ^[4]который также дает гораздо более старую ссылку; ^[5]термин «комбинадический» введен Джеймсом Маккаффри. ^[6] (без ссылки на предыдущую терминологию или работу).

В отличие от факториальной системы счисления , комбинаторная система счисления степени k не является смешанной системой счисления : часть ${\tbinom {c_{i}}{i}}$ числа N, представленного «цифрой» c _i, не получается из него простым умножением на разрядное значение.

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

Заказ комбинаций

k с множества S — это подмножество S k ( различными -комбинация ) элементами. Основная цель комбинаторной системы счисления — обеспечить представление каждого числа одним числом всех ${\tbinom {n}{k}}$ возможных k -комбинаций множества S из n элементов. Выбирая для любого n , {0, 1, ..., n − 1 } в качестве такого набора, можно добиться того, чтобы представление данной k -комбинации C не зависело от значения n (хотя n должно иметь конечно быть достаточно большим); другими словами, рассмотрение C как подмножества большего набора путем увеличения n не изменит число, представляющее C . Таким образом, для комбинаторной системы счисления C просто рассматривается как k -комбинация множества N всех натуральных чисел, без явного упоминания n .

Чтобы гарантировать, что числа, представляющие k -комбинации {0, 1, ..., n − 1 }, меньше чисел, представляющих k -комбинации, не содержащиеся в {0, 1, ..., n − 1 } , k -комбинации должны быть упорядочены таким образом, чтобы сначала сравнивались их самые большие элементы. Наиболее естественным упорядочением, обладающим этим свойством, является упорядочение убывающей лексикографическое последовательности их элементов. Таким образом, сравнивая 5-комбинации C = {0,3,4,6,9} и C ′ = {0,1,3,7,9}, получаем, что C предшествует C ′, поскольку они имеют одинаковый наибольший размер. часть 9, но следующая по величине часть 6 C меньше, чем следующая по величине часть 7 C '; лексикографически сравниваются последовательности (9,6,4,3,0) и (9,7,3,1,0).

Другой способ описать этот порядок — это комбинации представлений, описывающие k поднятых битов в двоичном представлении числа, так что C = { c ₁ , ..., c _k } описывает число

2^{c_{1}}+2^{c_{2}}+\cdots +2^{c_{k}}

(это связывает разные числа со всеми конечными наборами натуральных чисел); тогда сравнение k -комбинаций можно выполнить путем сравнения соответствующих двоичных чисел. В примере C и C ′ соответствуют числам 1001011001 ₂ = 601 ₁₀ и 1010001011 ₂ = 651 ₁₀ , что снова показывает, что C предшествует C ′. Однако это число не является тем числом, которым нужно представлять k -комбинацию, поскольку многие двоичные числа имеют несколько повышенных битов, отличных от k ; требуется найти относительное положение C в упорядоченном списке (только) k -комбинаций .

Место комбинации в заказе

Число, сопоставленное в комбинаторной системе счисления степени k k - комбинации C, есть число k -комбинаций, строго меньшее C в данном порядке. Это число можно вычислить из C = { c _k , ..., c ₂ , c ₁ } с c _k > ... > c ₂ > c ₁ следующим образом.

определения порядка следует, что для каждой k -комбинации S, строго меньшей, чем C , существует единственный индекс i такой, что c _i отсутствует в S , а ck _Из , ..., c _{i +1} присутствуют в S и никакое другое значение, большее, чем c _i . Таким образом, можно сгруппировать эти k -комбинации S в соответствии с возможными значениями 1, 2, ..., k для i и считать каждую группу отдельно. Для данного значения i необходимо включить c _k , ..., c _{i +1} в S , а остальные i элементов S должны быть выбраны из c _i неотрицательных целых чисел, строго ci _{меньших} ; более того, любой такой выбор приведет к тому, что k -комбинаций S строго меньше C . Число возможных вариантов равно ${\tbinom {c_{i}}{i}}$ , что, следовательно, представляет собой количество комбинаций в группе i ; общее число k -комбинаций строго меньше C тогда равно

{\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},

и это индекс (начиная с 0) C в упорядоченном списке k -комбинаций.

существует Очевидно, что для каждого N ∈ N ровно одна k -комбинация с индексом N в списке (предполагая, что k ≥ 1, поскольку в этом случае список бесконечен), поэтому приведенный выше аргумент доказывает, что каждое N можно записать ровно одним способом как сумма k биномиальных коэффициентов заданного вида.

Нахождение k -комбинации по заданному числу

Данная формула позволяет сразу найти место в лексикографическом порядке заданного k -сочетания. Обратный процесс нахождения k -комбинации в заданном месте N требует несколько большей работы, но, тем не менее, является простым. По определению лексикографического упорядочения две k -комбинации, различающиеся наибольшим элементом c _k, будут упорядочены по принципу сравнения этих крупнейших элементов, из чего следует, что все комбинации с фиксированным значением наибольшего элемента являются смежными в список. Более того, наименьшая комбинация с c _k в качестве самого большого элемента равна ${\tbinom {c_{k}}{k}}$ , и оно имеет c _i = i − 1 для всех i < k (для этой комбинации все члены выражения, кроме ${\tbinom {c_{k}}{k}}$ равны нулю). Следовательно, c _k — наибольшее число такое, что ${\tbinom {c_{k}}{k}}\leq N$ . Если k > 1, то остальные элементы k -комбинации образуют k − 1 -комбинацию, соответствующую числу $N-{\tbinom {c_{k}}{k}}$ в комбинаторной системе счисления степени k − 1 , и поэтому его можно найти, продолжая тем же способом для $N-{\tbinom {c_{k}}{k}}$ и k − 1 вместо N и k .

Пример

Предположим, кто-то хочет определить 5-комбинацию в позиции 72. Последовательные значения ${\tbinom {n}{5}}$ для n = 4, 5, 6, ... равны 0, 1, 6, 21, 56, 126, 252, ..., из которых наибольшее число, не превышающее 72, равно 56, для n = 8. Следовательно, c ₅ = 8, а оставшиеся элементы образуют 4-комбинацию в позиции 72 − 56 = 16 . Последовательные значения ${\tbinom {n}{4}}$ для n = 3, 4, 5, ... равны 0, 1, 5, 15, 35, ..., из которых наибольшее число, не превышающее 16, равно 15, для n = 6, поэтому c ₄ = 6. Продолжаем аналогично поиску 3-комбинации в позиции 16 - 15 = 1 находится c ₃ = 3, что расходует последнюю единицу; это устанавливает $72={\tbinom {8}{5}}+{\tbinom {6}{4}}+{\tbinom {3}{3}}$ , а остальные значения c _i будут максимальными с ${\tbinom {c_{i}}{i}}=0$ , а именно c _я знак равно я - 1 . Таким образом мы нашли 5-комбинацию {8, 6, 3, 1, 0 }.

Пример национальной лотереи

Для каждого из ${\binom {49}{6}}$ лотерейных комбинаций c ₁ < c ₂ < c ₃ < c ₄ < c ₅ < c ₆ , существует номер списка N между 0 и ${\binom {49}{6}}-1$ который можно найти, добавив

{\binom {49-c_{1}}{6}}+{\binom {49-c_{2}}{5}}+{\binom {49-c_{3}}{4}}+{\binom {49-c_{4}}{3}}+{\binom {49-c_{5}}{2}}+{\binom {49-c_{6}}{1}}.

См. также

Факториальная система счисления (также называемая факторадиком)
Первобытная система счисления
Асимметричные системы счисления - также, например, комбинация натуральных чисел, широко используемая при сжатии данных.

Ссылки

^ Прикладная комбинаторная математика , Под ред. Э. Ф. Беккенбах (1964), стр. 27–30.
^ Генерация элементарных комбинаторных объектов , Люсия Моура, Университет Оттавы, осень 2009 г.
^ «Комбинации — Справочное руководство Sage 9.4: Комбинаторика» .
^ Кнут, DE (2005), «Создание всех комбинаций и разделов», Искусство компьютерного программирования , том. 4, выпуск 3, Аддисон-Уэсли, стр. 5–6, ISBN. 0-201-85394-9 .
^ Паскаль, Эрнесто (1887), Журнал математики , том. 25, с. 45−49
^ Маккаффри, Джеймс (2004), Генерация m-го лексикографического элемента математической комбинации , Microsoft Developer Network

Дальнейшее чтение

Хунеке, Крейг; Суонсон, Ирена (2006), «Приложение 5» , Интегральное замыкание идеалов, колец и модулей , Серия лекций Лондонского математического общества, том. 336, Кембридж, Великобритания: Издательство Кембриджского университета , ISBN 978-0-521-68860-4 , МР 2266432
Кавилья, Джулио (2005), «Теорема Икина и Сатайе и теорема ограничения гиперплоскости Грина» , Коммутативная алгебра: геометрические, гомологические, комбинаторные и вычислительные аспекты , CRC Press , ISBN 978-1-420-02832-4
Грин, Марк (1989), «Ограничения линейных рядов на гиперплоскости и некоторые результаты Маколея и Готцмана», Алгебраические кривые и проективная геометрия , Конспект лекций по математике, том. 1389, Springer , стр. 76–86, doi : 10.1007/BFb0085925 , ISBN. 978-3-540-48188-1

[1] Прикладная комбинаторная математика , Под ред. Э. Ф. Беккенбах (1964), стр. 27–30.

[2] Генерация элементарных комбинаторных объектов , Люсия Моура, Университет Оттавы, осень 2009 г.

[3] «Комбинации — Справочное руководство Sage 9.4: Комбинаторика» .

[4] Кнут, DE (2005), «Создание всех комбинаций и разделов», Искусство компьютерного программирования , том. 4, выпуск 3, Аддисон-Уэсли, стр. 5–6, ISBN. 0-201-85394-9 .

[5] Паскаль, Эрнесто (1887), Журнал математики , том. 25, с. 45−49

[6] Маккаффри, Джеймс (2004), Генерация m-го лексикографического элемента математической комбинации , Microsoft Developer Network

[1]

[2]

[3]

[4]

[5]

[6]