288
правок
Изменения
Новая страница: « {{Числа Белла |neat=1 |definition = В комбинаторной математике числа Белла показывают количество...»
{{Числа Белла
|neat=1
|definition = В комбинаторной математике числа Белла показывают количество возможных способов разбиения множества из ''n''элементов на непустые подмножества. Эти числа изучались математиками с 17-го века. Их корни уходят в средневековую Японию. Названы в честь Эрика Темпла Белла, который описал их в 1930-х годах.
}}
Числа Белла начинаются с ''B''<sub>0</sub> = ''B''<sub>1</sub> = 1 и образуют последовательность :
: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, ... {{OEIS|id=A000110}}.
''n''- элемент чисел Белла, ''B<sub>n</sub>'', показывает количество различных способов разбиения множества, которое имеет не менее ''n'' элементов, т.е. количеству [[отношений эквивалентности]] в нем.
Вне математики, похожие числа показывают количество различных схем рифмовки для ''n''-й строфы стихотворения.
==Подсчет==
===Разделение набора===
{{main article|Partition of a set}}
[[File:Bell numbers subset partial order.svg|thumb|right|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины n-1.]]
[[File:Set partitions 5; circles.svg|thumb|The 52 partitions of a set with 5 elements]]
''B''<sub>''n''</sub> количество разбиений множества размера ''n''. Разбиение множества ''S'' определяется как совокупность непустых, попарно непересекающихся подмножеств множества ''S''. Например, ''B''<sub>3</sub> = 5, потому что множество, состоящее их 3 элементов {''a'', ''b'', ''c''} может быть разделено 5 различным способами:
:{ {''a''}, {''b''}, {''c''} }
:{ {''a''}, {''b'', ''c''} }
:{ {''b''}, {''a'', ''c''} }
:{ {''c''}, {''a'', ''b''} }
:{ {''a'', ''b'', ''c''} }.
''B''<sub>0</sub> является 1, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом, пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными:
:{ {''b''}, {''a'', ''c''} }
:{ {''a'', ''c''}, {''b''} }
:{ {''b''}, {''c'', ''a''} }
:{ {''c'', ''a''}, {''b''} }.
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются упорядоченными числами Белла.
===Факторизации===
Если число ''N'' является свободным от квадратов, то ''B<sub>n</sub>'' показывает количество различных мультипликативных
Если число ''N'' является квадратичным положительным целым числом (является произведением некоторого числа '' n'' различных простых чисел), то ''B<sub>n</sub> дает число различных мультипликативных разбиений ''N''. Это является факторизацией ''N'' в числа большие, чем 1, 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> Например, 30 является произведением 3 простых чисел 2, 3, and 5, и имеет ''B''<sub>3</sub> = 5 факторизаций:
:<tex>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</tex>
===Схемы рифмовки===
Числа Белла показывают количество схем рифмовки ''n''-строфы. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, 15 возможных четверостиший схемами рифмовки являются: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.{{sfn|Gardner|1978}}
==Вычисление с помощью треугольника Пирса==
{{main article|Треугольник Пирса}}
[[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>)
Here are the first five rows of the triangle constructed by these rules:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
==Свойства==
===Формулы суммирования===
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:{{sfn|Wilf|1994|p=23}}
:<tex>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'' непустых подмножеств.
{{harvtxt|Spivey|2008}} получил формулу, которая объединяет оба эти суммирования:
:<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>
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
===Моменты распределения вероятностей===
Числа Белла удовлетворяют [[формуле Добинского]]{{sfn|Dobiński|1877}}{{sfn|Rota|1964}}{{sfn|Bender|Williamson|2006}}
:<tex>B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</tex>
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты. {{sfn|Flajolet|Sedgewick|2009}}
Это позволяет интерпретировать ''B<sub>n</sub>'' как ''n''-й момент Пуассоновского распределения с ожидаемым значением 1.
===Интегральное представление===
Применение интегральной формулы Коши для экспоненциальной производящей функции дает комплексное интегральное представление:
: <tex> 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.{{sfn|Engel|1994}}{{sfn|Canfield|1995}}{{sfn|Asai|Kubo|Kuo|2000}}
===Темпы роста===
Известно несколько асимптотических формул для чисел Белла. В {{harvtxt|Berend|Tassa|2010}} были установлены следующие границы:
:<tex> 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> 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> ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,.
</tex>
Числа Белла могут быть аппроксимированы с помощью функции Ламберта Вт, данная функция имеет такой же темп роста, как логарифм, как{{sfnp|Lovász|1993}}
:<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>
{{harvtxt|Moser|Wyman|1955}} установил расширение:
:<tex>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>
Асимптотическое выражение
:<tex>
\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}
</tex>
Было установлено де Брайном в 1981 году.
