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

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

В теории чисел и перечислительной комбинаторике упорядоченные числа Белла или числа Фубини учитывают слабые порядки на множестве чисел. $n$ элементы. Слабый порядок упорядочивает свои элементы в последовательность, допускающую связи , например, которые могут возникнуть в результате скачек .

Упорядоченные числа Белла изучались в 19 веке Артуром Кэли и Уильямом Алленом Уитвортом . Они названы в честь Эрика Темпла Белла , который написал о числах Белла , которые подсчитывают разбиения множества ; Заказанные номера Bell учитывают разделы, которые были оборудованы в полном порядке . Их альтернативное название, числа Фубини, происходит от связи с Гвидо Фубини и теоремой Фубини об эквивалентных формах кратных интегралов. Поскольку слабые порядки имеют много имен, упорядоченные числа Белла также могут называться этими именами, например, числами предпочтительных порядков. или числа асимметричных обобщенных слабых порядков.

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

Определения и примеры

Слабый порядок упорядочивает свои элементы в последовательность, допускающую связи . Эта возможность описывает различные сценарии реального мира, включая определенные спортивные соревнования, такие как скачки . Слабый порядок можно аксиоматически формализовать частично упорядоченным множеством , для которого несравнимость является отношением эквивалентности . Классы эквивалентности этого отношения разбивают элементы упорядочения на подмножества взаимно связанных элементов, и эти классы эквивалентности затем могут быть линейно упорядочены с помощью слабого упорядочения. Таким образом, слабый порядок можно описать как упорядоченное разбиение , разбиение его элементов и общий порядок на множествах разбиения. Например, упорядоченный раздел { a , b },{ c }, { d , e , f } описывает упорядоченный раздел из шести элементов, в котором a и b связаны, и оба меньше, чем остальные четыре элемента, а c меньше чем d , e и f , которые все связаны друг с другом.

The $n$-е упорядоченное число Белла, обозначенное здесь $a(n)$, дает количество различных слабых порядков на $n$ элементы. Например, существует три слабых порядка для двух элементов a и b : их можно упорядочить с a перед b , с b перед a или с обоими связанными. На рисунке показаны 13 слабых упорядочений по трем элементам.

Начиная с $n=0$, упорядоченные числа Белла $a(n)$ являются

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

Когда упорядочиваемые элементы не помечены (имеет значение только количество элементов в каждом связанном множестве, а не их идентичность), остается композиция или упорядоченное целочисленное разделение, представление $n$ как упорядоченная сумма натуральных чисел. Например, рассмотренное выше упорядоченное разбиение { a , b },{ c }, { d , e , f } соответствует таким образом композиции 2 + 1 + 3. Число композиций из $n$ это точно $2^{n-1}$. Это связано с тем, что композиция определяется набором частичных сумм , которые могут представлять собой любое подмножество целых чисел от 1 до $n-1$.

История

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

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

Пиппенджер (2010) возводит проблему подсчета слабых порядков, имеющую ту же последовательность, что и ее решение, к работе Уитворта (1886) . Эти числа Луи Конте назвал числами Фубини, поскольку они учитывают различные способы изменения порядка сумм или интегралов в теореме Фубини , которая, в свою очередь, названа в честь Гвидо Фубини . Числа Белла , названные в честь Эрика Темпла Белла , подсчитывают разбиения множества , а слабые порядки, которые подсчитываются упорядоченными числами Белла, можно интерпретировать как разбиение вместе с общим порядком множеств в разбиении.

Эквивалентность между подсчетом деревьев Кэли и подсчетом слабых упорядочений была обнаружена в 1970 году Дональдом Кнутом , используя раннюю форму Онлайн-энциклопедии целочисленных последовательностей (OEIS). Это стало одним из первых успешных применений OEIS для обнаружения эквивалентности между различными задачами подсчета.

Формулы

Суммирование

