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

Материал из Викиконспекты
Перейти к: навигация, поиск
(References)
(References)
Строка 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''&nbsp;=&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;4,&nbsp;5,&nbsp;…|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.&nbsp;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>&nbsp;&minus;&nbsp;1</sup>
 
  | volume = 52
 
| year = 1945
 
| ref = harv}}
 
{{refend}}
 
  
 
==External links==
 
==External links==

Версия 14:35, 8 октября 2017

Шаблон:Числа Белла Числа Белла начинаются с 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-й строфы стихотворения.

Подсчет

Разделение набора

Файл:Set partitions 5; Order.png
The 52 partitions of a set with 5 elements

Bn количество разбиений множества размера n. Разбиение множества S определяется как совокупность непустых, попарно непересекающихся подмножеств множества S. Например, B3 = 5, потому что множество, состоящее их 3 элементов {abc} может быть разделено 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

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

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

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

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чания

  1. Шаблон:Harvnb credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).