Числа Белла

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
В комбинаторной математике числа Белла (англ. Bell's numbers) определяют количество возможных способов разбиения множестваРазбиение на подмножества из [math]n[/math] элементов на подмножества.

Числа Белла начинаются с [math]B_0=B_1=1[/math] и образуют последовательность:

[math]1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, \newline{} 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots [/math]

[math]n[/math]-й элемент множества чисел Белла, [math]B_n[/math], определяет количество различных способов разбиения множества, то есть количество отношений эквивалентности в нем.

Подсчет

52 разбиения множества из 5 элементов

Разбиения множеств могут быть расположены частично-упорядоченном виде[1]. Каждое подмножество длины n использует одно из подмножеств длины [math]n-1[/math].

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

[math] \{ a \} , \{ b \} , \{ c \} [/math]
[math] \{ a \} , \{b, c \} [/math]
[math] \{ b \} , \{a, c \} [/math]
[math] \{ c \} , \{ a, b \} [/math]
[math] \{ a, b , c \} [/math]

[math]B_0 = 1[/math], т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными:

[math] \{ b \} , \{ a , c \} [/math]
[math]\{ a, c\}, \{ b \} [/math]
[math]\{ b \}, \{ c, a \} [/math]
[math]\{ c, a \}, \{ b \} [/math]


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

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

Если число [math]N[/math]является свободным от квадратов [2], то [math]B_n[/math] показывает количество различных мультипликативных разбиений [math]N[/math]. Если [math]N[/math] является квадратичным положительным целым числом (является произведением некоторого числа [math]n[/math] различных простых чисел), то [math]B_n[/math] дает число различных мультипликативных разбиений [math]N[/math]. Это является факторизацией [math]N[/math] в числа большие, чем [math]1[/math] (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле[3]. Например, [math]30[/math] является произведением [math]3[/math] простых чисел [math]2[/math], [math]3[/math] и [math]5[/math] и имеет [math]N=5 [/math] факторизаций:

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

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

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

Свойства

Формулы суммирования

Числа Белла удовлетворяют рекуррентному соотношению 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] является количеством способов разбиения набора элементов [math]n[/math] в ровно [math]k[/math] непустых подмножеств. Майкл Спайви[4] получил формулу, которая объединяет оба эти суммирования:

[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]

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

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

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

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

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

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

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

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

Логарифмическая вогнутость

Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, [math]\frac{B_n}{n!}[/math], дает логарифмически выпуклую последовательность.

Темпы роста

Известно несколько асимптотических формул для чисел Белла. Беренд Тасса в [math]2010[/math]-м[8] установлил следующие границы:

[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]W[/math] [9], данная функция имеет такой же темп роста, как логарифм, как

[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]

Мозер Л. и Вайман М.[10] установили расширение:

[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] $$ \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) $$ \newline {} \qquad \text{as }n\to\infty [/math]

Было установлено де Брайном[11] в [math]1981[/math] году.

Получение

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

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

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

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

Первые пять строк треугольника, построенного по этим правилам:

[math]1[/math]
[math]1[/math] [math]2[/math]
[math]2[/math] [math]3[/math] [math]5[/math]
[math]5[/math] [math]7[/math] [math] 10[/math] [math] 15[/math]
[math]15[/math] [math] 20[/math] [math]27[/math] [math]37[/math] [math]52[/math]

Получение с помощью чисел Стирлинга второго рода

Числа Стирлинга второго рода связаны друг с другом по следующей формуле: [math]\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} [/math] Число Стирлинга второго рода показывает количество способов разбиения множества из [math]n[/math] элементов на [math]k[/math] непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую [math]n[/math], то получим количество способов разбиения множества из [math]n[/math] элементов на непустых подмножеств, то есть [math]n[/math]-ое число Белла.

Заполним таблицу чисел Стирлинга, используя формулу выше. Cумма чисел [math]n[/math]-ой строки будет являться [math]n[/math]-ым числом Белла.

n \ k [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] Число Белла
[math]0[/math] [math]1[/math] [math]1[/math]
[math]1[/math] [math]0[/math] [math]1[/math] [math]1[/math]
[math]2[/math] [math] 0[/math] [math]1[/math] [math]1[/math] [math]2[/math]
[math]3[/math] [math]0[/math] [math]1[/math] [math]3[/math] [math]1[/math] [math]5[/math]
[math]4[/math] [math]0[/math] [math]1[/math] [math]7[/math] [math]6[/math] [math]1[/math] [math]15[/math]

См.также

Примeчания

  1. ↑ Частичный порядок
  2. ↑ Wikipedia — Cвободные от квадратов числа
  3. ↑ Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
  4. ↑ Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.
  5. ↑ Ряд Тейлора
  6. ↑ Flajolet & Sedgewick (2009)
  7. ↑ Формула Коши
  8. ↑ 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.
  9. ↑ Функция Ламберта W
  10. ↑ Moser, Leo; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III.
  11. ↑ de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.

Источники информации

  • Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006
  • Wikipedia —Bell numbers
  • 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 "The arithmetic of Bell and Stirling numbers" American Journal of Texematics,1948,385–394
  • E. T.Bell Exponential polynomials,Annals of Texematics,1934, 258–277
  • E. T.Bell The iterated exponential integers,Annals of Texematics,1938,539–557
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Числа_Белла&oldid=62559»