WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Высшая школа, 2006. — 392 с. — ISBN 5-06-005683-X.

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.