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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Подсчет)
(что значит n-я строфа ?)
(не показано 40 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') показывают количество возможных способов разбиения множества<ref>[[wikipedia:Partition of a set|Разбиение множества]]</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>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.
 
==Подсчет==
 
==Подсчет==
Разбиения множеств могут быть расположены частично-упорядоченном виде<ref>[[Частичный порядок]]</ref>. Каждое подмножество размера <tex dpi="130">n</tex> имеет одно из подмножеств размера <tex dpi="130">n-1</tex>.
 
 
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
 
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
[[File:Order.png|400px|border|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины 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> различными способами:
  
 
:<tex>  \{ a \} , \{ b \} , \{ c \} </tex>
 
:<tex>  \{ a \} , \{ b \} , \{ c \} </tex>
Строка 37: Строка 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>.
  
Строка 47: Строка 46:
 
:<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=\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> непустых подмножеств.  
 
Майкл Спайви<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(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>
 
:<tex dpi = "150">B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>
 
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
 
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
Строка 59: Строка 58:
 
===Моменты распределения вероятностей===
 
===Моменты распределения вероятностей===
  
Числа Белла удовлетворяют '''формуле Добинского'''
+
Числа Белла удовлетворяют '''формуле Добинского''':
 
:<tex dpi = "150">B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</tex>
 
:<tex dpi = "150">B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</tex>
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя  ряд Тейлора <ref>[[wikipedia:Taylor series|Ряд Тейлора]]</ref> для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты. <ref>Flajolet & Sedgewick (2009)</ref>.
+
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя  ряд Тейлора<ref>[[wikipedia:Taylor series|Ряд Тейлора]]</ref> для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты.<ref>Flajolet & Sedgewick (2009)</ref>.
 
Это позволяет интерпретировать ''B<sub>n</sub>'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.
 
Это позволяет интерпретировать ''B<sub>n</sub>'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.
  
Строка 86: Строка 85:
 
:<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: Строка 97:
 
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''.
 
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''.
 
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
 
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, r}</tex> где <tex>r</tex> последний элемент <tex>(i-1)</tex> -й строки)
+
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</tex>)
# Определим остальные элементы строки <tex>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-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>3</tex>, пока <tex> j = r + 1 </tex>)
 
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
Первые пять строк треугольника, построенного по этим правилам:
 
Первые пять строк треугольника, построенного по этим правилам:
Строка 117: Строка 115:
  
 
===Получение с помощью чисел Стирлинга второго рода===
 
===Получение с помощью чисел Стирлинга второго рода===
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']]: связаны друг с другом по следующей формуле:
+
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']] связаны друг с другом по следующей формуле:
 
<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 
<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 
</tex>
 
</tex>
Заполним таблицу [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']], используя данную формулу.
 
 
Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую  <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на  непустых подмножеств, то есть <tex>n</tex>-ое число Белла.
 
Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую  <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на  непустых подмножеств, то есть <tex>n</tex>-ое число Белла.
Соответственно, сумма чисел <tex>n</tex>-столбца таблицы будет являться  <tex>n</tex>-ымчислом Белла.
+
 
 +
Заполним таблицу чисел Стирлинга, используя формулу выше.
 +
Cумма чисел <tex>n</tex>-ой строки будет являться  <tex>n</tex>-ым числом Белла.
 
{| border="1"
 
{| border="1"
 
  |-
 
  |-

Версия 18:11, 28 сентября 2020

Определение:
В комбинаторной математике числа Белла (англ. 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 участием биномиальных коэффициентов 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] непустых подмножеств. Майкл Спайви[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(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