Числа Белла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вычисление с помощью треугольника Пирса)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') определяют количество возможных способов разбиения множества<ref>[[Комбинаторные объекты#Разбиение на подмножества]]</ref> из <tex>n</tex> элементов на подмножества.  
+
|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') определяют количество возможных способов [[Комбинаторные объекты#Разбиение на подмножества|разбиения множества]] из <tex>n</tex> элементов на подмножества.  
 
}}
 
}}
 
Числа Белла начинаются с  <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность:
 
Числа Белла начинаются с  <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность:
 
:<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437,  
 
:<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437,  
\newline{} 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots
+
190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots
 
  </tex>
 
  </tex>
 
<tex dpi="130">n</tex>-й элемент множества чисел Белла, <tex dpi="130">B_n</tex>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.
 
<tex dpi="130">n</tex>-й элемент множества чисел Белла, <tex dpi="130">B_n</tex>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.
 
==Подсчет==
 
==Подсчет==
 
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
 
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
[[File:Order.png|400px|border|Разбиения множеств могут быть расположены частично-упорядоченном виде<ref>[[Отношение порядка#Частичный порядок]]</ref>. Каждое подмножество длины n использует одно из подмножеств длины <tex dpi="130">n-1</tex>.]]
+
[[File:Order.png|400px|border]]
  
 
Разбиение множества <tex dpi="130">S</tex> определяется как совокупность '''попарно непересекающихся подмножеств множества''' <tex dpi="130">S</tex>. Например, <tex>B_3 = 5</tex>, потому что множество, состоящее их <tex>3</tex> элементов  <tex> \{ a, b , c \} </tex> может быть разделено <tex>5</tex> различными способами:
 
Разбиение множества <tex dpi="130">S</tex> определяется как совокупность '''попарно непересекающихся подмножеств множества''' <tex dpi="130">S</tex>. Например, <tex>B_3 = 5</tex>, потому что множество, состоящее их <tex>3</tex> элементов  <tex> \{ a, b , c \} </tex> может быть разделено <tex>5</tex> различными способами:
Строка 36: Строка 36:
  
 
==Схемы рифмовки==
 
==Схемы рифмовки==
Числа Белла показывают ''количество схем рифмовки <tex dpi="130">n</tex>-ой строфы''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, <tex>15</tex> возможных четверостиший схемами рифмовки являются:
+
Числа Белла показывают ''количество схем рифмовки на <tex dpi="130">n</tex> строках''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как отношение экивалентности на множестве строк. Таким образом, <tex>15</tex> возможных четверостиший схемами рифмовки являются:
<tex dpi="130"> \newline{} AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
+
<tex dpi="130"> AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
 
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,  ABCD</tex>.
 
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,  ABCD</tex>.
  
Строка 43: Строка 43:
  
 
===Формулы суммирования===
 
===Формулы суммирования===
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:
+
====Биномиальные коэффициенты====
 +
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов:
 
:<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>
 
:<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>
 +
==== Доказательство ====
 +
Докажем, что  <tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}.</tex> По определению <tex dpi = "150">B_{n}\ { — }\ </tex>число всех неупорядоченных подмножеств <tex>n</tex>-элементного множества. Посчитаем количество неупорядоченных подмножеств для <tex dpi= "150">(n+1)</tex>-элементного множества множества: Пусть <tex dpi= "150">x_1 \cup... \cup x_k\ { — }\ </tex>подмножества множества <tex dpi= "150">[1...n+1]</tex>. Пусть <tex dpi= "150">n+1\in x_k</tex>, тогда <tex dpi= "150">x_1 \cup... \cup x_{k-1}\ { — }\ </tex>подмножество множества <tex dpi="150">[1...n+1]</tex> \ <tex dpi= "150">x_k</tex>. Пусть <tex dpi= "150">|x_k|=i+1</tex>, где <tex dpi= "150">i\in [0;n]</tex>, тогда <tex dpi= "150">x_k</tex> можно выбрать <tex dpi= "150">\binom{n}{i}</tex> способами, а оставшиеся элементы разбить <tex dpi = "150">B_{n-i}</tex> способами. <tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}=</tex> <tex dpi = "150">\sum_{k=0}^{n} \binom{n}{n-k} B_{k}=</tex> <tex dpi= "150">\sum_{k=0}^{n} \binom{n}{k} B_k</tex>.
 +
 +
====Связь с числами Стирлинга второго рода====
 
Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]:
 
Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]:
 
