Английская Википедия:Bell number

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

The Bell numbers are denoted <math>B_n</math>, where <math>n</math> is an integer greater than or equal to zero. Starting with <math>B_0 = B_1 = 1</math>, the first few Bell numbers are

1, 1, 2, 5, 15, 52, 203, 877, 4140, ... Шаблон:OEIS.

The Bell number <math>B_n</math> counts the number of different ways to partition a set that has exactly <math>n</math> elements, or equivalently, the number of equivalence relations on it. <math>B_n</math> also counts the number of different rhyme schemes for <math> n </math>-line poems.Шаблон:Sfn

As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, <math>B_n</math> is the <math> n </math>-th moment of a Poisson distribution with mean 1.

Counting

Set partitions

Шаблон:Main article

Файл:Bell numbers subset partial order.svg

Partitions of sets can be arranged in a partial order, showing that each partition of a set of size n "uses" one of the partitions of a set of size n − 1.

Файл:Set partitions 5; circles.svg

The 52 partitions of a set with 5 elements

In general, <math>B_n</math> is the number of partitions of a set of size <math>n</math>. A partition of a set <math>S</math> is defined as a family of nonempty, pairwise disjoint subsets of <math>S</math> whose union is <math>S</math>. For example, <math>B_3 = 5</math> because the 3-element set <math>\{a,b,c\}</math> can be partitioned in 5 distinct ways:

As suggested by the set notation above, the ordering of subsets within the family is not considered; ordered partitions are counted by a different sequence of numbers, the ordered Bell numbers. <math>B_0</math> is 1 because there is exactly one partition of the empty set. This partition is itself the empty set; it can be interpreted as a family of subsets of the empty set, consisting of zero subsets. It is vacuously true that all of the subsets in this family are non-empty subsets of the empty set and that they are pairwise disjoint subsets of the empty set, because there are no subsets to have these unlikely properties.

The partitions of a set correspond one-to-one with its equivalence relations. These are binary relations that are reflexive, symmetric, and transitive. The equivalence relation corresponding to a partition defines two elements as being equivalent when they belong to the same partition subset as each other. Conversely, every equivalence relation corresponds to a partition into equivalence classes.^[1] Therefore, the Bell numbers also count the equivalence relations.

Factorizations

If a number <math>N</math> is a squarefree positive integer, meaning that it is the product of some number <math>n</math> of distinct prime numbers), then <math>B_n</math> gives the number of different multiplicative partitions of <math>N</math>. These are factorizations of <math>N</math> into numbers greater than one, treating two factorizations as the same if they have the same factors in a different order.^[2] For instance, 30 is the product of the three primes 2, 3, and 5, and has <math>B_3</math> = 5 factorizations:

<math>30 = 2\times 15=3\times 10=5\times 6=2\times 3\times 5</math>

Rhyme schemes

The Bell numbers also count the rhyme schemes of an n-line poem or stanza. A rhyme scheme describes which lines rhyme with each other, and so may be interpreted as a partition of the set of lines into rhyming subsets. Rhyme schemes are usually written as a sequence of Roman letters, one per line, with rhyming lines given the same letter as each other, and with the first lines in each rhyming set labeled in alphabetical order. Thus, the 15 possible four-line rhyme schemes are AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, and ABCD.Шаблон:Sfn

Permutations

The Bell numbers come up in a card shuffling problem mentioned in the addendum to Шаблон:Harvtxt. If a deck of n cards is shuffled by repeatedly removing the top card and reinserting it anywhere in the deck (including its original position at the top of the deck), with exactly n repetitions of this operation, then there are nⁿ different shuffles that can be performed. Of these, the number that return the deck to its original sorted order is exactly B_n. Thus, the probability that the deck is in its original order after shuffling it in this way is B_n/nⁿ, which is significantly larger than the 1/n! probability that would describe a uniformly random permutation of the deck.

Related to card shuffling are several other problems of counting special kinds of permutations that are also answered by the Bell numbers. For instance, the nth Bell number equals the number of permutations on n items in which no three values that are in sorted order have the last two of these three consecutive. In a notation for generalized permutation patterns where values that must be consecutive are written adjacent to each other, and values that can appear non-consecutively are separated by a dash, these permutations can be described as the permutations that avoid the pattern 1-23. The permutations that avoid the generalized patterns 12-3, 32-1, 3-21, 1-32, 3-12, 21-3, and 23-1 are also counted by the Bell numbers.Шаблон:Sfnp The permutations in which every 321 pattern (without restriction on consecutive values) can be extended to a 3241 pattern are also counted by the Bell numbers.Шаблон:Sfnp However, the Bell numbers grow too quickly to count the permutations that avoid a pattern that has not been generalized in this way: by the (now proven) Stanley–Wilf conjecture, the number of such permutations is singly exponential, and the Bell numbers have a higher asymptotic growth rate than that.