Поскольку слабый порядок можно описать как полный порядок на подмножествах раздела, слабый порядок можно подсчитать, подсчитав общее количество упорядочений и разделов и соответствующим образом объединив результаты. Числа Стирлинга второго рода , обозначаемые $\{{\scriptstyle {n \atop k}}\}$, посчитайте разделы $n$-элемент установлен в $k$ непустые подмножества. Слабое упорядочение такого разбиения можно получить, выбрав одно из $k!$ тотальный порядок его подмножеств. Следовательно, упорядоченные числа Белла можно подсчитать путем суммирования по возможному числу подмножеств в разбиении (параметр $k$) и для каждого значения $k$, умножая количество разделов $\{{\scriptstyle {n \atop k}}\}$ по количеству заказов $k!$. То есть в виде формулы суммирования :

$$a(n)=\sum _{k=0}^{n}k!\left\{{\begin{matrix}n\\k\end{matrix}}\right\}$$

Из общих результатов о суммировании с участием чисел Стирлинга следует, что упорядоченные числа Белла логарифмически выпуклы , а это означает, что они подчиняются неравенству $a(n-1)a(n+1)\geq a(n)^{2}$ для всех $n>0$.

Трехмерный усеченный октаэдр , вершины которого помечены четырехмерными координатами как пермутоэдр.

Альтернативная интерпретация членов этой суммы состоит в том, что они подсчитывают особенности каждого измерения в пермутоэдре размерности $n$, с $k$й член, подсчитывающий особенности измерения $n-k$. Пермутоэдр — это выпуклый многогранник , выпуклая оболочка точек, координатные векторы которых представляют собой перестановки чисел от 1 до $n$. Эти векторы определены в пространстве размерности $n+1$, но все они и их выпуклая оболочка лежат в $n$-мерное аффинное подпространство . Например, трехмерный пермутоэдр — это усеченный октаэдр , выпуклая оболочка точек, координаты которых являются перестановками (1,2,3,4), в трехмерном подпространстве точек, сумма координат которых равна 10. Этот многогранник имеет один том ( $k=0$), 14 двумерных граней ( $k=1$), 36 ребер ( $k=2$) и 24 вершины ( $k=3$). Общее количество этих граней составляет 1 + 14 + 36 + 24 = 75, упорядоченное число Белла, соответствующее приведенной выше формуле суммирования для $n=3$.

Разлагая каждое число Стирлинга в этой формуле в сумму биномиальных коэффициентов , формулу для упорядоченных чисел Белла можно разложить до двойного суммирования. Упорядоченные числа Белла также могут быть заданы бесконечным рядом :

$$a(n)=\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}}}.$$

Другая формула суммирования выражает упорядоченные числа Белла через числа Эйлера. $\langle {\scriptstyle {n \atop k}}\rangle$, которые подсчитывают перестановки $n$ предметы, в которых $k$ пары последовательных элементов располагаются в порядке возрастания:

$$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$полином Эйлера . Один из способов объяснить эту формулу суммирования включает в себя отображение слабых порядков чисел от 1 до $n$ к перестановкам , полученным путем сортировки каждого связанного набора в числовом порядке. При этом отображении каждая перестановка с $k$ последовательные возрастающие пары происходят от $2^{k}$ слабые упорядочения, отличающиеся друг от друга подмножеством последовательных возрастающих пар, связанных слабым упорядочением.

Производящая функция и аппроксимация

Как и в случае со многими другими целочисленными последовательностями, переосмысление последовательности как коэффициентов степенного ряда и работа с функцией, получающейся в результате суммирования этого ряда, могут предоставить полезную информацию о последовательности. Быстрый рост упорядоченных чисел Белла приводит их обычной производящей функции к расхождению ; вместо этого экспоненциальная производящая функция используется . Для упорядоченных чисел Белла это:

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

Здесь левая часть — это просто определение экспоненциальной производящей функции, а правая часть — это функция, полученная в результате этого суммирования.Вид этой функции соответствует тому, что упорядоченные числа Белла — это числа в первом столбце бесконечной матрицы $(2I-P)^{-1}$. Здесь $I$ - единичная матрица и $P$ — бесконечная матричная форма треугольника Паскаля . Каждый ряд $P$ начинается с чисел в одной строке треугольника Паскаля, а затем продолжается бесконечной повторяющейся последовательностью нулей.

