Bell number

The Bell number , Bell number or exponential number is the number of partitions in a -element set. It is named after the mathematician Eric Temple Bell . The episode begins with ${\displaystyle B_{n}}$ ${\displaystyle n}$ ${\displaystyle B_{0},B_{1},B_{2},B_{3},\ldots }$

${\displaystyle 1,1,2,5,15,52,203,877,4140,21147,115975,678570,\ldots }$(Follow A000110 in OEIS )

meaning

Partitions

→ Main article : Partition (set theory)

A partition an amount includes pairwise disjoint subsets of so that each element is made in exactly an amount from occurring. For all natural numbers including zero , Bell's number now designates the number of possible different partitions of a set with the cardinality , where the set represents all possible partitions. Formally: ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle B_{n}}$ ${\displaystyle \left|Q\right|}$ ${\displaystyle n}$ ${\displaystyle Q}$

${\displaystyle \left|M\right|=n}$

${\displaystyle \forall P\in Q:\bigcup _{x\in P}x=M}$

${\displaystyle \forall P\in Q~\forall a,b\in P\ {\text{mit}}\ a\neq b:a\cap b=\emptyset }$

${\displaystyle B_{n}=\left|Q\right|}$

The Bell number with index 0 - i.e. the number of partitions of the empty set - is 1 because the only partition of the empty set is again the empty set itself. This is because all statements with the universal quantifier about the elements of the empty set are true (see empty set ). ${\displaystyle B_{0}}$ ${\displaystyle \emptyset }$

Multiplicative partitions

→ Main article : Multiplicative partition

Let be a square-free number , then is , where is the function for determining the number of unique prime factors . Then again the number of different multiplicative partitions is from . ${\displaystyle N}$ ${\displaystyle n=\omega (N)}$ ${\displaystyle \omega :\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle B_{n}}$ ${\displaystyle N}$

Let, for example , be (since 30 consists of the three prime factors 2, 3 and 5) and is therefore the number of multiplicative partitions. These are: ${\displaystyle N=30}$ ${\displaystyle n=\omega (30)=3}$ ${\displaystyle B_{3}=5}$

${\displaystyle 30\times 1=2\times 15=3\times 10=5\times 6=2\times 3\times 5}$

properties

The recursion formula applies to Bell numbers

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}}$

and the formula (Dobiński 1877)

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}\,,}$

thus the th moment of a Poisson distribution with expected value 1 is also. ${\displaystyle B_{n}}$ ${\displaystyle n}$

The generating function of the bell numbers is

${\displaystyle \sum _{n=0}^{\infty }B_{n}\,x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!\,(1-kx)}}\,,}$

is the exponential generating function

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}\,x^{n}=e^{e^{x}-1}\,.}$

In addition, the Bell numbers are sufficient for congruence (Touchard 1933)

${\displaystyle B_{p^{k}+n}\equiv k\,B_{n}+B_{n+1}\ ({\text{mod }}p)}$

for natural numbers and prime numbers , in particular and and, after iteration, ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle B_{p^{k}}\equiv k+1\ ({\text{mod }}p)}$ ${\displaystyle B_{p}\equiv 2\ ({\text{mod }}p)}$

${\displaystyle B_{1+p+\ldots +p^{p-1}+n}\equiv B_{n}\ ({\text{mod }}p).}$

It is thought that the smallest period of is. For prime numbers is ${\displaystyle 1+p+\dots +p^{p-1}}$ ${\displaystyle B_{n}\ ({\text{mod }}p)}$ ${\displaystyle p>2}$

${\displaystyle B_{p^{k+1}n}\equiv B_{p^{k}n+1}\ ({\text{mod }}p^{k+1}),}$

for is congruence . ${\displaystyle p=2}$ ${\displaystyle ({\text{mod }}p^{k})}$

Since the Stirling number of the second kind is the number of -partitions of a -elementary, we have ${\displaystyle S(n,k)}$ ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}$

Asymptotics

Various asymptotic formulas are known for the Bell numbers, for example

${\displaystyle B_{n}\sim n^{-1/2}\ {\bigl (}\lambda (n){\bigr )}^{n+1/2}\ e^{\lambda (n)-n-1}}$     With     ${\displaystyle \lambda (n)=e^{W(n)}={\frac {n}{W(n)}}}$

with the Lambert W function . ${\displaystyle W}$

Bell's triangle

