Заказанный номер звонка

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

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

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

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

История

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

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

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

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

${\ displaystyle \ int _ {A} \ left (\ int _ {B} f (x, y) \, {\ text {d}} y \ right) \, {\ text {d}} x = \ int _ {B} \ left (\ int _ {A} f (x, y) \, {\ text {d}} x \ right) \, {\ text {d}} y = \ int _ {A \ times B} е (х, у) \, {\ текст {d}} (х, у),}$

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

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

Формула

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

${\displaystyle a(n)=\sum _{k=0}^{n}k!\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\sum _{k=0}^{n}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}={\frac {1}{2}}\sum _{m=0}^{\infty }{\frac {m^{n}}{2^{m}}}.}$

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

${\displaystyle a(n)=\sum _{k=0}^{n-1}2^{k}\left\langle {\begin{matrix}n\\k\end{matrix}}\right\rangle =A_{n}(2),}$

где An — _n -й полином Эйлера.

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

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

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

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

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

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

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

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

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

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

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

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

${\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]}

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

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

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

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

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

использованная литература