Triangle scheme for calculations

Шаблон:Main article

Файл:BellNumberAnimated.gif

The triangular array whose right-hand diagonal sequence consists of Bell numbers

The Bell numbers can easily be calculated by creating the so-called Bell triangle, also called Aitken's array or the Peirce triangle after Alexander Aitken and Charles Sanders Peirce.^[3]

Start with the number one. Put this on a row by itself. (<math> x_{0,1} = 1 </math>)
Start a new row with the rightmost element from the previous row as the leftmost number (<math>x_{i,1} \leftarrow x_{i-1, r}</math> where r is the last element of (i-1)-th row)
Determine the numbers not on the left column by taking the sum of the number to the left and the number above the number to the left, that is, the number diagonally up and left of the number we are calculating <math>( x_{i,j} \leftarrow x_{i,j-1} + x_{i-1,j-1} )</math>
Repeat step three until there is a new row with one more number than the previous row (do step 3 until <math> j = r + 1 </math>)
The number on the left hand side of a given row is the Bell number for that row. (<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

The Bell numbers appear on both the left and right sides of the triangle.

Properties

Summation formulas

The Bell numbers satisfy a recurrence relation involving binomial coefficients:Шаблон:Sfn

<math>B_{n+1}=\sum_{k=0}^{n} \binom{n}{k} B_k.</math>

It can be explained by observing that, from an arbitrary partition of n + 1 items, removing the set containing the first item leaves a partition of a smaller set of k items for some number k that may range from 0 to n. There are <math>\tbinom{n}{k}</math> choices for the k items that remain after one set is removed, and B_k choices of how to partition them.

A different summation formula represents each Bell number as a sum of Stirling numbers of the second kind

<math>B_n=\sum_{k=0}^n \left\{{n\atop k}\right\}.</math>

The Stirling number <math>\left\{{n\atop k}\right\}</math> is the number of ways to partition a set of cardinality n into exactly k nonempty subsets. Thus, in the equation relating the Bell numbers to the Stirling numbers, each partition counted on the left hand side of the equation is counted in exactly one of the terms of the sum on the right hand side, the one for which k is the number of sets in the partition.Шаблон:Sfnp

Шаблон:Harvtxt has given a formula that combines both of these summations:

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

Applying Pascal's inversion formula to the recurrence relation, we obtain<math display="block">B_n = \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} B_{k+1}</math>

Which can be generalized in this manner^[4]

<math display="block">\sum_{j=0}^n \binom{n}{j} B_{k+j} = \sum_{i=0}^k \binom{k}{i} (-1)^{k-i} B_{n+i+1}</math>Other finite sum formulas using Stirling numbers of the first kind include^[4]

<math display="block">\sum_{j=0}^n \binom{n}{j} a^j b^{n-j} B_j = \sum_{i=0}^k \left[{k \atop i}\right](-1)^{k-i} \sum_{j=0}^n \binom{n}{j} a^j (b-ak)^{n-j}B_{j+i}</math>

Which simplifies down with <math>k=1</math> to

<math display="block">\sum_{j=0}^n \binom{n}{j} a^j b^{n-j} B_j = \sum_{j=0}^n \binom{n}{j} a^j (b-a)^{n-j}B_{j+1}</math>

and with <math>a=1, b=k</math> to

<math display="block">\sum_{j=0}^n \binom{n}{j} B_j k^{n-j} = \sum_{i=0}^k \left[{k \atop i}\right] B_{n+i} (-1)^{k-i}</math>which can be seen as the inversion formula for Stirling numbers applied to Spivey's formula.

Generating function

The exponential generating function of the Bell numbers is

<math>B(x) = \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}.</math>

In this formula, the summation in the middle is the general form used to define the exponential generating function for any sequence of numbers, and the formula on the right is the result of performing the summation in the specific case of the Bell numbers.

One way to derive this result uses analytic combinatorics, a style of mathematical reasoning in which sets of mathematical objects are described by formulas explaining their construction from simpler objects, and then those formulas are manipulated to derive the combinatorial properties of the objects. In the language of analytic combinatorics, a set partition may be described as a set of nonempty urns into which elements labelled from 1 to n have been distributed, and the combinatorial class of all partitions (for all n) may be expressed by the notation

