288
правок
Изменения
м
{{main article|Partition of a set}}[[Файл:[[Файл:Example.jpg]][[Файл:Example.jpg]]]][[File:Bell numbers subset partial orderbell.svg|thumbpnghumb|right|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины n-1.]][[File:Set partitions 5; circlesxxxCircles.svgpng|thumb|The 52 partitions of a set with 5 elements]]
{{harvtxt|Michael Spivey|2008}} получил формулу, которая объединяет оба эти суммирования:
{{harvtxt|Moser|Wyman|1955}} установил расширение:
Нет описания правки
==Подсчет==
===Разделение набора===
''B''<sub>''n''</sub> количество разбиений множества размера ''n''. Разбиение множества ''S'' определяется как совокупность непустых, попарно непересекающихся подмножеств множества ''S''. Например, ''B''<sub>3</sub> = 5, потому что множество, состоящее их 3 элементов {''a'', ''b'', ''c''} может быть разделено 5 различным способами:
===Формулы суммирования===
Числа Белла удовлетворяют рекуррентному соотношению 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'' непустых подмножеств.
:<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>
Числа Белла удовлетворяют ''формуле Добинского''{{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> ~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>
:<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>
Асимптотическое выражение
