Изменения

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

Числа Белла начинаются с <tex dpi="130">B_0=B_1=1</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-х годах.

===Разделение набора===Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины <tex dpi="130">n</tex> использует одно из подмножеств длины <tex dpi="130">n-1</tex>.[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]][[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>является свободным от квадратов <ref>[[wikipedia:Square-free element|'''свободным Wikipedia {{---}} Cвободные от квадратов'''числа]]</ref>, то <tex dpi="130">B_n</tex> показывает количество различных мультипликативных разбиений <tex dpi="130">N</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"> AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD</tex>. ==Вычисление с помощью треугольника Пирса== [[Image:BellNumberAnimated.gif|right|thumb| Треугольное множество, правая диагональная последовательность которого состоит из чисел Белла]]Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''.# Начнем с единицы. Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>)# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, r}</tex> где ''r'' последний элемент (''i''-1)-й строки)# Определим остальные элементы строки <tex>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )</tex> # Повторяем пункт 3, пока <tex> j = r + 1 </tex>)# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>)Первые пять строк треугольника, построенного по этим правилам:{| border="1" |- |1|| || || || |- |1|| 2|| || || |- | 2||3 ||5 || || |- |5|| 7|| 10|| 15|||- |15|| 20 || 27 || 37 || 52 |}

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

:<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 Spivey 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">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>. ===Производящая функция===Экспоненциальной [[wikipedia:ru:Moment-generating functionпроизводящая функция|производящей функцией]] числе чисел Белла является:

Числа Белла удовлетворяют '''формуле Добинского'''::<tex dpi = "180150">B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</tex>Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора<ref>[[wikipedia:Taylor series|'''ряд Ряд Тейлора''']](''Taylor series'') </ref> для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты. <ref>Flajolet & Sedgewick (2009)</ref>.Это позволяет интерпретировать ''B_n'' как <tex dpi="130">n</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.

Применение интегральной формулы Коши <ref>[[wikipedia:Cauchy's integral formula|'''формулы Формула Коши''']](''Cauchy's integral formula'') </ref> для экспоненциальной производящей функции дает комплексное интегральное представление:: <tex dpi = "180150"> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex>

Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, <tex dpi = "150170">\frac{B_n}{n!}</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 dpi = "150"> ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.

Числа Белла могут быть аппроксимированы с помощью функции Ламберта <tex>W</tex> <ref> [[wikipedia:Lambert W function|'''функции Функция Ламберта Вт'''W]]</ref>, данная функция имеет такой же темп роста, как логарифм, как

'''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> установили расширение:

:<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\}

Было установлено '''де Брайном''' в 1981 годуЧисло Стирлинга второго рода показывает количество способов разбиения множества из <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> |}

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

* [https://en.wikipedia.org/wiki/Bell_number Wikipedia {{---}}Bell numbers]