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

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

В теории чисел и перечислительной комбинаторике , то заказал номера Bell или номера Фубините подсчитать количество слабых упорядочений на множество из п элементов (Упорядоченности элементов в последовательность , позволяющей связь , например, может возникнуть как результат в скачках ). ^[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} f (x, y) \, {\ text {d}} (x, y),}$

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

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

Формула [ править ]

П - й заказал номер Белл может быть задана суммирования формулы с участием числа Стирлинга второго рода , которые подсчитывают количество разбиений п - элементного множества в 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) ^ {kj} {\ 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),}$

где A _n - 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]

Несколько дополнительных модульных тождеств даны Good (1975) и Poonen (1988) . ^{[11] [20]}

Дополнительные приложения [ править ]

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

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

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

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

Ссылки [ править ]