На основе контурного интегрирования этой производящей функции упорядоченные числа Белла могут быть выражены бесконечной суммой

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

Здесь, $\log$ обозначает натуральный логарифм . Это приводит к аппроксимации упорядоченных чисел Белла, полученной с использованием только члена для $k=0$ в этой сумме и отбрасывая остальные члены:

$$a(n)\sim {\frac {1}{2}}{n!}\,c^{n+1},$$

где $c={\tfrac {1}{\log 2}}\approx 1.4427$. Таким образом, упорядоченные числа Белла в экспоненциальном масштабе превышают факториалы. Здесь, как и в приближении Стирлинга к факториалу, $\sim$ указывает на асимптотическую эквивалентность . То есть отношение между упорядоченными числами Белла и их аппроксимацией в пределе стремится к единице как $n$ становится сколь угодно большим. Как выражено в небольших обозначениях , относительная ошибка равна $1\pm o(1)$и $o(1)$ Член ошибки убывает экспоненциально, поскольку $n$ растет.

Сравнивая приближения для $a(n-1)$ и $a(n)$ показывает, что

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

Например, взяв $n=5$ дает приближение $375/541\approx 0.693161$ к $\log 2\approx 0.693145$.Эта последовательность приближений и этот пример из нее были рассчитаны Рамануджаном , используя общий метод численного решения уравнений (здесь уравнение $e^{x}=2$).

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

Как и приведенные выше формулы, упорядоченные числа Белла можно вычислить по рекуррентному соотношению

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

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

$a(n+4)\equiv a(n){\pmod {10}},$

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

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

$a(n+500)\equiv a(n){\pmod {10000}}.$

Известны многие другие модульные тождества, включая тождества по модулю любой простой степени . Питер Бала предположил, что эта последовательность в конечном итоге является периодической (после конечного числа членов) по модулю каждого положительного целого числа. $k$, с периодом, который делит Эйлера полную функцию $k$, число остатков mod $k$ которые относительно просты для $k$.

Приложения

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

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

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

В теории чисел упорядоченное мультипликативное разбиение представляет натурального числа собой представление числа в виде произведения одного или нескольких его делителей . Например, число 30 имеет 13 мультипликативных разбиений как произведение одного делителя (само 30), двух делителей (например, 6 · 5 ) или трех делителей ( 3 · 5 · 2 и т. д.). Целое число не содержит квадратов, если оно является произведением различных простых чисел ; Число 30 не содержит квадратов, а число 20 — нет, поскольку его простое факторизация 2 · 2 · 5 повторяет простое число 2. Для чисел без квадратов с $n$ простые множители, упорядоченное мультипликативное разбиение можно описать слабым упорядочением его простых множителей, описывающим, какое простое число появляется в каком члене разбиения. Таким образом, количество упорядоченных мультипликативных разбиений определяется выражением $a(n)$. С другой стороны, для простой степени с показателем $n$, упорядоченное мультипликативное разбиение представляет собой произведение степеней одного и того же простого числа с показателями, равными $n$, и эта упорядоченная сумма показателей композицией является $n$. Таким образом, в данном случае существуют $2^{n-1}$ упорядоченные мультипликативные разбиения. Числа, которые не являются ни свободными от квадратов, ни простыми степенями, имеют ряд упорядоченных мультипликативных разбиений, которые (в зависимости от количества простых множителей) находятся между этими двумя крайними случаями.

Функция парковки в математике представляет собой конечную последовательность натуральных чисел со свойством, что для каждого $i$ до длины последовательности последовательность содержит по крайней мере $i$ значения, которые являются максимальными $i$. Последовательность такого типа длиной $n$, описывает следующий процесс: последовательность $n$ машины приезжают на улицу с $n$ парковочные места. У каждой машины есть предпочтительное место для парковки, определяемое ее значением в последовательности. Когда машина выезжает на улицу, она паркуется в предпочтительном для нее месте или, если оно занято, в следующем доступном месте. Последовательность предпочтений образует функцию парковки тогда и только тогда, когда каждый автомобиль может найти место для парковки на своем предпочтительном месте или после него. Количество парковочных функций длины $n$ это точно $(n+1)^{n-1}$. Для ограниченного класса функций парковки, в котором каждая машина паркуется либо на своем предпочтительном месте, либо на следующем месте, количество функций парковки определяется упорядоченными номерами Bell. Каждая функция ограниченной парковки соответствует слабому упорядочению, при котором автомобили, занимающие предпочтительное место, упорядочиваются по этим местам, а каждая оставшаяся машина привязана к машине, занимающей предпочтительное место. Перестановки . , подсчитанные факториалами, представляют собой функции парковки, при которых каждый автомобиль паркуется в предпочитаемом им месте Это приложение также обеспечивает комбинаторное доказательство верхних и нижних границ упорядоченных чисел Белла простой формы:

