Bell number

Bell number - the number of all unordered partitions $n$ ${\ displaystyle n}$ $n$ -element set denoted by $B_{n}$ ${\ displaystyle B_ {n}}$ $B_ {n}$ , while by definition $B_{0}=1$ ${\ displaystyle B_ {0} = 1}$ ${\ displaystyle B_ {0} = 1}$ .

Values $B_{n}$ ${\ displaystyle B_ {n}}$ $B_ {n}$ for $n=0,1,2,\dots$ ${\ displaystyle n = 0,1,2, \ dots}$ $n = 0,1,2, \ dots$ form the sequence ^[1] :

1, 1 , 2 , 5 , 15 , 52 , 203, 877 , 4140, 21 147, 115 975, ...

The Bell number can be calculated as the sum of Stirling numbers of the second kind :

B_{n}=\sum _{m=0}^{n}S(n,m)

{\ displaystyle B_ {n} = \ sum _ {m = 0} ^ {n} S (n, m)}

{\ displaystyle B_ {n} = \ sum _ {m = 0} ^ {n} S (n, m)}

,

and also set in recursive form:

B_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}B_{k}

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

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

.

For Bell numbers, the Dobinsky formula is also valid ^[2] :

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

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

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

.

If $p$ ${\ displaystyle p}$ $p$ - simple, the comparison of Tushar is true:

B_{n+p}\equiv B_{n}+B_{n+1}{\pmod {p}}

{\ displaystyle B_ {n + p} \ equiv B_ {n} + B_ {n + 1} {\ pmod {p}}}

{\ displaystyle B_ {n + p} \ equiv B_ {n} + B_ {n + 1} {\ pmod {p}}}

and more general:

B_{n+p^{m}}\equiv mB_{n}+B_{n+1}{\pmod {p}}

{\ displaystyle B_ {n + p ^ {m}} \ equiv mB_ {n} + B_ {n + 1} {\ pmod {p}}}

{\ displaystyle B_ {n + p ^ {m}} \ equiv mB_ {n} + B_ {n + 1} {\ pmod {p}}}

.

The exponential generating function of Bell numbers has the form ^[3] :

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

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

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

.

Notes

↑ sequence A000110 in OEIS
↑ Introduction to Discrete Mathematics, 2006 , p. 202.
↑ Introduction to Discrete Mathematics, 2006 , p. 200.

Literature

Yablonsky S.V. Introduction to discrete mathematics. - M .: Higher school, 2006 .-- 392 p. - ISBN 5-06-005683-X .

[1] sequence A000110 in OEIS

[_a3ff487016469d51-2] Introduction to Discrete Mathematics, 2006 , p. 202.

[_a3ff487016469d53-3] Introduction to Discrete Mathematics, 2006 , p. 200.

Bell number

Notes

Literature

More articles: