Изменения

|definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') показывают определяют количество возможных способов [[Комбинаторные объекты#Разбиение на подмножества|разбиения множества ]] из ''<tex>n'' </tex> элементов на непустые подмножества.

\newline{} 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... \dots </tex><tex dpi="130">n</tex>- й элемент множества чисел Белла, <tex dpi="130">B_n</tex>, показывает определяет количество различных способов разбиения множества, то есть. количество [[Отношение эквивалентности|отношений эквивалентности]] в нем.Вне математики, похожие числа показывают количество различных схем рифмовки для <tex dpi="130">n</tex>-й строфы стихотворения. Эти числа изучались математиками с 17-го века, их корни уходят в средневековую Японию. Названы в честь Эрика Темпла Белла, который описал их в 1930-х годах.

[[File:Order.png|400px|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины <tex dpi="130">n-1</tex>.border]]

<tex dpi="130">B_n</tex> количество разбиений множества размера <tex dpi="130">n</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>: <tex> \{ b \} , \{a, c \} </tex>: <tex> \{ c \} , \{ a, b \} </tex>: <tex> \{a, b , c \} </tex> <tex dpi="130">B_0 = 1</tex>, т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя. Как было обозначено выше, мы ''a'не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них',&nbsp;''. Это означает, что данные разбиения являются идентичными:: <tex> \{ b''\} , \{ a , c \} </tex>: <tex>\{ a, c\}, \{ b \} </tex>: <tex>\{ b \},&nbsp;''\{ c'', a \} может быть разделено 5 различным способами</tex>:<tex>\{ c, a \}, \{ b \} </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>30 </tex> является произведением <tex>3 </tex> простых чисел <tex>2</tex>, <tex>3, and&nbsp;</tex> и <tex>5, </tex> и имеет <tex dpi="130">N=5 </tex> факторизаций:

Числа Белла показывают ''количество схем рифмовки на <tex dpi="130">n</tex>-ой строфыстроках''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества отношение экивалентности на множестве строк в подмножества рифм. Таким образом, <tex>15 </tex> возможных четверостиший схемами рифмовки являются:<tex dpi="130"> \newline{} AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,

====Биномиальные коэффициенты====Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s::<tex dpi = "180150">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 = "180150">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> непустых подмножеств. Michael Spivey==== Доказательство ====Посчитаем количество подмножеств <tex dpi= "150">n<ref/tex>Spivey, Michael Z. (2008)-элементного множества. Нам нужно разбить <tex dpi= "150">n</tex>-элементное множество на <tex dpi= "A generalized recurrence for Bell numbers150" . Journal of Integer Sequences. 11 (2): Article 08.2.5>k</tex> непустых подмножеств, 3где <tex dpi= "150">k</tex> от <tex dpi= "150">1</tex> до <tex dpi= "150">n</tex>. MR 2420912Пусть<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</reftex> получил формулунепустых подмножеств, которая объединяет оба эти суммирования::тогда <tex dpi = "180150">B_C = \bigcup \limits_{k=1}^{n+m} A_k</tex>. <tex dpi = "150">|A_k|=\left\{{n\atop k}\right\}\ { — }\ </tex>по определению, тогда <tex dpi = "150">B_n=|C|= \sum_{k=01}^{n } \ |A_k|=\sum_{jk=01}^m n \left\{{mn\atop jk}\right\} =\sum_{n \choose k=0} j^n \left\{{n-\atop k} B_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 = "180150">B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>

Числа Белла удовлетворяют '''формуле Добинского'''::<tex dpi = "180150">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_n'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.

: <tex dpi = "180150"> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex>

'''Беренд Тасса''' в <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>W</tex> <ref> [[wikipedia:Lambert W function|Функция Ламберта ВтW]]</ref>, данная функция имеет такой же темп роста, как логарифм, как

'''Мозер Л. и ВайманМ.'''<ref>Moser, Leo; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III. </ref> установил установили расширение:

:<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) $$ \newline {} \qquad \text{as }n\to\infty</tex>Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году. ==Получение=====Вычисление с помощью треугольника Пирса=== [[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\}

Было установлено '''де Брайном'''Число Стирлинга второго рода показывает количество способов разбиения множества из <reftex>de Bruijnn</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на непустых подмножеств, Nто есть <tex>n</tex>-ое число Белла.G Заполним таблицу чисел Стирлинга, используя формулу выше. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108Cумма чисел <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</reftex> в 1981 году. |}

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