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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулы суммирования)
м (rollbackEdits.php mass rollback)
 
(не показано 208 промежуточных версий 13 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = В комбинаторной математике числа Белла показывают количество возможных способов разбиения множества из ''n''элементов на непустые подмножества. Эти числа изучались математиками с 17-го века. Их корни уходят в средневековую Японию. Названы в честь Эрика Темпла Белла, который описал их в 1930-х годах.  
+
|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') определяют количество возможных способов [[Комбинаторные объекты#Разбиение на подмножества|разбиения множества]] из <tex>n</tex> элементов на подмножества.  
 
}}
 
}}
Числа Белла начинаются с  ''B''<sub>0</sub> = ''B''<sub>1</sub> = 1 и образуют последовательность :
+
Числа Белла начинаются с  <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность:
:1, 1,2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ...
+
:<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437,  
''n''- элемент чисел Белла, ''B<sub>n</sub>'', показывает количество различных способов разбиения множества, которое имеет не менее ''n'' элементов, т.е. количеству [[Отношение эквивалентности|отношений эквивалентности]] в нем.
+
190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots
Вне математики, похожие числа показывают количество различных схем рифмовки для ''n''-й строфы стихотворения.
+
</tex>
 +
<tex dpi="130">n</tex>-й элемент множества чисел Белла, <tex dpi="130">B_n</tex>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.
 
==Подсчет==
 
==Подсчет==
===Разделение набора===
+
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]]
[[File:Order.png|thumb|upright|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины n-1.]]
+
[[File:Order.png|400px|border]]
[[File:XxxCircles.png|thumb|upright|52 разбиения множества из 5 элементов]]
 
''B''<sub>''n''</sub> количество разбиений множества размера ''n''. Разбиение множества ''S'' определяется как совокупность '''непустых, попарно непересекающихся подмножеств множества ''S'' '''. Например, ''B''<sub>3</sub>&nbsp;=&nbsp;5, потому что множество, состоящее их 3 элементов  {''a'',&nbsp;''b'',&nbsp;''c''} может быть разделено 5 различным способами:
 
  
:{ {''a''}, {''b''}, {''c''} }
+
Разбиение множества <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> различными способами:
:{ {''a''}, {''b'', ''c''} }
 
:{ {''b''}, {''a'', ''c''} }
 
:{ {''c''}, {''a'', ''b''} }
 
:{ {''a'', ''b'', ''c''} }.
 
  
''B''<sub>0</sub> является 1, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом, пустое множество может разбиваться только на само себя.
+
:<tex\{ a \} , \{ b \} , \{ c \} </tex>
Как было обозначено выше, мы '''не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них '''. Это означает, что данные разбиения являются идентичными:
+
: <tex>  \{ a \} , \{b, c \} </tex>
:{ {''b''}, {''a'', ''c''} }
+
: <tex>  \{ b \} , \{a, c \} </tex>
:{ {''a'', ''c''}, {''b''} }
+
: <tex> \{ c \} , \{ a, b \} </tex>
:{ {''b''}, {''c'', ''a''} }
+
: <tex> \{ a, b , c \} </tex>
:{ {''c'', ''a''}, {''b''} }.
 
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются упорядоченными числами Белла.
 
  
===Факторизации===
+
<tex dpi="130">B_0 = 1</tex>, т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя.
Если число ''N'' является свободным от квадратов, то ''B<sub>n</sub>'' показывает количество различных мультипликативных
+
Как было обозначено выше, мы '''не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них'''. Это означает, что данные разбиения являются идентичными:
Если число ''N'' является квадратичным положительным целым числом (является произведением некоторого числа '' n''  различных простых чисел), то B<sub>n</sub> дает '''число различных мультипликативных разбиений  ''N'' '''. Это является факторизацией ''N'' в числа большие, чем 1(рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле(''Principii di Analisi Combinatoria'', 1909).</ref> Например, 30 является произведением  3 простых чисел 2, 3, and&nbsp;5, и имеет ''B''<sub>3</sub> = 5 факторизаций:
+
: <tex> \{ b \} , \{ a , c \} </tex>
:<tex>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</tex>
+
: <tex>\{ a, c\}, \{ b \} </tex>
 +
: <tex>\{ b \}, \{ c, a \} </tex>
 +
: <tex>\{ c, a \}, \{ b \} </tex>
  
===Схемы рифмовки===
 
Числа Белла показывают '''количество схем рифмовки ''n''-строфы'''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, 15 возможных четверостиший схемами рифмовки являются: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.
 
  
==Вычисление с помощью треугольника Пирса==
+
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются '''упорядоченными числами Белла'''.
  
[[Image:BellNumberAnimated.gif|right|thumb| Треугольное множество, правая диагональная последовательность которого состоит из чисел Белла]]
+
==Факторизации==
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют массивом Айткена или треугольником Пирса.
+
Если число <tex dpi="130">N</tex>является свободным от квадратов <ref>[[wikipedia:Square-free element|Wikipedia {{---}} Cвободные от квадратов числа]]</ref>, то <tex dpi="130">B_n</tex> показывает количество различных мультипликативных разбиений  <tex dpi="130">N</tex>.
# Начнем с единицы. Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
+
Если <tex dpi="130">N</tex> является квадратичным положительным целым числом (является произведением некоторого числа <tex dpi="130">n</tex> различных простых чисел), то <tex dpi="130">B_n</tex> дает '''число различных мультипликативных разбиений''' <tex dpi="130">N</tex>. Это является факторизацией <tex dpi="130">N</tex> в числа большие, чем <tex>1</tex> (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле<ref> Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).</ref>.
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, r}</tex> где ''r'' последний элемент (''i''-1)-й строки)
+
Например, <tex>30</tex> является произведением <tex>3</tex> простых чисел <tex>2</tex>, <tex>3</tex> и <tex>5</tex> и имеет <tex dpi="130">N=5 </tex> факторизаций:
# Определим остальные элементы строки <tex>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )</tex>  
+
:<tex>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</tex>
# Повторяем пункт 3, пока <tex> j = r + 1 </tex>)
 
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)
 
