Изменения

|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 (number)|1]], [[2 (number)|2]], [[5 (number)|5]], [[15 (number)|15]], [[52 (number)|52]], [[203 (number)|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:bellXxxCircles.png|right400px|thumb|upright|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно 52 разбиения множества из подмножеств длины n-1.5 элементов]][[File:Order.png|thumb400px|The 52 partitions of a set with 5 elementsborder]]''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'':<tex> \{ a \} , \{ b \} , \{ c \} </tex>: <tex> \{ a \} , \{b, c \} </tex>: <tex> \{ b \} , \{a, c \} </tex>: <tex> \{ c \} , \{ a, b \} </tex>: <subtex>0\{ a, b , c \} </subtex> <tex dpi="130"> является B_0 = 1</tex>, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом, пустое Пустое множество может разбиваться только на само себя. Как было обозначено выше, мы '''не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них'''. Это означает, что данные разбиения являются идентичными::<tex> \{ {''b''\}, \{''a'', ''c''} \}</tex>:<tex>\{ {''a'', ''c''\}, \{''b''} \}</tex>:<tex>\{ {''b''\}, \{''c'', ''a''} \}</tex>:<tex>\{ {''c'', ''a''\}, \{''b''\} }.</tex>  В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются '''упорядоченными числами Белла'''.===Факторизации===Если число ''<tex dpi="130">N'' </tex>является свободным от квадратов<ref>[[wikipedia:Square-free element|Wikipedia {{---}} Cвободные от квадратов числа]]</ref>, то ''B<subtex dpi="130">nB_n</subtex>'' показывает количество различных мультипликативныхразбиений <tex dpi="130">N</tex>.Если число ''<tex dpi="130">N'' </tex> является квадратичным положительным целым числом (является произведением некоторого числа '' <tex dpi="130">n'' </tex> различных простых чисел), то ''B<subtex dpi="130">nB_n</subtex> дает '''число различных мультипликативных разбиений ''' <tex dpi="130">N''</tex>. Это является факторизацией ''<tex dpi="130">N'' </tex> в числа большие, чем <tex>1</tex> (рассматривая две факторизации как идентичные, treating two factorizations as the same if they have the same factors in a different orderесли они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле<ref>{{harvnb|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> и имеет ''B''<subtex dpi="130">3N=5 </subtex> = 5 факторизаций:

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>==== Доказательство ====Докажем, что <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>. ====Связь с числами Стирлинга второго рода====Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]::<texdpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.</tex>, Число где число Стирлинга <texdpi = "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> получил формулу, которая объединяет оба эти суммирования::<texdpi = "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. 

Известно несколько асимптотических формул для чисел Белла. В {{harvtxt|'''Беренд Тасса''' в <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>

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

:<texdpi = "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}

Было установлено де Брайном в 1981 году.===Получение с помощью чисел Стирлинга второго рода===[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']] связаны друг с другом по следующей формуле:<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{Reflist|30emn\atop k-1}\right\}</tex>Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на непустых подмножеств, то есть <tex>n</tex>-ое число Белла.

==References==Заполним таблицу чисел Стирлинга, используя формулу выше.*[Nobuhiro Izumi HuiCумма чисел <tex>n</tex>-Hsiung ой строки будет являться <tex>n</tex>-ым числом Белла.{| border="Acta Applicandae Texematicae1",79–87.Bell numbers, log |-concavity, and log| n \ k ||<tex>0</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||Число Белла |-convexity 2000]*[Aitken A. C. Edinburgh Texematical Notes,18–23 A problem in combinations 1933] |<tex>0</tex>||<tex>1</tex>|| || || |||| |<tex>1</tex>*[H. W.BeckerJohn Riordan "The arithmetic of Bell and Stirling numbers" American Journal of Texematics,1948,385–394]|-*{{cite journal |<tex>1</tex>||<tex>0</tex>|first=E. T.|last=Bell<tex>1</tex>|authorlink=Eric Temple Bell|title= Exponential polynomials|journal=Annals of Texematics|volume=35|year=1934|pages=258–277|ref=harv|jstor=1968431|doi=10.2307<tex>1</1968431}}.tex> |-*{{cite journal |<tex>2</tex>||<tex> 0</tex>|first=E. T.|last=Bell<tex>1</tex> |authorlink=Eric Temple Bell|title= The iterated exponential integers<tex>1</tex> |journal=Annals of Texematics|volume=39|year=1938|pages=539–557|ref=harv|jstor=1968633|doi=10.2307<tex>2</1968633}}.tex> |-*[http: |<tex>3</tex>||<tex>0</www.tex.ucsd.edu>|| <tex>1</tex>|| <tex>3</~ebendertex>|| <tex>1</CombTexttex>|||| |<tex>5</chtex>|-11.pdf Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006]* [[wikipedia:com:Bells numbers |<tex>4</tex>||<tex>0</tex>|| <tex>1</tex> || <tex>7</tex> || <tex>6</tex> || <tex>1</tex> ||<tex>15</tex> | Bells numbers]]}

==External linksСм.также ==* {{Cite web|author=Robert Dickau|url=http://texforum.org/advanced/robertd/bell.html|title=Diagrams of Bell numbers}}[[Числа Стирлинга второго рода]]* {{TexWorld|urlname=BellNumber|title=Bell Number}}[[Числа Стирлинга первого рода]]* {{Cite web|author=Gottfried Helms|url=http://go.helms-net.de/tex/binomial/04_5_SummingBellStirling.pdf|title=Further properties & Generalization of Bell-Numbers}}[[Числа Эйлера I и II рода]]