:<tex dpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}</tex>,  
 
:<tex dpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}</tex>,  
где число Стирлинга <tex dpi = "150">\left\{{n\atop k}\right\}</tex> является количеством способов разбиения набора элементов <tex dpi = "150">n</tex> в ровно <tex dpi="150">k</tex> непустых подмножеств.  
+
где число Стирлинга <tex dpi = "150">\left\{{n\atop k}\right\}</tex> является количеством способов разбиения набора элементов <tex dpi = "150">n</tex> в ровно <tex dpi="150">k</tex> непустых подмножеств.
 +
==== Доказательство ====
 +
Посчитаем количество подмножеств <tex dpi= "150">n</tex>-элементного множества. Нам нужно разбить <tex dpi= "150">n</tex>-элементное множество на <tex dpi= "150">k</tex> непустых подмножеств, где <tex dpi= "150">k</tex> от <tex dpi= "150">1</tex> до <tex dpi= "150">n</tex>. Пусть
 +
<tex dpi= "150">C\ { — }\ </tex>все подмножества <tex dpi= "150">n</tex>-элементного множества. Пусть <tex dpi= "150">A_k\ { — }\ </tex>разбиение <tex dpi= "150">n</tex>-элементного множества на <tex dpi= "150">k</tex> непустых подмножеств, тогда <tex dpi = "150"> C = \bigcup \limits_{k=1}^{n}A_k</tex>. <tex dpi = "150">|A_k|=\left\{{n\atop k}\right\}\ { — }\ </tex>по определению, тогда <tex dpi = "150">B_n=|C|=\sum_{k=1}^{n} \ |A_k|=\sum_{k=1}^n \left\{{n\atop k}\right\}=\sum_{k=0}^n \left\{{n\atop k}\right\}</tex>, т.к. <tex dpi = "150">\left\{{n\atop 0}\right\}=0</tex>.
 +
 
 +
====Объединяющая формула====
 
Майкл Спайви<ref>Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.</ref>  получил формулу, которая объединяет оба эти суммирования:
 
Майкл Спайви<ref>Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.</ref>  получил формулу, которая объединяет оба эти суммирования:
 
:<tex dpi = "150">B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.</tex>
 
:<tex dpi = "150">B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.</tex>
 +
==== Лемма ====
 +
<tex dpi = "150">B_{n+m}\ { — }\ </tex>количество способов разбить <tex dpi = "150">(n+m)</tex>-элементное множество на подмножества. Количество способов разбить <tex dpi = "150">m</tex>-элементное множество на <tex dpi = "150">j</tex> непустых подмножеств это <tex dpi = "150">\left\{{m\atop j}\right\}</tex>, где <tex dpi = "150">j</tex> меняется от <tex dpi = "150">1</tex> до <tex dpi = "150">m</tex>. Из оставшихся <tex dpi = "150">n</tex> объектов выберем <tex dpi = "150">k</tex>, для разделения их на новые подмножества, а оставшиеся <tex dpi = "150">n-k</tex> объектов распределим между <tex dpi = "150">j</tex> подмножествами, сформированных из <tex dpi = "150">m</tex>-элементного множества. <tex dpi = "150">B_{k}\ { — }\ </tex>количество разбиений <tex dpi = "150">k</tex>-элементного множества на подмножества и <tex dpi = "150">j^{n-k}</tex> способов разбить <tex dpi = "150">n-k</tex> элементов между <tex dpi = "150">j</tex> подмножествами. Значит <tex dpi = "150">j^{n-k} \left\{{n\atop k}\right\}\binom{n}{k} B_{k}</tex> способов разбить <tex dpi = "150">m</tex> элементов на <tex dpi = "150">j</tex> подмножеств и выбрать <tex dpi = "150">k</tex> элементов из <tex dpi = "150">n</tex>-элементного множества и выбрать <tex dpi = "150">k</tex> элементов из <tex dpi = "150">n </tex>-элементного множества и сформировать из них новые подмножества, а из оставшихся <tex dpi = "150">n-k</tex> объектов разделить между <tex dpi = "150">j</tex> множествами, сформированных из <tex dpi = "150">m</tex>-элементного множества.
 +
 +
