Числа Белла — различия между версиями
(→Получение с помощью чисел Стирлинга второго рода) |
(что значит n-я строфа ?) |
||
(не показаны 33 промежуточные версии 3 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
− | |definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') определяют количество возможных способов | + | |definition = В комбинаторной математике '''числа Белла''' (''англ. Bell's numbers'') определяют количество возможных способов [[Комбинаторные объекты#Разбиение на подмножества|разбиения множества]] из <tex>n</tex> элементов на подмножества. |
}} | }} | ||
Числа Белла начинаются с <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность: | Числа Белла начинаются с <tex dpi="130">B_0=B_1=1</tex> и образуют последовательность: | ||
:<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, | :<tex dpi="130">1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, | ||
− | + | 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057\dots | |
</tex> | </tex> | ||
− | <tex dpi="130">n</tex>-й элемент чисел Белла, <tex dpi="130">B_n</tex>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем. | + | <tex dpi="130">n</tex>-й элемент множества чисел Белла, <tex dpi="130">B_n</tex>, определяет количество различных способов разбиения множества, то есть количество [[Отношение эквивалентности|отношений эквивалентности]] в нем. |
==Подсчет== | ==Подсчет== | ||
− | |||
[[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]] | [[File:XxxCircles.png|400px|thumb|upright|52 разбиения множества из 5 элементов]] | ||
− | [[File:Order.png|400px|border | + | [[File:Order.png|400px|border]] |
− | Разбиение множества <tex dpi="130">S</tex> определяется как совокупность ''' | + | Разбиение множества <tex dpi="130">S</tex> определяется как совокупность '''попарно непересекающихся подмножеств множества''' <tex dpi="130">S</tex>. Например, <tex>B_3 = 5</tex>, потому что множество, состоящее их <tex>3</tex> элементов <tex> \{ a, b , c \} </tex> может быть разделено <tex>5</tex> различными способами: |
:<tex> \{ a \} , \{ b \} , \{ c \} </tex> | :<tex> \{ a \} , \{ b \} , \{ c \} </tex> | ||
Строка 37: | Строка 36: | ||
==Схемы рифмовки== | ==Схемы рифмовки== | ||
− | Числа Белла показывают ''количество схем рифмовки <tex dpi="130">n</tex> | + | Числа Белла показывают ''количество схем рифмовки на <tex dpi="130">n</tex> строках''. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как отношение экивалентности на множестве строк. Таким образом, <tex>15</tex> возможных четверостиший схемами рифмовки являются: |
− | <tex dpi="130"> | + | <tex dpi="130"> AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, |
ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD</tex>. | ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD</tex>. | ||
Строка 47: | Строка 46: | ||
:<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex> | :<tex dpi = "150">B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</tex> | ||
Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]: | Другая формула суммирования представляет каждое число Белла как сумму [[Числа Стирлинга второго рода|'''чисел Стирлинга второго рода''']]: | ||
− | :<tex dpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\} | + | :<tex dpi = "150">B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}</tex>, |
− | + | где число Стирлинга <tex dpi = "150">\left\{{n\atop k}\right\}</tex> является количеством способов разбиения набора элементов <tex dpi = "150">n</tex> в ровно <tex dpi="150">k</tex> непустых подмножеств. | |
Майкл Спайви<ref>Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.</ref> получил формулу, которая объединяет оба эти суммирования: | Майкл Спайви<ref>Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.</ref> получил формулу, которая объединяет оба эти суммирования: | ||
:<tex dpi = "150">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> | :<tex dpi = "150">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> | ||
Строка 86: | Строка 85: | ||
:<tex dpi = "150">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> | :<tex dpi = "150">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> | ||
Асимптотическое выражение | Асимптотическое выражение | ||
− | :<tex dpi = "150"> | + | :<tex dpi = "150"> |
− | + | \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 | |
</tex> | </tex> | ||
Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году. | Было установлено '''де Брайном'''<ref>de Bruijn, N.G. (1981). Asymptotic methods in analysis (3rd ed.). Dover. p. 108.</ref> в <tex>1981</tex> году. | ||
Строка 98: | Строка 97: | ||
Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''. | Числа Белла могут быть с легкостью '''вычислены''' с помощью '''треугольника Белла''', который также называют '''массивом Айткена''' или '''треугольником Пирса'''. | ||
# Начнем с единицы. Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>) | # Начнем с единицы. Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>) | ||
− | # Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, | + | # Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</tex>) |
− | + | # Заполняем строчку <tex>i</tex> по формуле <tex> ( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1}) </tex> , начиная с <tex> j = 2 </tex>, пока <tex>j \leqslant i + 1 </tex>. | |
− | |||
# Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>) | # Крайнее левое число данной строки является числом Белла для этой строки. (<tex>B_i \leftarrow x_{i,1}</tex>) | ||
Первые пять строк треугольника, построенного по этим правилам: | Первые пять строк треугольника, построенного по этим правилам: | ||
Строка 117: | Строка 115: | ||
===Получение с помощью чисел Стирлинга второго рода=== | ===Получение с помощью чисел Стирлинга второго рода=== | ||
− | [[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']] | + | [[Числа Стирлинга второго рода|'''Числа Стирлинга второго рода''']] связаны друг с другом по следующей формуле: |
<tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} | <tex dpi="150">\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\} | ||
</tex> | </tex> | ||
− | |||
Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на непустых подмножеств, то есть <tex>n</tex>-ое число Белла. | Число Стирлинга второго рода показывает количество способов разбиения множества из <tex>n</tex> элементов на <tex>k</tex> непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую <tex>n</tex>, то получим количество способов разбиения множества из <tex>n</tex> элементов на непустых подмножеств, то есть <tex>n</tex>-ое число Белла. | ||
− | + | ||
+ | Заполним таблицу чисел Стирлинга, используя формулу выше. | ||
+ | Cумма чисел <tex>n</tex>-ой строки будет являться <tex>n</tex>-ым числом Белла. | ||
{| border="1" | {| border="1" | ||
|- | |- |
Версия 18:11, 28 сентября 2020
Определение: |
В комбинаторной математике числа Белла (англ. Bell's numbers) определяют количество возможных способов разбиения множества из элементов на подмножества. |
Числа Белла начинаются с
и образуют последовательность:отношений эквивалентности в нем.
-й элемент множества чисел Белла, , определяет количество различных способов разбиения множества, то есть количествоСодержание
Подсчет
Разбиение множества
определяется как совокупность попарно непересекающихся подмножеств множества . Например, , потому что множество, состоящее их элементов может быть разделено различными способами:, т.к. существует только одно возможное разбиение пустого множества. Пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них. Это означает, что данные разбиения являются идентичными:
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются упорядоченными числами Белла.
Факторизации
Если число [1], то показывает количество различных мультипликативных разбиений . Если является квадратичным положительным целым числом (является произведением некоторого числа различных простых чисел), то дает число различных мультипликативных разбиений . Это является факторизацией в числа большие, чем (рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле[2]. Например, является произведением простых чисел , и и имеет факторизаций:
является свободным от квадратовСхемы рифмовки
Числа Белла показывают количество схем рифмовки на
строках. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как отношение экивалентности на множестве строк. Таким образом, возможных четверостиший схемами рифмовки являются: .Свойства
Формулы суммирования
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:
Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода:
- ,
где число Стирлинга [3] получил формулу, которая объединяет оба эти суммирования:
является количеством способов разбиения набора элементов в ровно непустых подмножеств. Майкл СпайвиПроизводящая функция
Экспоненциальной производящей функцией чисел Белла является:
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
Моменты распределения вероятностей
Числа Белла удовлетворяют формуле Добинского:
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора[4] для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты.[5]. Это позволяет интерпретировать Bn как -й момент Пуассоновского распределения с ожидаемым значением .
Интегральное представление
Применение интегральной формулы Коши [6] для экспоненциальной производящей функции дает комплексное интегральное представление:
Логарифмическая вогнутость
Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал,
, дает логарифмически выпуклую последовательность.Темпы роста
Известно несколько асимптотических формул для чисел Белла. Беренд Тасса в [7] установлил следующие границы:
-м- для всех положительных чисел ;
кроме того, если
затем для всех ,где [8], данная функция имеет такой же темп роста, как логарифм, как
и Числа Белла могут быть аппроксимированы с помощью функции ЛамбертаМозер Л. и Вайман М.[9] установили расширение:
Асимптотическое выражение
Было установлено де Брайном[10] в году.
Получение
Вычисление с помощью треугольника Пирса
Числа Белла могут быть с легкостью вычислены с помощью треугольника Белла, который также называют массивом Айткена или треугольником Пирса.
- Начнем с единицы. Помещаем ее в верхнюю строку. ( )
- Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ( )
- Заполняем строчку по формуле , начиная с , пока .
- Крайнее левое число данной строки является числом Белла для этой строки. ( )
Первые пять строк треугольника, построенного по этим правилам:
Получение с помощью чисел Стирлинга второго рода
Числа Стирлинга второго рода связаны друг с другом по следующей формуле: Число Стирлинга второго рода показывает количество способов разбиения множества из элементов на непустых подмножеств. Если сложить все числа Стирлинга второго рода, имеющих одинаковую , то получим количество способов разбиения множества из элементов на непустых подмножеств, то есть -ое число Белла.
Заполним таблицу чисел Стирлинга, используя формулу выше. Cумма чисел
-ой строки будет являться -ым числом Белла.n \ k | Число Белла | |||||
См.также
Примeчания
- ↑ Wikipedia — Cвободные от квадратов числа
- ↑ Williams 1945 credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
- ↑ Spivey, Michael Z. (2008). "A generalized recurrence for Bell numbers" . Journal of Integer Sequences. 11 (2): Article 08.2.5, 3. MR 2420912.
- ↑ Ряд Тейлора
- ↑ Flajolet & Sedgewick (2009)
- ↑ Формула Коши
- ↑ 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.
- ↑ Функция Ламберта W
- ↑ Moser, Leo; Wyman, Max (1955). "An asymptotic formula for the Bell numbers". Transactions of the Royal Society of Canada, Section III.
- ↑ 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