Изменения

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

Числа Белла начинаются с ''B''<sub>0</subtex dpi="130"> B_0=B_1= ''B''<sub>1</subtex> = 1 и образуют последовательность ::<tex dpi="130">1, 1,2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... \dots </tex>''<tex dpi="130">n''</tex>- й элемент множества чисел Белла, ''B<subtex dpi="130">nB_n</subtex>'', показывает определяет количество различных способов разбиения множества, которое имеет не менее ''n'' элементов, т.е. количеству то есть количество [[Отношение эквивалентности|отношений эквивалентности|Определение_отношение_эквивалентности]] в нем.Вне математики, похожие числа показывают количество различных схем рифмовки для ''n''-й строфы стихотворения.

===Разделение набора===[[File:OrderXxxCircles.png|400px|thumb|upright|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно 52 разбиения множества из подмножеств длины n-1.5 элементов]][[File:XxxCirclesOrder.png|thumb|upright400px|52 разбиения множества из 5 элементовborder]]''B''_''n'' количество разбиений множества размера ''n''. Разбиение множества ''S'' определяется как совокупность непустых, попарно непересекающихся подмножеств множества ''S''. Например, ''B''₃&nbsp;=&nbsp;5, потому что множество, состоящее их 3 элементов {''a'',&nbsp;''b'',&nbsp;''c''} может быть разделено 5 различным способами:

:{ {Разбиение множества <tex dpi="130">S</tex> определяется как совокупность ''a''}, {'попарно непересекающихся подмножеств множества'b''}, {''c''} }:{ {''a''}<tex dpi="130">S</tex>. Например, {''b''<tex>B_3 = 5</tex>, ''c''} }:{ {''b''}потому что множество, состоящее их <tex>3</tex> элементов <tex> \{''a'', ''c''} }:{ {''c''}, {''a'', ''b''} }:{ {''a'', ''b'', ''c''\} }.</tex> может быть разделено <tex>5</tex> различными способами:

''B'':<subtex>0</sub> является 1, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом \{ a \} , пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными::{ \{''b''\}, \{''a'', ''c''} \}</tex>:<tex> \{ {''a'', ''c''\}, \{''b''} , c \}</tex>:<tex> \{ {''b''\}, \{''a, c'', ''a''} \}</tex>:<tex> \{ {''c''\} , ''\{ a''}, {''b''\} }.</tex>В противном случае: <tex> \{ a, если различные упорядочивания множеств считаются различными разбиениямиb , тогда количество таких упорядоченных разбиений называются упорядоченными числами Белла.c \} </tex>

