Числа Белла

Материал из Викиконспекты
Версия от 01:17, 9 декабря 2017; MikeTerentyev (обсуждение | вклад) (Вычисление с помощью треугольника Пирса)
Перейти к: навигация, поиск
Определение:
В комбинаторной математике числа Белла (англ. Bell's numbers) определяют количество возможных способов разбиения множества[1] из [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 элементов

Разбиения множеств могут быть расположены частично-упорядоченном виде[2]. Каждое подмножество длины 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]является свободным от квадратов [3], то [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] (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле[4]. Например, [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] непустых подмножеств. Майкл Спайви[5] получил формулу, которая объединяет оба эти суммирования:

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

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

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

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

[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][9] установлил следующие границы:

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

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

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

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

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