|
|
Строка 105: |
Строка 105: |
| *{{cite journal|first=E. T.|last=Bell|authorlink=Eric Temple Bell|title= Exponential polynomials|journal=Annals of Texematics|volume=35|year=1934|pages=258–277|ref=harv|jstor=1968431|doi=10.2307/1968431}}. | | *{{cite journal|first=E. T.|last=Bell|authorlink=Eric Temple Bell|title= Exponential polynomials|journal=Annals of Texematics|volume=35|year=1934|pages=258–277|ref=harv|jstor=1968431|doi=10.2307/1968431}}. |
| *{{cite journal|first=E. T.|last=Bell|authorlink=Eric Temple Bell|title= The iterated exponential integers|journal=Annals of Texematics|volume=39|year=1938|pages=539–557|ref=harv|jstor=1968633|doi=10.2307/1968633}}. | | *{{cite journal|first=E. T.|last=Bell|authorlink=Eric Temple Bell|title= The iterated exponential integers|journal=Annals of Texematics|volume=39|year=1938|pages=539–557|ref=harv|jstor=1968633|doi=10.2307/1968633}}. |
− | *{{cite book | + | *[ Bender Edward A.Williamson, S. Gill |
− | | last1 = Bender | first1 = Edward A.
| + | contribution = Example 11.7, Set Partitions pages = 319–320 |
− | | last2 = Williamson | first2 = S. Gill
| + | http://www.tex.ucsd.edu/~ebender/CombText/ch-11.pdf , 2006] |
− | | contribution = Example 11.7, Set Partitions | + | * [[wikipedia:com:Bells numbers| Bells numbers]] |
− | | isbn = 0-486-44603-4
| |
− | | pages = 319–320
| |
− | | publisher = Dover | |
− | | title = Foundations of Combinatorics with Applications
| |
− | | url = http://www.tex.ucsd.edu/~ebender/CombText/ch-11.pdf
| |
− | | year = 2006
| |
− | | ref = harv}}
| |
− | *{{cite journal | |
− | | last1 = Berend | first1 = D.
| |
− | | last2 = Tassa | first2 = T.
| |
− | | issue = 2
| |
− | | journal = Probability and Texematical Statistics
| |
− | | pages = 185–205
| |
− | | title = Improved bounds on Bell numbers and on moments of sums of random variables
| |
− | | volume = 30
| |
− | | year = 2010
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Berndt | first = Bruce C.
| |
− | | issue = 2
| |
− | | journal = Asia Pacific Texematics Newsletter
| |
− | | pages = 8–13
| |
− | | title = Ramanujan Reaches His Hand From His Grave To Snatch Your Theorems From You
| |
− | | url = http://www.asiapacific-texnews.com/01/0102/0008_0013.pdf
| |
− | | volume = 1
| |
− | | year = 2011
| |
− | | ref = harv}}
| |
− | *{{cite book
| |
− | | last = de Bruijn | first = N.G. | author-link = Nicolaas_Govert_de_Bruijn
| |
− | | page = 108
| |
− | | title = Asymptotic methods in analysis
| |
− | | publisher = Dover
| |
− | | edition = 3rd
| |
− | | year = 1981
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Callan | first = David
| |
− | | arxiv = tex/0507169
| |
− | | issue = 1
| |
− | | journal = Journal of Integer Sequences
| |
− | | mr = 2193154
| |
− | | page = 06.1.4
| |
− | | title = A combinatorial interpretation of the eigensequence for composition
| |
− | | url = https://eudml.org/doc/52955
| |
− | | volume = 9
| |
− | | year = 2006
| |
− | | ref = harv|bibcode = 2005tex......7169C}}
| |
− | *{{cite journal
| |
− | | last = Canfield | first = E. Rodney
| |
− | | doi = 10.1016/0097-3165(95)90033-0
| |
− | | issue = 1
| |
− | | journal = Journal of Combinatorial Theory
| |
− | | mr = 1354972
| |
− | | pages = 184–187
| |
− | | series = Series A
| |
− | | title = Engel's inequality for Bell numbers
| |
− | | volume = 72
| |
− | | year = 1995
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Claesson | first = Anders
| |
− | | doi = 10.1006/eujc.2001.0515
| |
− | | issue = 7
| |
− | | journal = European Journal of Combinatorics
| |
− | | mr = 1857258
| |
− | | pages = 961–971
| |
− | | title = Generalized pattern avoidance
| |
− | | volume = 22
| |
− | | year = 2001
| |
− | | ref = harv}}
| |
− | *{{cite book|last1=Conway|first1=John Horton|author1-link=John Horton Conway|last2=Guy|first2=Richard K.|author2-link=Richard K. Guy|title=The Book of Numbers|series=Copernicus Series|publisher=Springer|year=1996|isbn=9780387979939|contribution=Famous Families of Numbers: Bell Numbers and Stirling Numbers|pages=91–94|ref=harv}}
| |
− | *{{cite journal|first=G.|last=Dobiński|title=Summirung<!-- "Summirung" is an archaic spelling, and it is the spelling that was used in this title. --> der Reihe <tex>\textstyle\sum\frac{n^m}{n!}</tex> für ''m'' = 1, 2, 3, 4, 5, …|journal=Grunert's Archiv|volume=61|year=1877|pages=333–336|url=https://archive.org/stream/archivdertexem88unkngoog#page/n346|ref=harv}}
| |
− | *{{cite journal
| |
− | | last = Engel | first = Konrad
| |
− | | doi = 10.1016/0097-3165(94)90038-8
| |
− | | issue = 1
| |
− | | journal = [[Journal of Combinatorial Theory]]
| |
− | | mr = 1255264
| |
− | | pages = 67–78
| |
− | | series = Series A
| |
− | | title = On the average rank of an element in a filter of the partition lattice
| |
− | | volume = 65
| |
− | | year = 1994
| |
− | | ref = harv}}
| |
− | *{{cite book
| |
− | | last1 = Flajolet | first1 = Philippe | author1-link = Philippe Flajolet
| |
− | | last2 = Sedgewick | first2 = Robert | author2-link = Robert Sedgewick (computer scientist)
| |
− | | contribution = II.3 Surjections, set partitions, and words
| |
− | | pages = 106–119
| |
− | | publisher = Cambridge University Press
| |
− | | title = Analytic Combinatorics
| |
− | | url = http://algo.inria.fr/flajolet/Publications/book.pdf
| |
− | | year = 2009
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Gardner | first = Martin | author-link = Martin Gardner
| |
− | | doi = 10.1038/scientificamerican0578-24
| |
− | | journal = [[Scientific American]]
| |
− | | pages = 24–30
| |
− | | title = The Bells: versatile numbers that can count partitions of a set, primes and even rhymes
| |
− | | volume = 238
| |
− | | year = 1978|ref=harv}} Reprinted with an addendum as "The Tinkly Temple Bells", Chapter 2 of ''Fractal Music, Hypercards, and more ... Texematical Recreations from Scientific American'', W. H. Freeman, 1992, pp. 24–38
| |
− | * {{springer|title=Bell numbers|id=p/b110240}}
| |
− | *{{cite arXiv|title=An elementary (number theory) proof of Touchard's congruence|first1=Greg|last1=Hurst|first2=Andrew|last2=Schultz|eprint=0906.0696|year=2009|class=tex.CO|ref=harv}}
| |
− | * {{cite book|contribution=Two thousand years of combinatorics|first=Donald E.|last=Knuth|authorlink=Donald Knuth|pages=7–37|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins|ref=harv}}
| |
− | *{{Cite book |authorlink=László Lovász| last=Lovász | first=L. |title=Combinatorial Problems and Exercises |edition=2nd |place=Amsterdam, Netherlands |publisher=North-Holland |year=1993|zbl=0785.05001|contribution=Section 1.14, Problem 9|page=17|url=https://books.google.com/books?id=e99fXXYx9zcC&pg=PA17|ref=harv}}
| |
− | *{{cite journal
| |
− | | last1 = Moser | first1 = Leo | author1-link = Leo Moser
| |
− | | last2 = Wyman | first2 = Max
| |
− | | journal = Transactions of the Royal Society of Canada, Section III
| |
− | | mr = 0078489
| |
− | | pages = 49–54
| |
− | | title = An asymptotic formula for the Bell numbers
| |
− | | volume = 49
| |
− | | year = 1955
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Peirce | first = C. S. | author-link = Charles Sanders Peirce
| |
− | | issue = 1
| |
− | | journal = [[American Journal of Texematics]]
| |
− | | jstor = 2369442
| |
− | | pages = 15–57
| |
− | | title = On the algebra of logic
| |
− | | volume = 3
| |
− | | year = 1880|ref=harv | doi=10.2307/2369442}}.
| |
− | *{{citation
| |
− | | last = Rota | first = Gian-Carlo | author-link = Gian-Carlo Rota
| |
− | | doi = 10.2307/2312585
| |
− | | issue = 5
| |
− | | journal = [[American Texematical Monthly]]
| |
− | | mr = 0161805
| |
− | | pages = 498–504
| |
− | | title = The number of partitions of a set
| |
− | | volume = 71
| |
− | | year = 1964
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Spivey | first = Michael Z.
| |
− | | issue = 2
| |
− | | journal = Journal of Integer Sequences
| |
− | | mr = 2420912
| |
− | | page = Article 08.2.5, 3
| |
− | | title = A generalized recurrence for Bell numbers
| |
− | | url = http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Spivey/spivey25.pdf
| |
− | | volume = 11
| |
− | | year = 2008
| |
− | | ref = harv}}
| |
− | *{{cite journal
| |
− | | last = Wagstaff | first = Samuel S. | author-link = Sam Wagstaff
| |
− | | bibcode = 1996MaCom..65..383W
| |
− | | doi = 10.1090/S0025-5718-96-00683-7
| |
− | | issue = 213
| |
− | | journal = [[Texematics of Computation]]
| |
− | | mr = 1325876
| |
− | | pages = 383–391
| |
− | | title = Aurifeuillian factorizations and the period of the Bell numbers modulo a prime
| |
− | | url = http://homes.cerias.purdue.edu/~ssw/bell/bell.ps
| |
− | | volume = 65
| |
− | | year = 1996
| |
− | | ref = harv}}
| |
− | * {{cite book | last=Wilf | first=Herbert S. | authorlink=Herbert Wilf | title=Generatingfunctionology | edition=2nd | location=Boston, MA | publisher=Academic Press | year=1994 | isbn=0-12-751956-4 | zbl=0831.05001 |ref=harv | url = https://www.tex.upenn.edu/~wilf/gfology2.pdf
| |
− | }}
| |
− | *{{cite journal
| |
− | | last = Williams | first = G. T.
| |
− | | journal = [[American Texematical Monthly]]
| |
− | | jstor = 2305292
| |
− | | doi = 10.2307/2305292
| |
− | | mr = 0012612
| |
− | | pages = 323–327
| |
− | | title = Numbers generated by the function ''e''<sup>''e''<sup>''x''</sup> − 1</sup>
| |
− | | volume = 52
| |
− | | year = 1945
| |
− | | ref = harv}}
| |
− | {{refend}}
| |
| | | |
| ==External links== | | ==External links== |
Шаблон:Числа Белла
Числа Белла начинаются с 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, treating two factorizations as the same if they have the same factors in a different order.[1] Например, 30 является произведением 3 простых чисел 2, 3, and 5, и имеет B3 = 5 факторизаций:
- [math]30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5[/math]
Схемы рифмовки
Числа Белла показывают количество схем рифмовки n-строфы. Схема рифмы описывает, какие строки рифмуются друг с другом, и поэтому может быть истолковано как разбиение множества строк в подмножества рифм. Таким образом, 15 возможных четверостиший схемами рифмовки являются: AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.Шаблон:Sfn
Вычисление с помощью треугольника Пирса
Шаблон:Main article
Треугольное множество, правая диагональная последовательность которого состоит из чисел Белла
Числа Белла могут быть с легкостью вычислены с помощью треугольника Белла, который также называют массивом Айткена или треугольником Пирса.
- Начнем с единицы. Помещаем ее в верхнюю строку. ([math] x_{0,1} = 1 [/math])
- Каждая новая строка должна начинаться с крайнего правого элемента прошлой строки. ([math]x_{i,1} \leftarrow x_{i-1, r}[/math] где r последний элемент (i-1)-й строки)
- Определим остальные элементы строки [math]( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )[/math]
- Повторяем пункт 3, пока [math] j = r + 1 [/math])
- Крайнее левое число данной строки является числом Белла для этой строки. ([math]B_i \leftarrow x_{i,1}[/math])
Here are the first five rows of the triangle constructed by these rules:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
Свойства
Формулы суммирования
Числа Белла удовлетворяют рекуррентному соотношению 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] является количеством способов разбиения набора элементов n в ровно k непустых подмножеств.
Michael Spivey получил формулу, которая объединяет оба эти суммирования:
- [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]
Суммирование используется для определения экспоненциальной производящей функции для любой последовательности чисел. Правая часть является результатом выполнения суммирования в конкретном случае.
Моменты распределения вероятностей
Числа Белла удовлетворяют формуле ДобинскогоШаблон:SfnШаблон:SfnШаблон:Sfn
- [math]B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.[/math]
Эта формула может быть получена за счет расширения экспоненциальной производящей функции, используя ряд Тейлора для экспоненциальной функции, а затем собирая условия с аналогичным показателем экспоненты.
Это позволяет интерпретировать Bn как n-й момент Пуассоновского распределения с ожидаемым значением 1.
Интегральное представление
Применение интегральной формулы Коши для экспоненциальной производящей функции дает комплексное интегральное представление:
- [math] B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. [/math]
Log-concavity
Числа Белла формируют логарифмически выпуклую последовательность. Деление их на факториал, Bn/n!, дает логарифмически выпуклую последовательность.sequence.
Темпы роста
Известно несколько асимптотических формул для чисел Белла. В Шаблон:Harvtxt были установлены следующие границы:
- [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]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]
Moser Wyman установил расширение:
- [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]
\begin{align}
\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
\end{align}
[/math]
Было установлено де Брайном в 1981 году.
Шаблон:Reflist
References
- [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]
- Шаблон:Cite journal.
- Шаблон:Cite journal.
- [ Bender Edward A.Williamson, S. Gill
contribution = Example 11.7, Set Partitions pages = 319–320
http://www.tex.ucsd.edu/~ebender/CombText/ch-11.pdf , 2006]
External links
Примeчания
- ↑ Шаблон:Harvnb credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).