<tex dpi="130">B_0 ==Факторизации===Если число ''N'' является свободным от квадратов, то ''B<sub>n1</subtex>'' показывает количество различных мультипликативных, т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя. Если число Как было обозначено выше, мы ''N'не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них' является квадратичным положительным целым числом (является произведением некоторого числа '' n'' различных простых чисел). Это означает, то Bчто данные разбиения являются идентичными:: <subtex>n\{ b \} , \{ a , c \} </subtex>: <tex> дает '''число различных мультипликативных разбиений ''N'' '''. Это является факторизацией ''N'' в числа большие\{ a, чем 1(рассматривая две факторизации как идентичныеc\}, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле''Principii di Analisi Combinatoria'' (1909).\{ b \} </reftex> Например: <tex>\{ b \}, 30 является произведением 3 простых чисел 2\{ c, 3, and&nbsp;5, и имеет ''B''<sub>3a \} </subtex> = 5 факторизаций: :<tex>30 = 2\times 15=3{ c, a \times 10=5\times 6=2}, \times 3{ b \times 5} </tex>

==Факторизации==Если число <tex dpi="130">N</tex>является свободным от квадратов <ref>[[Imagewikipedia:BellNumberAnimated.gifSquare-free element|right|thumb| Треугольное множество, правая диагональная последовательность которого состоит из чисел БеллаWikipedia {{---}} Cвободные от квадратов числа]]Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла'''</ref>, который также называют массивом Айткена или треугольником Пирсато <tex dpi="130">B_n</tex> показывает количество различных мультипликативных разбиений <tex dpi="130">N</tex>.# Начнем с единицы. Если <tex dpi="130">N</tex> является квадратичным положительным целым числом Помещаем ее в верхнюю строку. (является произведением некоторого числа <texdpi="130"> x_{0,1} = 1 n</tex> различных простых чисел)# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (, то <texdpi="130">x_{i,1} \leftarrow x_{i-1, r}B_n</tex> где дает ''r'число различных мультипликативных разбиений' последний элемент (''i''-<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,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )30</tex> # является произведением Повторяем пункт <tex>3</tex> простых чисел <tex>2</tex>, пока <tex> j 3</tex> и <tex>5</tex> и имеет <tex dpi="130">N= r + 1 5 </tex>)факторизаций: # Крайнее левое число данной строки является числом Белла для этой строки. (:<tex>B_i 30 = 2\leftarrow x_{i,1}times 15=3\times 10=5\times 6=2\times 3\times 5</tex>)

Here are the first five rows of the triangle constructed by these rules==Схемы рифмовки==Числа Белла показывают ''количество схем рифмовки на <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, 1 1 2 2 3 5 5 7 10 15 15 20 27 37 52ABCD</tex>.

====Биномиальные коэффициенты====Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s::<texdpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex>Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода:==== Доказательство ====:Докажем, что <texdpi = "150">B_nB_{n+1}=\sum_{k=0}^{n } \left\binom{n}{k} B_{n\atop -k}.</tex> По определению <tex dpi = "150">B_{n}\right{ — }\</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>Число Стирлинга , тогда <texdpi= "150">x_1 \leftcup... \cup x_{k-1}\ {— }\ </tex>подмножество множества <tex dpi="150">[1...n+1]</tex> \atop k}<tex dpi= "150">x_k</tex>. Пусть <tex dpi= "150">|x_k|=i+1</tex>, где <tex dpi= "150">i\rightin [0;n]</tex>, тогда <tex dpi= "150">x_k</tex> можно выбрать <tex dpi= "150">\binom{n}{i}</tex> является количеством способов разбиения набора элементов ''способами, а оставшиеся элементы разбить <tex dpi = "150">B_{n'' в ровно ''k'' непустых подмножеств-i}</tex> способами. Michael Spivey получил формулу, которая объединяет оба эти суммирования::<texdpi = "150">B_{n+m1} = \sum_{k=0}^{n } \binom{n}{k} B_{n-k}=</tex> <tex dpi = "150">\sum_{jk=0}^m \left\{{m\atop jn}\right\binom{n} {n -k} B_{k}=</tex> <tex dpi= "150">\choose sum_{k=0} j^{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">\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>. ===Производящая функция===Экспоненциальной [[производящая функция|производящей функцией числе ]] чисел Белла является::<texdpi = "150">B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</tex>

Числа Белла удовлетворяют '''формуле Добинского''{{sfn|Dobiński|1877}}{{sfn|Rota|1964}}{{sfn|Bender|Williamson|2006}}'::<texdpi = "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_n'' как ''<tex dpi="130">n''</tex>-й момент Пуассоновского распределения с ожидаемым значением <tex>1</tex>.

Применение интегральной формулы Коши <ref>[[wikipedia:Cauchy's integral formula|Формула Коши]]</ref> для экспоненциальной производящей функции дает комплексное интегральное представление:: <texdpi = "150"> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex> ===Log-concavityЛогарифмическая вогнутость===Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, ''B'' <subtex dpi = "170">''\frac{B_n}{n''!}</subtex>/''n''!, дает логарифмически выпуклую последовательность.sequence. 

'''Беренд Тасса''' в <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> установлил следующие границы::<texdpi = "150"> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </tex> для всех положительных чисел <tex>n</tex>;

:<texdpi = "150"> B_n < \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n </tex>

<texdpi = "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>, данная функция имеет такой же темп роста, как логарифм, как:<texdpi = "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> установили расширение::<mathtex 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)</mathtex>

:<mathtex 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) \\& {} \qquad \text{as }n\to\infty\end{align}</mathtex>Было установлено '''де Брайном''' <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> |}

==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 <tex dpi="The arithmetic of Bell and Stirling numbers150" American Journal of Texematics,1948,385–394]>\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}*[E. T.Bell Exponential polynomials,Annals of Texematics,1934, 258–277]</tex>*[E. T.Bell The iterated exponential integers,Annals of Texematics,1938,539–557]*[http:Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</wwwtex> непустых подмножеств.Если сложить все числа Стирлинга второго рода, имеющих одинаковую <tex.ucsd.edu>n</~ebendertex>, то получим количество способов разбиения множества из <tex>n</CombTexttex> элементов на непустых подмножеств, то есть <tex>n</chtex>-11.pdf Bender Edward Aое число Белла.Williamson, S. Gill, Set Partitions, 319–320, 2006]* [[wikipedia:Bell numbers| Bell numbers]]