Заказанный номер звонка - Ordered Bell number

13 возможных строгих слабых порядков на множестве из трех элементов {а, б, c}

В теория чисел и перечислительная комбинаторика, то заказанные номера Bell или же Числа Фубини подсчитать количество слабые порядки на набор из п элементы (порядок элементов в последовательности, позволяющей связи, которые могут возникнуть в результате скачки ).^[1] Начиная с п = 0, эти числа

1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (последовательность A000670 в OEIS ).

Упорядоченные числа Белла могут быть вычислены с помощью формулы суммирования, включающей биномиальные коэффициенты, или используя отношение повторения. Наряду со слабым порядком они насчитывают несколько других типов комбинаторных объектов, у которых есть биективное соответствие к слабым порядкам, таким как упорядоченный мультипликативные разделы из свободный от квадратов номер^[2] или грани всех размеров пермутоэдр^[3] (например, сумма граней всех размеров в усеченный октаэдр равно 1 + 14 + 36 + 24 = 75^[4]).

История

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

Упорядоченные номера Bell появляются в работе Кэли (1859), кто использовал их для подсчета определенных платаны с п + 1 полностью заказанный лист. В деревьях, рассмотренных Кэли, каждый путь от корня к листу имеет одинаковую длину, а количество узлов на расстоянии я от корня должно быть строго меньше количества узлов на расстоянии я +1, пока не дойдем до листьев.^[5] В таком дереве есть п пары соседних листьев, которые могут быть слабо упорядочены по высоте их наименьший общий предок; этот слабый порядок определяет дерево. Мор и Френкель (1984) называют деревья этого типа «деревьями Кэли», и они называют последовательности, которые могут быть использованы для обозначения их пропусков (последовательности п положительные целые числа, которые включают в себя по крайней мере одну копию каждого положительного целого числа от единицы до максимального значения в последовательности) «Перестановки Кэли».^[6]

Пиппенгер (2010) прослеживает проблему подсчета слабых порядков, которая имеет ту же последовательность, что и ее решение, к работе Уитворт (1886).^[7][8]

Эти числа Луи Конте назвал числами Фубини, потому что они подсчитывают количество различных способов изменить порядок сумм или интегралов в Теорема Фубини, который, в свою очередь, назван в честь Гвидо Фубини.^[9] Например, для двумерного интеграла теорема Фубини утверждает, что

${displaystyle int _{A}left(int _{B}f(x,y),{ ext{d}}yight),{ ext{d}}x=int _{B}left(int _{A}f(x,y),{ ext{d}}xight),{ ext{d}}y=int _{A imes B}f(x,y),{ ext{d}}(x,y),}$

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

В Номера звонков, названный в честь Эрик Темпл Белл, подсчитайте количество перегородки набора, а слабые порядки, которые подсчитываются с помощью упорядоченных чисел Белла, можно интерпретировать как разбиение вместе с общий заказ по комплектам в перегородке.^[10]

Формула

В п-ый заказанный номер звонка может быть задан суммирование формула, включающая Числа Стирлинга второго рода, которые подсчитывают количество разделов п-элемент установлен в k непустые подмножества,^[11][12]раскладывается в двойное суммирование с участием биномиальные коэффициенты (используя формулу, выражающую числа Стирлинга как сумму биномиальных коэффициентов), или задаваемый бесконечная серия:^[7][10]

${displaystyle a(n)=sum _{k=0}^{n}k!left{{egin{matrix}nkend{matrix}}ight}=sum _{k=0}^{n}sum _{j=0}^{k}(-1)^{k-j}{inom {k}{j}}j^{n}={frac {1}{2}}sum _{m=0}^{infty }{frac {m^{n}}{2^{m}}}.}$

Альтернативная формула суммирования выражает упорядоченные числа Белла через Числа Эйлера, которые подсчитывают количество перестановок п предметы с k + 1 пробег увеличивающихся предметов:^[13]

${displaystyle a(n)=sum _{k=0}^{n-1}2^{k}leftlangle {egin{matrix}nkend{matrix}}ightangle =A_{n}(2),}$

куда А_п это п-й полином Эйлера.

В экспоненциальная производящая функция упорядоченных номеров Белла составляет^{[7][10][12][14]}

${displaystyle sum _{n=0}^{infty }a(n){frac {x^{n}}{n!}}={frac {1}{2-e^{x}}}.}$

Это может быть эквивалентно выражено как тот факт, что упорядоченные числа Белла - это числа в первом столбце таблицы. бесконечная матрица (2я − п)⁻¹, куда я это единичная матрица и п представляет собой бесконечную матричную форму Треугольник Паскаля.^[15]На основе контурная интеграция этой производящей функции, упорядоченные числа Белла могут быть выражены бесконечной суммой^[2][16]

