Число Белла
Число Белла — число всех неупорядоченных разбиений [math]\displaystyle{ n }[/math]-элементного множества, обозначаемое [math]\displaystyle{ B_n }[/math], при этом по определению полагают [math]\displaystyle{ B_0 = 1 }[/math].
Значения [math]\displaystyle{ B_n }[/math] для [math]\displaystyle{ n=0,1,2,\dots }[/math] образуют последовательность[1]:
Ряд чисел Белла обозначает число способов, с помощью которых можно распределить [math]\displaystyle{ n }[/math] пронумерованных шаров по [math]\displaystyle{ n }[/math] идентичным коробкам. Кроме этого, числа Белла дают возможность узнать сколько существует способов разложить на множители составное число, состоящее из [math]\displaystyle{ n }[/math] простых множителей[2].
Числа Белла названы в честь Эрика Белла, который писал о них в 1930-х годах.
Математические свойства
Число Белла можно вычислить как сумму чисел Стирлинга второго рода:
- [math]\displaystyle{ B_n = \sum_{m=0}^n S(n, m), }[/math]
а также задать в рекуррентной форме:
- [math]\displaystyle{ B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k. }[/math]
Для чисел Белла справедлива также формула Добинского[3]:
- [math]\displaystyle{ B_n = \frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}. }[/math]
Если [math]\displaystyle{ p }[/math] — простое, то верно сравнение Тушара:
- [math]\displaystyle{ B_{n+p} \equiv B_n + B_{n+1} \pmod{p} }[/math]
и более общее:
- [math]\displaystyle{ B_{n+p^m} \equiv mB_n + B_{n+1} \pmod{p}. }[/math]
Экспоненциальная производящая функция чисел Белла имеет вид[4]
- [math]\displaystyle{ \sum_{n=0}^\infty \frac{B_n}{n!} x^n = e^{e^x-1}. }[/math]
Примечания
- ↑ последовательность A000110 в OEIS
- ↑ дель Сид, 2014, Числа Белла, с. 105.
- ↑ Введение в дискретную математику, 2006, с. 202.
- ↑ Введение в дискретную математику, 2006, с. 200.
Литература
- Ламберто Гарсия дель Сид. Замечательные числа : Ноль, 666 и другие бестии. — М. : «Де Агостини», 2014. — Т. 21. — 160 с. — (Мир математики: в 40 т.). — ББК 22.1. — УДК 51(0.062)(G). — ISBN 978-5-9774-0682-6.
- Яблонский С. В. Введение в дискретную математику. — М.: Высшая школа, 2006. — 392 с. — ISBN 5-06-005683-X.
Ссылки
- Bell, E. T. (1934). «Exponential polynomials». Annals of Mathematics 35: 258–277. doi:10.2307/1968431..
- Bell, E. T. (1938). «The iterated exponential integers». Annals of Mathematics 39: 539–557. doi:10.2307/1968633..