Числа Белла

Определение:

В комбинаторной математике числа Белла (англ. Bell's numbers) определяют количество возможных способов разбиения множества из [math]n[/math] элементов на подмножества.

Числа Белла начинаются с [math]B_0=B_1=1[/math] и образуют последовательность:

[math]1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, \newline{} 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots [/math]

[math]n[/math]-й элемент чисел Белла, [math]B_n[/math], определяет количество различных способов разбиения множества, то есть количество отношений эквивалентности в нем.

Подсчет

Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество размера [math]n[/math] имеет одно из подмножеств размера [math]n-1[/math].

52 разбиения множества из 5 элементов

Разбиение множества [math]S[/math] определяется как совокупность непустых, попарно непересекающихся подмножеств множества [math]S[/math]. Например, [math]B_3 = 5[/math], потому что множество, состоящее их [math]3[/math] элементов [math] \{ a, b , c \} [/math] может быть разделено [math]5[/math] различными способами:

[math] \{ a \} , \{ b \} , \{ c \} [/math]

[math] \{ a \} , \{b, c \} [/math]

[math] \{ b \} , \{a, c \} [/math]

[math] \{ c \} , \{ a, b \} [/math]

[math] \{ a, b , c \} [/math]

[math]B_0 = 1[/math], т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными:

[math] \{ b \} , \{ a , c \} [/math]

[math]\{ a, c\}, \{ b \} [/math]

[math]\{ b \}, \{ c, a \} [/math]

[math]\{ c, a \}, \{ b \} [/math]

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

Факторизации

Если число [math]N[/math]является свободным от квадратов , то [math]B_n[/math] показывает количество различных мультипликативных разбиений [math]N[/math]. Если [math]N[/math] является квадратичным положительным целым числом (является произведением некоторого числа [math]n[/math] различных простых чисел), то [math]B_n[/math] дает число различных мультипликативных разбиений [math]N[/math]. Это является факторизацией [math]N[/math] в числа большие, чем [math]1[/math] (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле. Например, [math]30[/math] является произведением [math]3[/math] простых чисел [math]2[/math], [math]3[/math] и [math]5[/math] и имеет [math]N=5 [/math] факторизаций:

[math]30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5[/math]

Схемы рифмовки

Числа Белла показывают количество схем рифмовки [math]n[/math]-ой строфы. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, [math]15[/math] возможных четверостиший схемами рифмовки являются: [math] \newline{} AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD[/math].

Свойства

Формулы суммирования

Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:

[math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.[/math]

Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода:

[math]B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.[/math]

Число Стирлинга [math]\left\{{n\atop k}\right\}[/math] является количеством способов разбиения набора элементов [math]n[/math] в ровно [math]k[/math] непустых подмножеств. Майкл Спайви получил формулу, которая объединяет оба эти суммирования:

[math]B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.[/math]

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

Экспоненциальной производящей функцией чисел Белла является:

[math]B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.[/math]

Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.

Моменты распределения вероятностей

Числа Белла удовлетворяют формуле Добинского:

[math]B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.[/math]

Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты.. Это позволяет интерпретировать B_n как [math]n[/math]-й момент Пуассоновского распределения с ожидаемым значением [math]1[/math].

Интегральное представление

Применение интегральной формулы Коши для экспоненциальной производящей функции дает комплексное интегральное представление:

[math] B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. [/math]

Логарифмическая вогнутость

Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, [math]\frac{B_n}{n!}[/math], дает логарифмически выпуклую последовательность.

Темпы роста

Известно несколько асимптотических формул для чисел Белла. Беренд Тасса в [math]2010[/math]-м установлил следующие границы:

[math] B_n \lt \left( \frac{0.792 n}{\ln( n+1)} \right)^n [/math] для всех положительных чисел [math]n[/math];

кроме того, если [math] \varepsilon\gt 0 [/math] затем для всех [math] n \gt n_0(\varepsilon) [/math],

[math] B_n \lt \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n [/math]

где [math] ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ [/math] и [math] ~d(x)= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,. [/math] Числа Белла могут быть аппроксимированы с помощью функции Ламберта [math]W[/math] , данная функция имеет такой же темп роста, как логарифм, как

[math]B_n \sim \frac{1}{\sqrt{n}} \left( \frac{n}{W(n)} \right)^{n + \frac{1}{2}} \exp\left(\frac{n}{W(n)} - n - 1\right). [/math]

Мозер Л. и Вайман М. установили расширение:

[math]B_{n+h} = \frac{(n+h)!}{W(n)^{n+h}} \times \frac{\exp(e^{W(n)} - 1)}{(2\pi B)^{1/2}} \times \left( 1 + \frac{P_0 + hP_1 + h^2P_2}{e^{W(n)}} + \frac{Q_0 + hQ_1 + h^2Q_2 + h^3Q_3 + h^4Q_4}{e^{2W(n)}} + O(e^{-3W(n)}) \right)[/math]

Асимптотическое выражение

[math] $$ \frac{\ln B_n}{n} = \ln n - \ln \ln n - 1 + \frac{\ln \ln n}{\ln n} + \frac{1}{\ln n} + \frac{1}{2}\left(\frac{\ln \ln n}{\ln n}\right)^2 + O\left(\frac{\ln \ln n}{(\ln n)^2} \right) $$ \newline {} \qquad \text{as }n\to\infty [/math]

Было установлено де Брайном в [math]1981[/math] году.

Получение

Вычисление с помощью треугольника Пирса

Треугольное множество, правая диагональная последовательность которого состоит из чисел Белла

Числа Белла могут быть с легкостью вычислены с помощью треугольника Белла, который также называют массивом Айткена или треугольником Пирса.

1. Начнем с единицы. Помещаем ее в верхнюю строку. ([math] x_{0,1} = 1 [/math])
2. Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ([math]x_{i,1} \leftarrow x_{i-1, r}[/math] где [math]r[/math] последний элемент [math](i-1)[/math] -й строки)
3. Определим остальные элементы строки [math]( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )[/math]
4. Повторяем пункт [math]3[/math], пока [math] j = r + 1 [/math])
5. Крайнее левое число данной строки является числом Белла для этой строки. ([math]B_i \leftarrow x_{i,1}[/math])

Первые пять строк треугольника, построенного по этим правилам:

[math]1[/math]
[math]1[/math]	[math]2[/math]
[math]2[/math]	[math]3[/math]	[math]5[/math]
[math]5[/math]	[math]7[/math]	[math] 10[/math]	[math] 15[/math]
[math]15[/math]	[math] 20[/math]	[math]27[/math]	[math]37[/math]	[math]52[/math]

Получение с помощью чисел Стирлинга второго рода

Числа Стирлинга второго рода: связаны друг с другом по следующей формуле: [math]\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} [/math] Заполним таблицу чисел Стирлинга второго рода, используя данную формулу. Число Стирлинга второго рода показывает количество способов разбиения множества из [math]n[/math] элементов на [math]k[/math] непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую [math]n[/math], то получим количество способов разбиения множества из [math]n[/math] элементов на непустых подмножеств, то есть [math]n[/math]-ое число Белла. Соответственно, сумма чисел [math]n[/math]-столбца таблицы будет являться [math]n[/math]-ымчислом Белла.

n \ k	[math]0[/math]	[math]1[/math]	[math]2[/math]	[math]3[/math]	[math]4[/math]	Число Белла
[math]0[/math]	[math]1[/math]					[math]1[/math]
[math]1[/math]	[math]0[/math]	[math]1[/math]				[math]1[/math]
[math]2[/math]	[math] 0[/math]	[math]1[/math]	[math]1[/math]			[math]2[/math]
[math]3[/math]	[math]0[/math]	[math]1[/math]	[math]3[/math]	[math]1[/math]		[math]5[/math]
[math]4[/math]	[math]0[/math]	[math]1[/math]	[math]7[/math]	[math]6[/math]	[math]1[/math]	[math]15[/math]

См.также

• Числа Стирлинга второго рода
• Числа Стирлинга первого рода
• Числа Эйлера I и II рода

Источники информации

• Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006
• Wikipedia —Bell numbers
• Nobuhiro Izumi Hui-Hsiung "Acta Applicandae Texematicae",79–87.Bell numbers, log-concavity, and log-convexity 2000
• Aitken A. C. Edinburgh Texematical Notes,18–23 A problem in combinations 1933
• H. W.BeckerJohn Riordan "The arithmetic of Bell and Stirling numbers" American Journal of Texematics,1948,385–394
• E. T.Bell Exponential polynomials,Annals of Texematics,1934, 258–277
• E. T.Bell The iterated exponential integers,Annals of Texematics,1938,539–557