Числа Белла — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
===Разделение набора===
 
===Разделение набора===
 
[[File:bell.pnghumb|right|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины n-1.]]
 
[[File:bell.pnghumb|right|Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины n-1.]]
−
[[File:Set partitions 5; xxxCircles.png|thumb|The 52 partitions of a set with 5 elements]]
+
[[File:Set partitions 5; Order.png|thumb|The 52 partitions of a set with 5 elements]]
 
''B''<sub>''n''</sub> количество разбиений множества размера ''n''. Разбиение множества ''S'' определяется как совокупность непустых, попарно непересекающихся подмножеств множества ''S''. Например, ''B''<sub>3</sub>&nbsp;=&nbsp;5, потому что множество, состоящее их 3 элементов  {''a'',&nbsp;''b'',&nbsp;''c''} может быть разделено 5 различным способами:
 
''B''<sub>''n''</sub> количество разбиений множества размера ''n''. Разбиение множества ''S'' определяется как совокупность непустых, попарно непересекающихся подмножеств множества ''S''. Например, ''B''<sub>3</sub>&nbsp;=&nbsp;5, потому что множество, состоящее их 3 элементов  {''a'',&nbsp;''b'',&nbsp;''c''} может быть разделено 5 различным способами:
  

Версия 14:10, 8 октября 2017


Шаблон:Числа Белла Числа Белла начинаются с B0 = B1 = 1 и образуют последовательность :

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ...

n- элемент чисел Белла, Bn, показывает количество различных способов разбиения множества, которое имеет не менее n элементов, т.е. количеству отношений эквивалентности в нем. Вне математики, похожие числа показывают количество различных схем рифмовки для n-й строфы стихотворения.

Подсчет

Разделение набора

Разбиения множеств могут быть расположены частично-упорядоченном виде. Каждое подмножество длины n использует одно из подмножеств длины n-1.
Файл:Set partitions 5; Order.png
The 52 partitions of a set with 5 elements

Bn количество разбиений множества размера n. Разбиение множества S определяется как совокупность непустых, попарно непересекающихся подмножеств множества S. Например, B3 = 5, потому что множество, состоящее их 3 элементов {a, b, c} может быть разделено 5 различным способами:

{ {a}, {b}, {c} }
{ {a}, {b, c} }
{ {b}, {a, c} }
{ {c}, {a, b} }
{ {a, b, c} }.

B0 является 1, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом, пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными:

{ {b}, {a, c} }
{ {a, c}, {b} }
{ {b}, {c, a} }
{ {c, a}, {b} }.

В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются упорядоченными числами Белла.

Факторизации

Если число N является свободным от квадратов, то Bn показывает количество различных мультипликативных Если число N является квадратичным положительным целым числом (является произведением некоторого числа n различных простых чисел), то Bn дает число различных мультипликативных разбиений N. Это является факторизацией N в числа большие, чем 1, treating two factorizations as the same if they have the same factors in a different order.[1] Например, 30 является произведением 3 простых чисел 2, 3, and 5, и имеет B3 = 5 факторизаций:

[math]30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5[/math]

Схемы рифмовки

Числа Белла показывают количество схем рифмовки n-строфы. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, 15 возможных четверостиший схемами рифмовки являются: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.Шаблон:Sfn

Вычисление с помощью треугольника Пирса

Шаблон:Main article

Треугольное множество, правая диагональная последовательность которого состоит из чисел Белла

Числа Белла могут быть с легкостью вычислены с помощью треугольника Белла, который также называют массивом Айткена или треугольником Пирса.

  1. Начнем с единицы. Помещаем ее в верхнюю строку. ([math] x_{0,1} = 1 [/math])
  2. Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ([math]x_{i,1} \leftarrow x_{i-1, r}[/math] где r последний элемент (i-1)-й строки)
  3. Определим остальные элементы строки [math]( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )[/math]
  4. Повторяем пункт 3, пока [math] j = r + 1 [/math])
  5. Крайнее левое число данной строки является числом Белла для этой строки. ([math]B_i \leftarrow x_{i,1}[/math])

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:

[math]B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.[/math]

Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода:

[math]B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.[/math]

Число Стирлинга [math]\left\{{n\atop k}\right\}[/math] является количеством способов разбиения набора элементов n в ровно k непустых подмножеств. Michael Spivey получил формулу, которая объединяет оба эти суммирования:

[math]B_{n+m} = \sum_{k=0}^n \sum_{j=0}^m \left\{{m\atop j}\right\} {n \choose k} j^{n-k} B_k.[/math]

Производная функция

Экспоненциальной производящей функцией числе Белла является:

[math]B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.[/math]

Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.

Моменты распределения вероятностей

Числа Белла удовлетворяют формуле ДобинскогоШаблон:SfnШаблон:SfnШаблон:Sfn

[math]B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.[/math]

Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты. Это позволяет интерпретировать Bn как n-й момент Пуассоновского распределения с ожидаемым значением 1.

Интегральное представление

Применение интегральной формулы Коши для экспоненциальной производящей функции дает комплексное интегральное представление:

[math] B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. [/math]

Log-concavity

Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, Bn/n!, дает логарифмически выпуклую последовательность.sequence.

Темпы роста

Известно несколько асимптотических формул для чисел Белла. В Шаблон:Harvtxt были установлены следующие границы:

[math] B_n \lt \left( \frac{0.792 n}{\ln( n+1)} \right)^n [/math] для всех положительных чисел [math]n[/math];

кроме того, если [math] \varepsilon\gt 0 [/math] затем для всех [math] n \gt n_0(\varepsilon) [/math],

[math] B_n \lt \left( \frac{e^{-0.6 + \varepsilon} n}{\ln(n+1)}\right)^n [/math]

где [math] ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ [/math] и [math] ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,. [/math] Числа Белла могут быть аппроксимированы с помощью функции Ламберта Вт, данная функция имеет такой же темп роста, как логарифм, как

[math]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). [/math]

Moser Wyman установил расширение:

[math]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)[/math]

Асимптотическое выражение

[math] \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} [/math]

Было установлено де Брайном в 1981 году. Шаблон:Reflist

References

Шаблон:Refbegin

Шаблон:Refend

External links

  • ↑ Шаблон:Harvnb credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
    • Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Числа_Белла&oldid=62000»