${displaystyle a(n)={frac {n!}{2}}sum _{k=-infty }^{infty }(log 2+2pi ik)^{-(n+1)},qquad ngeq 1,}$

и аппроксимируется как^{[2][12][17][18][16]}

${displaystyle a(n)approx {frac {n!}{2(log 2)^{n+1}}}.}$

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

${displaystyle lim _{n o infty }{frac {n,a(n-1)}{a(n)}}=log 2.}$

Повторяемость и модульная периодичность

Как и в приведенных выше формулах, упорядоченные числа Белла могут быть вычислены с помощью отношение повторения^[7][17]

${displaystyle a(n)=sum _{i=1}^{n}{inom {n}{i}}a(n-i).}$

Интуитивный смысл этой формулы состоит в том, что слабое упорядочение на п элементы могут быть разбиты на выбор некоторого непустого набора я элементы, которые попадают в первый класс эквивалентности порядка, вместе с меньшим слабым порядком на оставшихся п − я Предметы. В качестве базового случая для повторения а(0) = 1 (есть одно слабое упорядочение по нулевым элементам). Основываясь на этой повторяемости, можно показать, что эти числа подчиняются определенным периодическим образцам в модульная арифметика: для достаточно большихп,

${displaystyle a(n+4)equiv a(n){pmod {10}},}$^[17]

${displaystyle a(n+20)equiv a(n){pmod {100}},}$

${displaystyle a(n+100)equiv a(n){pmod {1000}},}$ и

${displaystyle a(n+500)equiv a(n){pmod {10000}}.}$^[19]

Несколько дополнительных модульных идентичностей даются Хорошо (1975) и Пунен (1988).^[11][20]

Дополнительные приложения

Как уже упоминалось, упорядоченные числа Белла учитывают слабые порядки, пермутоэдр грани, деревья Кэли, перестановки Кэли, упорядоченные мультипликативные разбиения бесквадратных чисел и эквивалентные формулы в теореме Фубини. В свою очередь, у слабых порядков есть много других приложений. Например, в скачки, фото отделки устранили большинство, но не все связи, называемые в этом контексте мертвая жара, а результат забега, который может содержать ничьи (включая всех лошадей, а не только первых трех финишировавших), может быть описан с использованием слабого порядка. По этой причине упорядоченные числа Bell подсчитывают возможное количество исходов скачки,^[1] или возможные результаты мульти-кандидата выборы.^[21] Напротив, когда элементы упорядочены или ранжированы таким образом, который не допускает совпадений (например, это происходит с упорядочением карт в колоде карт или сортировкой приказов между бейсбол игроков), количество заказов на п предметы - это факториальное число п!,^[22] что значительно меньше соответствующего упорядоченного числа Белла.^[23]

Кемени (1956) использует упорядоченные числа Белла для описания «сложности» п-арное отношение, под которым он подразумевает ряд других отношений, которые можно сформировать из него, переставляя и повторяя его аргументы (уменьшая арность при каждом повторении).^[24] В этом приложении для каждого производного отношения аргументы исходного отношения слабо упорядочены по позициям соответствующих аргументов производного отношения.

Веллеман и Колл (1995) учитывать кодовые замки с цифровой клавиатурой, в которой несколько клавиш могут быть нажаты одновременно, а комбинация состоит из последовательности нажатий клавиш, которая включает каждую клавишу ровно один раз. Как они показывают, количество различных комбинаций в такой системе определяется упорядоченными числами Белла.^[13]

Эллисон и Кляйн (2001) указать на применение этих чисел к теория оптимальности в лингвистика. В этой теории грамматики для естественные языки строятся путем ранжирования определенных ограничений, и (в явлении, называемом факторной типологией) количество различных грамматик, которые могут быть сформированы таким образом, ограничено числом перестановок ограничений. В статье, рассмотренной Эллисоном и Кляйном, предложено расширение этой лингвистической модели, в которой разрешены связи между ограничениями, так что ранжирование ограничений становится слабым порядком, а не полным порядком. Как они отмечают, гораздо большая величина упорядоченных чисел Белла по сравнению с соответствующими факториалы, позволяет этой теории генерировать гораздо более богатый набор грамматик.^[23]

Рекомендации