<math>\mathrm{S\scriptstyle ET}(\mathrm{S\scriptstyle ET}_{\ge 1}(\mathcal{Z})).</math>

Here, <math>\mathcal{Z}</math> is a combinatorial class with only a single member of size one, an element that can be placed into an urn. The inner <math>\mathrm{S\scriptstyle ET}_{\ge 1}</math> operator describes a set or urn that contains one or more labelled elements, and the outer <math>\mathrm{S\scriptstyle ET}</math> describes the overall partition as a set of these urns. The exponential generating function may then be read off from this notation by translating the <math>\mathrm{S\scriptstyle ET}</math> operator into the exponential function and the nonemptiness constraint ≥1 into subtraction by one.Шаблон:Sfn

An alternative method for deriving the same generating function uses the recurrence relation for the Bell numbers in terms of binomial coefficients to show that the exponential generating function satisfies the differential equation <math>B'(x) = e^{x}B(x)</math>. The function itself can be found by solving this equation.Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn

Moments of probability distributions

The Bell numbers satisfy Dobinski's formula Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn

<math>B_n=\frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}.</math>

This formula can be derived by expanding the exponential generating function using the Taylor series for the exponential function, and then collecting terms with the same exponent.Шаблон:Sfn It allows B_n to be interpreted as the nth moment of a Poisson distribution with expected value 1.

The nth Bell number is also the sum of the coefficients in the nth complete Bell polynomial, which expresses the nth moment of any probability distribution as a function of the first n cumulants.

Modular arithmetic

The Bell numbers obey Touchard's congruence: If p is any prime number thenШаблон:Sfnp

<math>B_{p+n} \equiv B_n+B_{n+1} \pmod p</math>

or, generalizingШаблон:Sfnp

<math>B_{p^m+n} \equiv mB_n+B_{n+1} \pmod p.</math>

Because of Touchard's congruence, the Bell numbers are periodic modulo p, for every prime number p; for instance, for p = 2, the Bell numbers repeat the pattern odd-odd-even with period three. The period of this repetition, for an arbitrary prime number p, must be a divisor of

and for all prime p ≤ 101 and p = 113, 163, 167, or 173 it is exactly this number Шаблон:OEIS.Шаблон:Sfn Шаблон:Sfn

The period of the Bell numbers to modulo n are

1, 3, 13, 12, 781, 39, 137257, 24, 39, 2343, 28531167061, 156, 25239592216021, 411771, 10153, 48, 51702516367896047761, 39, 109912203092239643840221, 9372, 1784341, 85593501183, 949112181811268728834319677753, 312, 3905, 75718776648063, 117, 1647084, 91703076898614683377208150526107718802981, 30459, 568972471024107865287021434301977158534824481, 96, 370905171793, 155107549103688143283, 107197717, 156, ... Шаблон:OEIS

Integral representation

An application of Cauchy's integral formula to the exponential generating function yields the complex integral representation

<math> B_n = \frac{n!}{2 \pi i e} \int_{\gamma} \frac{e^{e^z}}{z^{n+1}} \, dz. </math>

Some asymptotic representations can then be derived by a standard application of the method of steepest descent.^[5]

Log-concavity

The Bell numbers form a logarithmically convex sequence. Dividing them by the factorials, B_n/n!, gives a logarithmically concave sequence.Шаблон:Sfn Шаблон:Sfn Шаблон:Sfn

Growth rate

Several asymptotic formulas for the Bell numbers are known. In Шаблон:Harvtxt the following bounds were established:

<math> B_n < \left( \frac{0.792 n}{\ln( n+1)} \right)^n </math> for all positive integers <math>n</math>;

moreover, if <math> \varepsilon>0 </math> then for all <math> n > n_0(\varepsilon) </math>,

where <math> ~n_0(\varepsilon) = \max\left\{e^4,d^{-1}(\varepsilon) \right\}~ </math> and <math> ~d(x):= \ln \ln (x+1) - \ln \ln x + \frac{1+e^{-1}}{\ln x}\,. </math> The Bell numbers can also be approximated using the Lambert W function, a function with the same growth rate as the logarithm, as Шаблон:Sfnp

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

Шаблон:Harvtxt established the expansion

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

