Числа Белла — различия между версиями
(что значит n-я строфа ?) |
|||
(не показано 9 промежуточных версий 2 участников) | |||
Строка 4: | Строка 4: | ||
Числа Белла начинаются с <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>B_3 = 5</tex>, потому что множество, состоящее их <tex>3</tex> элементов <tex> \{ a, b , c \} </tex> может быть разделено <tex>5</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> различными способами: | ||
Строка 36: | Строка 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>. | ||
Строка 85: | Строка 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: | Строка 98: | ||
# Начнем с единицы. Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>) | # Начнем с единицы. Помещаем ее в верхнюю строку. (<tex> x_{0,1} = 1 </tex>) | ||
# Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<tex>x_{i,1} \leftarrow x_{i-1, i}</tex>) | # Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. (<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 = | + | # Заполняем строчку <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>) | ||
Первые пять строк треугольника, построенного по этим правилам: | Первые пять строк треугольника, построенного по этим правилам: |
Версия 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