1. де Конинк, Дж. М. (2009), Эти увлекательные числа, Американское математическое общество, стр. 4, ISBN  9780821886311. Из-за этого приложения де Конинк называет эти числа «номерами лошадей», но это имя не имеет широкого распространения.
2. Скляр, Абэ (1952), "О факторизации бесквадратных целых чисел", Труды Американского математического общества, 3: 701–705, Дои:10.1090 / S0002-9939-1952-0050620-1, JSTOR  2032169, МИСТЕР  0050620.
3. Циглер, Гюнтер М. (1995), Лекции по многогранникам, Тексты для выпускников по математике, 152, Springer, стр. 18.
4. 1, 14, 36, 24 - четвертый ряд этого треугольника (последовательность A019538 в OEIS )
5. Кэли, А. (1859 г.), «Об аналитических формах, называемых деревьями, вторая часть», Философский журнал, Серия IV, 18 (121): 374–378, Дои:10.1017 / CBO9780511703706.026. В Собрание сочинений Артура Кэли, п. 113.
6. Mor, M .; Френкель, А.С. (1984), «Перестановки Кэли», Дискретная математика, 48 (1): 101–112, Дои:10.1016 / 0012-365X (84) 90136-5, МИСТЕР  0732206.
7. Пиппенгер, Николас (2010), «Гиперкуб резисторов, асимптотические разложения и предпочтительные схемы», Математический журнал, 83 (5): 331–346, arXiv:0904.1757, Дои:10.4169 / 002557010X529752, МИСТЕР  2762645.
8. Витворт, В.А. (1886), Выбор и шанс, Дейтон: Белл и Ко, Предложение XXII, стр. 93. Как цитирует Пиппенгер (2010).
9. Контет, Луи (1974), Продвинутая комбинаторика: искусство конечных и бесконечных расширений (PDF) (переработанное и дополненное ред.), D. Reidel Publishing Co., p. 228, заархивировано оригинал (PDF) на 2014-07-04, получено 2013-03-12.
10. Knopfmacher, A .; Мэйс, М. Э. (2005), "Обзор счетных функций факторизации", Международный журнал теории чисел, 1 (4): 563–581, Дои:10.1142 / S1793042105000315, МИСТЕР  2196796.
11. Хорошо, И. Дж. (1975), "Количество заказов п кандидаты, когда связи разрешены " (PDF), Ежеквартальный отчет Фибоначчи, 13: 11–18, МИСТЕР  0376367.
12. Спругноли, Ренцо (1994), "Массивы Риордана и комбинаторные суммы", Дискретная математика, 132 (1–3): 267–290, Дои:10.1016 / 0012-365X (92) 00570-H, HDL:10338.dmlcz / 143149, МИСТЕР  1297386.
13. Веллеман, Дэниел Дж .; Звоните, Грегори С. (1995), "Перестановки и кодовые замки", Математический журнал, 68 (4): 243–253, Дои:10.2307/2690567, МИСТЕР  1363707.
14. Гету, Сейюм; Шапиро, Луи В.; Воан, Вэнь Цзинь; Вудсон, Леон С. (1992), "Как угадать производящую функцию", Журнал SIAM по дискретной математике, 5 (4): 497–499, Дои:10.1137/0405040, МИСТЕР  1186818.
15. Льюис, Барри (2010), «Возвращаясь к матрице Паскаля», Американский математический ежемесячный журнал, 117 (1): 50–66, Дои:10.4169 / 000298910X474989, МИСТЕР  2599467.
16. Бейли, Ральф В. (1998), "Число слабых порядков конечного множества", Социальный выбор и благосостояние, 15 (4): 559–562, Дои:10.1007 / s003550050123, МИСТЕР  1647055.
17. Гросс, О. А. (1962), «Льготные условия», Американский математический ежемесячник, 69: 4–8, Дои:10.2307/2312725, МИСТЕР  0130837.
18. Бартелеми, Ж.-П. (1980), "Асимптотический эквивалент количества полных предпорядков на конечном множестве", Дискретная математика, 29 (3): 311–313, Дои:10.1016 / 0012-365X (80) 90159-4, МИСТЕР  0560774.
19. Кауфман, Долорес Х. (1963), «Заметка о льготных условиях», Американский математический ежемесячник, 70: 62, Дои:10.2307/2312790, МИСТЕР  0144827.
20. Пунен, Бьорн (1988), "Периодичность комбинаторной последовательности", Ежеквартальный отчет Фибоначчи, 26 (1): 70–76, МИСТЕР  0931425.
21. Петкович, Миодраг (2009), Известные загадки великих математиков, Американское математическое общество, стр. 194, г. ISBN  9780821886304.
22. Харрис, Джон; Херст, Джеффри Л .; Моссингхофф, Майкл Дж. (2008), Комбинаторика и теория графов, Тексты для бакалавриата по математике (2-е изд.), Springer, p. 132, ISBN  9780387797106.
23. Эллисон, Т. Марк; Кляйн, Юэн (2001), "Обзор: лучшее из всех возможных слов" (обзор Теория оптимальности: обзор, Archangeli, Diana & Langendoen, D. Terence, eds., Blackwell, 1997) ", Журнал лингвистики, 37 (1): 127–143, JSTOR  4176645.
24. Кемени, Джон Г. (1956), «Две меры сложности», Журнал Философии, 52 (24): 722–733, JSTOR  2022697.