==== Доказательство ====
 +
Суммируя подмножества, рассмотренные в лемме, меняя <tex dpi = "150">m</tex> и <tex dpi = "150">k</tex>, получаем:
 +
<tex dpi = "150">B_{n+m}=\sum_{k=0}^n \sum_{j=1}^m </tex><tex dpi = "150">\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}=</tex><tex dpi = "150">B_{n+m}=\sum_{k=0}^n \sum_{j=0}^m </tex><tex dpi = "150">\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}</tex> т.к. <tex dpi = "150">\left\{{m\atop 0}\right\}=0</tex>.
  
 
===Производящая функция===
 
===Производящая функция===
Строка 85: Строка 101:
 
:<tex dpi = "150">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)</tex>
 
:<tex dpi = "150">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)</tex>
 
Асимптотическое выражение
 
Асимптотическое выражение
:<tex dpi = "150">
+
:<tex dpi = "150">  
$$ \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) $$
+
\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
+
\qquad \text{as }n\to\infty
 
</tex>
 
</tex>
 
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году.
 
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году.
Строка 98: Строка 114:
 
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
 
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
 
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</tex>)
 
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</tex>)
#  Заполняем строчку <tex>i</tex>, начиная с <tex>i = 1</tex>, по формуле <tex> x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} </tex> , где <tex>j</tex> - номер столбца, пока  <tex>j \leq i + 1 </tex>.
+
#  Заполняем строчку <tex>i</tex> по формуле <tex> ( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1}) </tex> , начиная с <tex> j = 2 </tex>, пока  <tex>j \leqslant i + 1 </tex>.
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
Первые пять строк треугольника, построенного по этим правилам:
 
Первые пять строк треугольника, построенного по этим правилам:

Текущая версия на 19:40, 4 сентября 2022