Bell's numbers can be generated intuitively by Bell's triangle, which - like Pascal's triangle - consists of numbers and has one more element or one column per line. The Bell triangle is sometimes also called Aitkens array (after  Alexander Aitken ) or Peirce triangle (after  Charles Sanders Peirce ).

It is constructed according to the following rules:

1. The first line has only one element: the one (1).
2. If the -th line (starting from 1) has elements, a new line is created. The first number of the new line results from the last number of the last line. ${\displaystyle n}$ ${\displaystyle n}$
3. The -th number of the line (for ) results from the sum of the -th element of the same line and the -th element of the previous line (i.e. the one with the number ). ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle 1<k\leq n}$ ${\displaystyle (k-1)}$ ${\displaystyle (k-1)}$ ${\displaystyle n-1}$
4. ${\displaystyle B_{n}}$is now the -th element of the -th line. ${\displaystyle n}$ ${\displaystyle n}$

The first five lines - generated according to these rules - look like this:

 1
 1   2
 2   3   5
 5   7  10  15
15  20  27  37  52

Because of the second step, Bell's numbers can be seen both on the left and on the right edge of the triangle, with the only difference that in the -th line the number is on the left and the number on the right . ${\displaystyle n}$ ${\displaystyle B_{n-1}}$ ${\displaystyle B_{n}}$

Bell primes

In 1978 Martin Gardner formulated the question of whether an infinite number of Bell numbers are also prime numbers . The first Bell prime numbers are:

${\displaystyle n}$(Follow A051130 in OEIS )	${\displaystyle B_{n}}$(Follow A051131 in OEIS )
2	2
3	5
7th	877
13	27644437
42	35742549198872617291353508656626642567
55	359334085968622831041960188598043661065388726959079837

The closest Bell prime number is , which roughly equals. It is also currently the largest known Bell prime number (as of August 5, 2018). In 2002 Phil Carmody showed  that this number is probably a prime number (a so-called PRP number ), i.e. it is either actually a true prime number or a pseudoprime number . After a 17-month calculation with Marcel Martin's program "Primo", which works with a method with elliptic curves , Ignacio Larrosa Cañestro proved in 2004 that it is a prime number. At the same time he joined Bell's other prime numbers up to a limit of from which later by Eric Weis stone on was raised. ${\displaystyle B_{2841}}$ ${\displaystyle 9{,}30740105\times 10^{6538}}$ ${\displaystyle B_{2841}}$ ${\displaystyle B_{6000}}$ ${\displaystyle B_{30447}}$

Individual evidence

1. ↑ G. Dobiński: Summing up the series for ${\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}}$ ${\displaystyle m=1,2,3,4,5,\ldots }$ , Grunert Archive 61, 1877, pp. 333–336
2. ^ Jacques Touchard: Propriétés arithmétiques de certains nombres récurrents , Annales de la Société scientifique de Bruxelles A 53, 1933, pp. 21–31 (French)
3. ↑ Marshall Hall : Arithmetic properties of a partition function , Bulletin of the AMS 40, 1934, p. 387 (English; abstract only)
4. ↑ Christian Radoux: Nombres de Bell, modulo p premier, et extensions de degré p de F _p , Comptes rendus hebdomadaires des séances de l'académie des sciences 281 A, 1975, pp. 879-882 ​​(French)
5. ↑ Peter L. Montgomery , Sangil Nahm, Samuel S. Wagstaff : The period of the Bell numbers modulo a prime ( PDF file, 168 kB), Mathematics of computation 79, 2010, pp. 1793–1800 (English)
6. ^ Anne Gertsch, Alain M. Robert : Some congruences concerning the Bell numbers , Bulletin of the Belgian Mathematical Society - Simon Stevin 3, 1996, pp. 467–475 (English)
7. ↑ 93074010508593618333 ... (6499 other digits) ... 83885253703080601131 on Prime Pages . Retrieved August 5, 2018.

literature

• Eric Temple Bell : Exponential Numbers , The American Mathematical Monthly 41, 1934, pp. 411-419
• Jacques Touchard: Nombres exponentiels et nombres de Bernoulli , Canadian Journal of Mathematics 8, 1956, pp. 305-320 (French)

Web links

• Eric W. Weisstein : Bell Number and Dobiński's Formula . In MathWorld (English)
• Bell numbers at The Wolfram Functions Site (English; with calculation option)
• Set Partitions: Bell Numbers in the NIST Digital Library of Mathematical Functions (English)
• Peter Luschny: Set partitions and Bell numbers (English). A summary of OEIS consequences for the Bell Numbers in the OEIS Wiki.