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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Получение с помощью чисел Стирлинга второго рода)
Строка 38: Строка 38:
 
<tex dpi="130"> \newline{} AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
 
<tex dpi="130"> \newline{} AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC,
 
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,  ABCD</tex>.
 
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC,  ABCD</tex>.
−
==Получение==
 
−
===Вычисление с помощью треугольника Пирса===
 
−
 
−
[[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>)
 
−
Первые пять строк треугольника, построенного по этим правилам:
 
−
{| border="1"
 
−
|-
 
−
|1|| || || ||
 
−
|-
 
−
|1|| 2|| || ||
 
−
|-
 
−
| 2||3 ||5 || ||
 
−
|-
 
−
|5||  7||  10||  15||
 
−
|-
 
−
|15||  20 || 27 || 37 || 52
 
−
|}
 
−
===Получение с помощью чисел Стирлинга второго рода===
 
−
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']]: связаны друг с другом по следующей формуле:
 
−
<tex dpi="180">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 
−
</tex>
 
−
Заполним таблицу [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']], используя данную формулу.
 
−
Очевидно,что сумма чисел <tex>n</tex>-столбца будет являться  <tex>n-ым</tex> числом Белла.
 
−
{| border="1"
 
−
|-
 
−
| n \ k ||0||1||2||3||4||Число Белла
 
−
|-
 
−
|0||1|| || || |||| |1
 
−
|-
 
−
|1||0|| 1|| || |||| |1
 
−
|-
 
−
|2|| 0||1 ||1 || || |||2
 
−
|-
 
−
|3||0||  1||  3||  1|||| |5
 
−
|-
 
−
|4||0||  1 || 7 || 6 || 1 ||15
 
−
|}
 
  
 
==Свойства==
 
==Свойства==
Строка 131: Строка 88:
 
</tex>
 
</tex>
 
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в 1981 году.
 
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в 1981 году.
 +
==Получение==
 +
===Вычисление с помощью треугольника Пирса===
  
 +
[[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>)
 +
Первые пять строк треугольника, построенного по этим правилам:
 +
{| border="1"
 +
|-
 +
|1|| || || ||
 +
|-
 +
|1|| 2|| || ||
 +
|-
 +
| 2||3 ||5 || ||
 +
|-
 +
|5||  7||  10||  15||
 +
|-
 +
|15||  20 || 27 || 37 || 52
 +
|}
 +
===Получение с помощью чисел Стирлинга второго рода===
 +
[[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']]: связаны друг с другом по следующей формуле:
 +
<tex dpi="180">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}
 +
</tex>
 +
Заполним таблицу [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']], используя данную формулу.
 +
Очевидно,что сумма чисел <tex>n</tex>-столбца будет являться  <tex>n-ым</tex> числом Белла.
 +
{| border="1"
 +
|-
 +
| n \ k ||0||1||2||3||4||Число Белла
 +
|-
 +
|0||1|| || || |||| |1
 +
|-
 +
|1||0|| 1|| || |||| |1
 +
|-
 +
|2|| 0||1 ||1 || || |||2
 +
|-
 +
|3||0||  1||  3||  1|||| |5
 +
|-
 +
|4||0||  1 || 7 || 6 || 1 ||15
 +
|}
 
== См.также ==
 
== См.также ==
 
*[[Числа Стирлинга второго рода]]
 
*[[Числа Стирлинга второго рода]]

Версия 18:55, 1 декабря 2017

Определение:
В комбинаторной математике числа Белла (англ. Bell's numbers) показывают количество возможных способов разбиения множества из n элементов на непустые подмножества.

Числа Белла начинаются с [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, ... [/math]

[math]n[/math]- элемент чисел Белла, [math]B_n[/math], показывает количество различных способов разбиения множества, то есть. количество отношений эквивалентности в нем. Вне математики, похожие числа показывают количество различных схем рифмовки для [math]n[/math]-й строфы стихотворения. Эти числа изучались математиками с 17-го века, их корни уходят в средневековую Японию. Названы в честь Эрика Темпла Белла, который описал их в 1930-х годах.

Подсчет

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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], дает логарифмически выпуклую последовательность.

Темпы роста

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

[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] Числа Белла могут быть аппроксимированы с помощью функции Ламберта Вт [8], данная функция имеет такой же темп роста, как логарифм, как

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

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

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

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

Получение

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

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

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

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

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

1
1 2
2 3 5
5 7 10 15
15 20 27 37 52

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

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

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

См.также

Примeчания

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