Число Белла (Cnvlk >yllg)

Число Белла — число всех неупорядоченных разбиений $n$-элементного множества, обозначаемое $B_{n}$, при этом по определению полагают $B_{0}=1$. Названы в честь Эрика Белла, который изучил их в 1930-е годы.

Значения $B_{n}$ для $n=0,1,2,\dots$ образуют последовательность Белла:

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

Ряд чисел Белла обозначает число способов, с помощью которых можно распределить $n$ пронумерованных шаров по $n$ идентичным коробкам. Кроме этого, числа Белла дают возможность узнать сколько существует способов разложить на множители составное число, состоящее из $n$ простых множителей.

Число Белла можно вычислить как сумму чисел Стирлинга второго рода:

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

а также задать в рекуррентной форме:

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

Для чисел Белла справедлива также формула Добинского:

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

Если $p$ — простое, то верно сравнение Тушара:

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

и более общее:

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

Экспоненциальная производящая функция чисел Белла имеет вид:

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

Литература

• Ламберто Гарсия дель Сид. Замечательные числа. — М.: Де Агостини, 2014. — Т. 21. — 160 с. — (Мир математики: в 40 т.). — ISBN 978-5-9774-0682-6.
• Яблонский С. В. Введение в дискретную математику. — М.: Высшая школа, 2006. — 392 с. — ISBN 5-06-005683-X.
• Bell E. T. Exponential polynomials (англ.) // Annals of Mathematics. — 1934. — Vol. 35. — P. 258–277. — doi:10.2307/1968431. — .
• Bell E. T. The iterated exponential integers (англ.) // Annals of Mathematics. — 1938. — Vol. 39. — P. 539–557. — doi:10.2307/1968633. — .