Первые пять строк треугольника, построенного по этим правилам:
 
  
  1
+
==Схемы рифмовки==
  1  2
+
Числа Белла показывают ''количество схем рифмовки на <tex dpi="130">n</tex> строках''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как отношение экивалентности на множестве строк. Таким образом, <tex>15</tex> возможных четверостиший схемами рифмовки являются:
  2  3  5
+
<tex dpi="130">  AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
   5  7  10  15
+
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,   ABCD</tex>.
15  20  27  37  52
 
  
 
==Свойства==
 
==Свойства==
  
 
===Формулы суммирования===
 
===Формулы суммирования===
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:
+
====Биномиальные коэффициенты====
:<tex>B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>
+
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов:
Другая формула суммирования представляет каждое число Белла как сумму [Числа Стирлинга второго рода|чисел Стирлинга второго рода]:
+
:<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>
:<tex>B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.</tex>
+
==== Доказательство ====
Число Стирлинга <tex>\left\{{n\atop k}\right\}</tex> является количеством способов разбиения набора элементов ''n'' в ровно ''k'' непустых подмножеств.  
+
Докажем, что  <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>.
Michael Spivey  получил формулу, которая объединяет оба эти суммирования:
 
:<tex>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>B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</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">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>  получил формулу, которая объединяет оба эти суммирования:
 +
:<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>.
 +
 
 +
===Производящая функция===
 +
Экспоненциальной [[производящая функция|производящей функцией]] чисел Белла является:
 +
:<tex dpi = "150">B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>
 
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
 
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
 +
 
===Моменты распределения вероятностей===
 
===Моменты распределения вероятностей===
  
Числа Белла удовлетворяют '''формуле Добинского'''{{sfn|Bender|Williamson|2006}}
+
Числа Белла удовлетворяют '''формуле Добинского''':
:<tex>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>.
Это позволяет интерпретировать ''B<sub>n</sub>'' как ''n''-й момент Пуассоновского распределения с ожидаемым значением 1.
+
Это позволяет интерпретировать ''B<sub>n</sub>'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.
  
 
===Интегральное представление===
 
===Интегральное представление===
Применение интегральной формулы Коши для экспоненциальной производящей функции дает комплексное интегральное представление:
+
Применение интегральной формулы Коши <ref>[[wikipedia:Cauchy's integral formula|Формула Коши]]</ref> для экспоненциальной производящей функции дает комплексное интегральное представление:
: <tex> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex>
+
: <tex dpi = "150"> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex>
===Log-concavity===
+
 
Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, ''B''<sub>''n''</sub>/''n''!,  дает логарифмически выпуклую последовательность.sequence.
+
===Логарифмическая вогнутость===
 +
Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, <tex dpi = "170">\frac{B_n}{n!}</tex>,  дает логарифмически выпуклую последовательность.
 +
 
 
===Темпы роста===
 
===Темпы роста===
 
Известно несколько асимптотических формул для чисел Белла.
 
Известно несколько асимптотических формул для чисел Белла.
'''Беренд Тасса''' в 2010-м  установлил следующие границы:
+
'''Беренд Тасса''' в <tex>2010</tex><ref>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.</ref> установлил следующие границы:
:<tex> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </tex> для всех положительных чисел  <tex>n</tex>;
+
:<tex dpi = "150"> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </tex> для всех положительных чисел  <tex>n</tex>;
 
кроме того, если <tex> \varepsilon>0 </tex> затем для всех  <tex> n > n_0(\varepsilon) </tex>,
 
кроме того, если <tex> \varepsilon>0 </tex> затем для всех  <tex> n > n_0(\varepsilon) </tex>,
:<tex> B_n < \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n </tex>
+
:<tex dpi = "150"> B_n < \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n </tex>
 
где  <tex> ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ </tex>  и
 
где  <tex> ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ </tex>  и
<tex> ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.
+
<tex dpi = "150"> ~d(x)= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.
 
</tex>
 
</tex>
Числа Белла могут быть аппроксимированы с помощью  [[wikipedia:Lambert W function|'''функции Ламберта Вт''']], данная функция имеет такой же темп роста, как логарифм, как
+
Числа Белла могут быть аппроксимированы с помощью  функции Ламберта <tex>W</tex> <ref> [[wikipedia:Lambert W function|Функция Ламберта W]]</ref>, данная функция имеет такой же темп роста, как логарифм, как
:<tex>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). </tex>
+
:<tex dpi = "150">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). </tex>
  
'''Moser Wyman''' установил расширение:
+
'''Мозер Л. и Вайман М.'''<ref>Moser, Leo; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III. </ref> установили расширение:
:<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>
+
:<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>
 
Асимптотическое выражение
 
Асимптотическое выражение
:<math>
+
:<tex dpi = "150">  
\begin{align}
+
\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) \\
+
\qquad \text{as }n\to\infty
& {} \qquad \text{as }n\to\infty
+
</tex>
\end{align}
+
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году.
</math>
 
Было установлено '''де Брайном''' в 1981 году.
 
  
==References==
+
==Получение==
*[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]
 
*[http://www.tex.ucsd.edu/~ebender/CombText/ch-11.pdf Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006]
 
* [[wikipedia:Bell numbers| Bell numbers]]
 
  
 +
[[Image:BellNumberAnimated.gif|right|thumb| Треугольное множество, правая диагональная последовательность которого состоит из чисел Белла]]
 +
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''.
 +
# Начнем с единицы.  Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)
 +
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</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>)
 +
Первые пять строк треугольника, построенного по этим правилам:
 +
{| border="1"
 +
|-
 +
|<tex>1</tex>|| || || ||
 +
|-
 +
|<tex>1</tex>|| <tex>2</tex>|| || ||
 +
|-
 +
| <tex>2</tex>||<tex>3</tex> ||<tex>5</tex> || ||
 +
|-
 +
|<tex>5</tex>||  <tex>7</tex>|| <tex> 10</tex>|| <tex> 15</tex>||
 +
|-
 +
|<tex>15</tex>|| <tex> 20</tex> || <tex>27</tex> || <tex>37</tex> || <tex>52</tex>
 +
|}
 +
 +
===Получение с помощью чисел Стирлинга второго рода===
 +
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']]  связаны друг с другом по следующей формуле:
 +
<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 +
</tex>
 +
Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую  <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на  непустых подмножеств, то есть <tex>n</tex>-ое число Белла.
 +
 +
Заполним таблицу чисел Стирлинга, используя формулу выше.
 +
Cумма чисел <tex>n</tex>-ой строки будет являться  <tex>n</tex>-ым числом Белла.
 +
{| border="1"
 +
|-
 +
| n \ k ||<tex>0</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||Число Белла
 +
|-
 +
|<tex>0</tex>||<tex>1</tex>|| || || |||| |<tex>1</tex>
 +
|-
 +
|<tex>1</tex>||<tex>0</tex>|| <tex>1</tex>|| || |||| |<tex>1</tex>
 +
|-
 +
|<tex>2</tex>||<tex> 0</tex>||<tex>1</tex> ||<tex>1</tex> || || |||<tex>2</tex>
 +
|-
 +
|<tex>3</tex>||<tex>0</tex>||  <tex>1</tex>||  <tex>3</tex>||  <tex>1</tex>|||| |<tex>5</tex>
 +
|-
 +
|<tex>4</tex>||<tex>0</tex>||  <tex>1</tex> || <tex>7</tex> || <tex>6</tex> || <tex>1</tex> ||<tex>15</tex>
 +
|}
 +
 +
== См.также ==
 +
*[[Числа Стирлинга второго рода]]
 +
*[[Числа Стирлинга первого рода]]
 +
*[[Числа Эйлера I и II рода]]
 
==Примeчания==
 
==Примeчания==
 
<references/>
 
<references/>
 +
 +
==Источники информации==
 +
*[https://cseweb.ucsd.edu/~gill/BWLectSite/Resources/C1U4SF.pdf  Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006]
 +
* [https://en.wikipedia.org/wiki/Bell_number 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
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Комбинаторика]]

Текущая версия на 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