uniformly for <math>h = O(\ln(n))</math> as <math>n \rightarrow \infty</math>, where <math>B</math> and each <math>P_i</math> and <math>Q_i</math> are known expressions in <math>W(n)</math>.^[6]

The asymptotic expression

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

was established by Шаблон:Harvtxt.

Bell primes

Шаблон:Harvtxt raised the question of whether infinitely many Bell numbers are also prime numbers. The first few Bell numbers that are prime are:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837 Шаблон:OEIS

corresponding to the indices 2, 3, 7, 13, 42 and 55 Шаблон:OEIS.

The next Bell prime is B₂₈₄₁, which is approximately 9.30740105 × 10⁶⁵³⁸.^[7] Шаблон:As of, it is the largest known prime Bell number. Ignacio Larrosa Cañestro showed it was a probable prime in 2002. After 17 months of computation with Marcel Martin's ECPP program Primo, Ignacio Larrosa Cañestro proved it to be prime in 2004. He ruled out any other possible primes below B₆₀₀₀, later extended to B₃₀₄₄₇ by Eric Weisstein.^[8] The search was extended to B₅₀₀₀₀ by Václav Kotěšovec (05/18/2021).

History

The Bell numbers are named after Eric Temple Bell, who wrote about them in 1938, following up a 1934 paper in which he studied the Bell polynomials.Шаблон:Sfn Шаблон:Sfn Bell did not claim to have discovered these numbers; in his 1938 paper, he wrote that the Bell numbers "have been frequently investigated" and "have been rediscovered many times". Bell cites several earlier publications on these numbers, beginning with Шаблон:Harvtxt which gives Dobiński's formula for the Bell numbers. Bell called these numbers "exponential numbers"; the name "Bell numbers" and the notation B_n for these numbers was given to them by Шаблон:Harvtxt.^[9]

The first exhaustive enumeration of set partitions appears to have occurred in medieval Japan, where (inspired by the popularity of the book The Tale of Genji) a parlor game called genji-ko sprang up, in which guests were given five packets of incense to smell and were asked to guess which ones were the same as each other and which were different. The 52 possible solutions, counted by the Bell number B₅, were recorded by 52 different diagrams, which were printed above the chapter headings in some editions of The Tale of Genji.Шаблон:Sfn^[10]

In Srinivasa Ramanujan's second notebook, he investigated both Bell polynomials and Bell numbers.Шаблон:Sfn Early references for the Bell triangle, which has the Bell numbers on both of its sides, include Шаблон:Harvtxt and Шаблон:Harvtxt.

Notes

Шаблон:Reflist

References

Шаблон:Refbegin

Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite journal.
Шаблон:Cite journal.
Шаблон:Cite journal.
Шаблон:Cite book
Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite book
Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite book
Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite book
Шаблон:Cite journal Reprinted with an addendum as "The Tinkly Temple Bells", Chapter 2 of Fractal Music, Hypercards, and more ... Mathematical Recreations from Scientific American, W. H. Freeman, 1992, pp. 24–38
Шаблон:Springer
Шаблон:Cite arXiv
Шаблон:Cite book
Шаблон:Cite book
Шаблон:Cite journal
Шаблон:Cite journal.
Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite journal
Шаблон:Cite book
Шаблон:Cite journal

Шаблон:Refend

External links

Шаблон:Classes of natural numbers

↑ Шаблон:Cite book
↑ Шаблон:Harvnb credits this observation to Silvio Minetola's Principii di Analisi Combinatoria (1909).
↑ Шаблон:Cite OEIS
↑ ^4,0 ^4,1 Шаблон:Cite journal
↑ Шаблон:Cite book
↑ Шаблон:Cite web
↑ Шаблон:Cite web
↑ Шаблон:Mathworld
↑ Шаблон:Harvnb. However, Rota gives an incorrect date, 1934, for Шаблон:Harvnb.
↑ Шаблон:Harvnb and Шаблон:Harvnb also mention the connection between Bell numbers and The Tale of Genji, in less detail.

[1] Шаблон:Cite book

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

[3] Шаблон:Cite OEIS

[:0-4] 4,0 ^4,1 Шаблон:Cite journal

[5] Шаблон:Cite book

[6] Шаблон:Cite web

[7] Шаблон:Cite web

[8] Шаблон:Mathworld

[9] Шаблон:Harvnb. However, Rota gives an incorrect date, 1934, for Шаблон:Harvnb.

[10] Шаблон:Harvnb and Шаблон:Harvnb also mention the connection between Bell numbers and The Tale of Genji, in less detail.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.