Числа Белла — различия между версиями
(→Примeчания) |
(→Log-concavity) |
||
Строка 77: | Строка 77: | ||
: <tex> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex> | : <tex> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </tex> | ||
− | === | + | ===Логарифмическая вогнутость=== |
− | Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, <tex>\frac{B_n}{n!}</tex>, дает логарифмически выпуклую последовательность | + | Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, <tex>\frac{B_n}{n!}</tex>, дает логарифмически выпуклую последовательность. |
===Темпы роста=== | ===Темпы роста=== |
Версия 16:08, 8 октября 2017
Определение: |
В комбинаторной математике числа Белла показывают количество возможных способов разбиения множества из nэлементов на непустые подмножества. Эти числа изучались математиками с 17-го века. Их корни уходят в средневековую Японию. Названы в честь Эрика Темпла Белла, который описал их в 1930-х годах. |
Числа Белла начинаются с B0 = B1 = 1 и образуют последовательность :
- 1, 1,2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ...
n- элемент чисел Белла, Bn, показывает количество различных способов разбиения множества, которое имеет не менее n элементов, т.е. количеству отношений эквивалентности в нем. Вне математики, похожие числа показывают количество различных схем рифмовки для n-й строфы стихотворения.
Подсчет
Разделение набора
Bn количество разбиений множества размера n. Разбиение множества S определяется как совокупность непустых, попарно непересекающихся подмножеств множества S . Например, B3 = 5, потому что множество, состоящее их 3 элементов {a, b, c} может быть разделено 5 различным способами:
- { {a}, {b}, {c} }
- { {a}, {b, c} }
- { {b}, {a, c} }
- { {c}, {a, b} }
- { {a, b, c} }.
B0 является 1, т.к. существует только одно возможное разбиение пустого множества. Каждый элемент пустого множества является непустым множеством и их объединение является пустым множеством. Таким образом, пустое множество может разбиваться только на само себя. Как было обозначено выше, мы не рассматриваем ни порядок подмножеств, ни порядок элементов в каждом их них . Это означает, что данные разбиения являются идентичными:
- { {b}, {a, c} }
- { {a, c}, {b} }
- { {b}, {c, a} }
- { {c, a}, {b} }.
В противном случае, если различные упорядочивания множеств считаются различными разбиениями, тогда количество таких упорядоченных разбиений называются упорядоченными числами Белла.
Факторизации
Если число N является свободным от квадратов, то Bn показывает количество различных мультипликативных Если число N является квадратичным положительным целым числом (является произведением некоторого числа n различных простых чисел), то Bn дает число различных мультипликативных разбиений N . Это является факторизацией N в числа большие, чем 1(рассматривая две факторизации как идентичные, если они имеют одинаковые факторы в другом порядке.) подтверждает это наблюдение Сильвио Минетоле(Principii di Analisi Combinatoria, 1909).</ref> Например, 30 является произведением 3 простых чисел 2, 3, and 5, и имеет B3 = 5 факторизаций:
Схемы рифмовки
Числа Белла показывают количество схем рифмовки n-строфы. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, 15 возможных четверостиший схемами рифмовки являются: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.
Вычисление с помощью треугольника Пирса
Числа Белла могут быть с легкостью вычислены с помощью треугольника Белла, который также называют массивом Айткена или треугольником Пирса.
- Начнем с единицы. Помещаем ее в верхнюю строку. ( )
- Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ( где r последний элемент (i-1)-й строки)
- Определим остальные элементы строки
- Повторяем пункт 3, пока )
- Крайнее левое число данной строки является числом Белла для этой строки. ( )
Первые пять строк треугольника, построенного по этим правилам:
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52
Свойства
Формулы суммирования
Числа Белла удовлетворяют рекуррентному соотношению c участием биномиальных коэффициентов s:
Другая формула суммирования представляет каждое число Белла как сумму чисел Стирлинга второго рода:
Число Стирлинга
является количеством способов разбиения набора элементов n в ровно k непустых подмножеств. Michael Spivey получил формулу, которая объединяет оба эти суммирования:Производная функция
Экспоненциальной производящей функцией числе Белла является:
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
Моменты распределения вероятностей
Числа Белла удовлетворяют формуле Добинского
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты. Это позволяет интерпретировать Bn как n-й момент Пуассоновского распределения с ожидаемым значением 1.
Интегральное представление
Применение интегральной формулы Коши для экспоненциальной производящей функции дает комплексное интегральное представление:
Логарифмическая вогнутость
Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал,
, дает логарифмически выпуклую последовательность.Темпы роста
Известно несколько асимптотических формул для чисел Белла. Беренд Тасса в 2010-м установлил следующие границы:
- для всех положительных чисел ;
кроме того, если
затем для всех ,где функции Ламберта Вт, данная функция имеет такой же темп роста, как логарифм, как
и Числа Белла могут быть аппроксимированы с помощьюMoser Wyman установил расширение:
Асимптотическое выражение
Было установлено де Брайном в 1981 году.
Литература
- [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]
- Bender Edward A.Williamson, S. Gill, Set Partitions, 319–320, 2006
- Bell numbers
Примeчания
--MikeTerentyev 16:07, 8 октября 2017 (MSK)MikeTerentyev