Определение:
В комбинаторной математике числа Белла (англ. 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, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots [/math]

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

Подсчет

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

Order.png

Разбиение множества [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]является свободным от квадратов [1], то [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] (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле[2]. Например, [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] AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD[/math].

Свойства

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

Биномиальные коэффициенты

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

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

Доказательство

Докажем, что [math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}.[/math] По определению [math]B_{n}\ { — }\ [/math]число всех неупорядоченных подмножеств [math]n[/math]-элементного множества. Посчитаем количество неупорядоченных подмножеств для [math](n+1)[/math]-элементного множества множества: Пусть [math]x_1 \cup... \cup x_k\ { — }\ [/math]подмножества множества [math][1...n+1][/math]. Пусть [math]n+1\in x_k[/math], тогда [math]x_1 \cup... \cup x_{k-1}\ { — }\ [/math]подмножество множества [math][1...n+1][/math] \ [math]x_k[/math]. Пусть [math]|x_k|=i+1[/math], где [math]i\in [0;n][/math], тогда [math]x_k[/math] можно выбрать [math]\binom{n}{i}[/math] способами, а оставшиеся элементы разбить [math]B_{n-i}[/math] способами. [math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_{n-k}=[/math] [math]\sum_{k=0}^{n} \binom{n}{n-k} B_{k}=[/math] [math]\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]n[/math]-элементного множества. Нам нужно разбить [math]n[/math]-элементное множество на [math]k[/math] непустых подмножеств, где [math]k[/math] от [math]1[/math] до [math]n[/math]. Пусть [math]C\ { — }\ [/math]все подмножества [math]n[/math]-элементного множества. Пусть [math]A_k\ { — }\ [/math]разбиение [math]n[/math]-элементного множества на [math]k[/math] непустых подмножеств, тогда [math] C = \bigcup \limits_{k=1}^{n}A_k[/math]. [math]|A_k|=\left\{{n\atop k}\right\}\ { — }\ [/math]по определению, тогда [math]B_n=|C|=\sum_{k=1}^{n} \ |A_k|=\sum_{k=1}^n \left\{{n\atop k}\right\}=\sum_{k=0}^n \left\{{n\atop k}\right\}[/math], т.к. [math]\left\{{n\atop 0}\right\}=0[/math].

Объединяющая формула

Майкл Спайви[3] получил формулу, которая объединяет оба эти суммирования:

[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_{n+m}\ { — }\ [/math]количество способов разбить [math](n+m)[/math]-элементное множество на подмножества. Количество способов разбить [math]m[/math]-элементное множество на [math]j[/math] непустых подмножеств это [math]\left\{{m\atop j}\right\}[/math], где [math]j[/math] меняется от [math]1[/math] до [math]m[/math]. Из оставшихся [math]n[/math] объектов выберем [math]k[/math], для разделения их на новые подмножества, а оставшиеся [math]n-k[/math] объектов распределим между [math]j[/math] подмножествами, сформированных из [math]m[/math]-элементного множества. [math]B_{k}\ { — }\ [/math]количество разбиений [math]k[/math]-элементного множества на подмножества и [math]j^{n-k}[/math] способов разбить [math]n-k[/math] элементов между [math]j[/math] подмножествами. Значит [math]j^{n-k} \left\{{n\atop k}\right\}\binom{n}{k} B_{k}[/math] способов разбить [math]m[/math] элементов на [math]j[/math] подмножеств и выбрать [math]k[/math] элементов из [math]n[/math]-элементного множества и выбрать [math]k[/math] элементов из [math]n [/math]-элементного множества и сформировать из них новые подмножества, а из оставшихся [math]n-k[/math] объектов разделить между [math]j[/math] множествами, сформированных из [math]m[/math]-элементного множества.

Доказательство

Суммируя подмножества, рассмотренные в лемме, меняя [math]m[/math] и [math]k[/math], получаем: [math]B_{n+m}=\sum_{k=0}^n \sum_{j=1}^m [/math][math]\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}=[/math][math]B_{n+m}=\sum_{k=0}^n \sum_{j=0}^m [/math][math]\left\{{m\atop j}\right\}j^{n-k} \binom{n}{k} B_{k}[/math] т.к. [math]\left\{{m\atop 0}\right\}=0[/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]

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

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

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

[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][7] установлил следующие границы:

[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] [8], данная функция имеет такой же темп роста, как логарифм, как

[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]

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

[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) \qquad \text{as }n\to\infty [/math]

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

Получение

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

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

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

  1. Начнем с единицы. Помещаем ее в верхнюю строку. ([math] x_{0,1} = 1 [/math])
  2. Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ([math]x_{i,1} \leftarrow x_{i-1, i}[/math])
  3. Заполняем строчку [math]i[/math] по формуле [math] ( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1}) [/math] , начиная с [math] j = 2 [/math], пока [math]j \leqslant i + 1 [/math].
  4. Крайнее левое число данной строки является числом Белла для этой строки. ([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]-ое число Белла.

Заполним таблицу чисел Стирлинга, используя формулу выше. Cумма чисел [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]

См.также

Примeчания

  1. Wikipedia — Cвободные от квадратов числа
  2. Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
  3. Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.
  4. Ряд Тейлора
  5. Flajolet & Sedgewick (2009)
  6. Формула Коши
  7. Berend, D.; Tassa, T. (2010). "Improved bounds on Bell numbers and on moments of sums of random variables". Probability and Mathematical Statistics. 30 (2): 185–205.
  8. Функция Ламберта W
  9. Moser, Leo; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III.
  10. de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.

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

  • 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