$$n!\leq a(n)\leq (n+1)^{n-1}.$$

Комплекс Кокстера для $A_{3}$ разрезает пространство на 24 треугольных конуса, показанных здесь их пересечениями с единичной сферой . Плоскости отражения $A_{3}$ нарежьте сферу большими кругами . Грани комплекса пересекают сферу по 24 треугольникам, 36 дугам и 14 вершинам; еще одно лицо в центре сферы не видно.

Заказанный номер звонка $a(n)$ подсчитывает количество граней в комплексе Кокстера, связанных с группой Кокстера типа $A_{n-1}$. Здесь группу Кокстера можно рассматривать как конечную систему симметрий отражений, замкнутую относительно многократных отражений, зеркала которой разбивают евклидово пространство на ячейки комплекса Кокстера. Например, $a(3)=13$ соответствует $A_{2}$, система отражений евклидовой плоскости от трех прямых, которые встречаются в начале координат в точке $60^{\circ }$ углы. Комплекс, образованный этими тремя линиями, имеет 13 граней: начало координат, шесть лучей от начала координат и шесть областей между парами лучей.

Кемени (1956) использует упорядоченные числа Белла для анализа n -арных отношений — математических утверждений, которые могут быть верны для некоторых вариантов выбора. $n$ аргументы для отношения и ложные для других. Он определяет «сложность» отношения как количество других отношений, которые можно получить из данного, переставляя и повторяя его аргументы. Например, для $n=2$, отношение двух аргументов $x$ и $y$ может принять форму $y=f(x)$. Согласно анализу Кемени, это $a(n)=3$ производные отношения. Это заданное соотношение $y=f(x)$, обратное соотношение $x=f(y)$ полученное заменой аргументов, и унарное отношение $x=f(x)$ полученное повторением аргумента. (Повторение другого аргумента приводит к тому же отношению.)

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

Другое

Если честная монета (с одинаковой вероятностью выпадения орла или решки) подбрасывается несколько раз до тех пор, пока в первый раз результатом не станет орел, количество решок следует геометрическому распределению . Моменты этого распределения представляют собой упорядоченные числа Белла.

Хотя обычная производящая функция упорядоченных чисел Белла не сходится, она описывает степенной ряд , который (оценивается при ${\tfrac {1}{n}}$ а затем умножить на ${\tfrac {2}{n}}$) обеспечивает асимптотическое разложение расстояния сопротивления противоположных вершин $n$-мерный граф гиперкуба . Усечение этого ряда до ограниченного числа членов и последующее применение результата для неограниченных значений $n$ приближает сопротивление к сколь угодно высокому порядку.

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

При фильтрации спама проблема присвоения весов последовательностям слов со свойством, что вес любой последовательности превышает сумму весов всех ее подпоследовательностей, может быть решена с помощью веса $W(n)$ для последовательности $n$ слова, где $W(n)$ получается из рекуррентного уравнения

$$W(n)=1+\sum _{k=1}^{n-1}{\binom {n}{k}}W(n-1),$$

с базовым корпусом $W(1)=0$. Эта повторяемость отличается от приведенной ранее для упорядоченных чисел Белла в двух отношениях: отсутствием $W(0)$ член из суммы (поскольку рассматриваются только непустые последовательности) и добавление одного члена отдельно от суммы (чтобы результат превышал, а не равнялся сумме). Эти различия имеют компенсирующий эффект, и результирующие веса представляют собой упорядоченные числа Белла.