Формула Добинского

В комбинаторной математике формула Добинского ^[1] утверждает, что n - е число Белла B _n (т.е. число разбиений множества размера n ) равно

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

где обозначает число Эйлера . Формула названа в честь Г. Добинского, который опубликовал ее в 1877 году.${\displaystyle е}$

В теории вероятностей формула Добинского представляет собой n- й момент распределения Пуассона со средним значением 1. Иногда формулу Добинского формулируют так, что число разбиений множества размера n равно n -му моменту этого распределения.

Вычисление суммы ряда Добинского можно свести к конечной сумме членов, принимая во внимание информацию, которая является целым числом. Точно, для любого целого числа${\displaystyle n+o(n)}$${\displaystyle B_{n}}$${\displaystyle К>1}$

${\displaystyle B_{n}=\left\lceil {1 \over e}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}\right\rceil }$

при условии (условие, которое, конечно, подразумевает , но которому удовлетворяют некоторые из размера ). Действительно, поскольку , то есть ${\displaystyle {\frac {K^{n}}{K!}}\leq 1}$${\displaystyle К>н}$${\displaystyle К}$${\displaystyle n+o(n)}$${\displaystyle К>н}$

${\displaystyle {\begin{aligned}\displaystyle {\Big (}{\frac {K+j}{K}}{\Big )}^{n}&\leq {\Big (}{\frac {K+j}{K}}{\Big )}^{K}={\Big (}1+{\frac {j}{K}}{\Big )}^{K}\\&\leq {\Big (}1+{\frac {j}{1}}{\Big )}{\Big (}1+{\frac {j}{2}}{\Big )}\dots {\Big (}1+{\frac {j}{K}}{\Big )}\\&={\frac {1+j}{1}}{\frac {2+j}{2}}\dots {\frac {K+j}{K}}\\&={\frac {(К+j)!}{К!j!}}.\end{align}}}$

Поэтому для всех так, что хвост доминируется рядом , что влечет , откуда и вытекает приведенная формула.${\displaystyle {\frac {(K+j)^{n}}{(K+j)!}}\leq {\frac {K^{n}}{K!}}{\frac {1}{j!}}\leq {\frac {1}{j!}}}$${\displaystyle j\geq 0}$${\displaystyle \sum _{k\geq K}{\frac {k^{n}}{k!}} =\sum _{j\geq 0}{\frac {(K+j)^{n} }{(K+j)!}}}$${\displaystyle \sum _{j\geq 0}{\frac {1}{j!}}=e}$${\displaystyle 0<B_{n}-{\frac {1}{e}}\sum _{k=0}^{K-1}{\frac {k^{n}}{k!}}<1}$

Формулу Добинского можно рассматривать как частный случай, для , более общего соотношения:${\displaystyle x=0}$$${\displaystyle {1 \over e}\sum _{k=x}^{\infty }{\frac {k^{n}}{(kx)!}}=\sum _{k=0}^{ n}{\binom {n}{k}}B_{k}x^{nk}}$$

и для этой формулы для полиномов Тушара${\displaystyle x=1}$

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

Одно доказательство ^[2] опирается на формулу для производящей функции для чисел Белла ,

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

Степенной ряд для экспоненты дает

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

так

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

Коэффициент в этом степенном ряду должен быть , поэтому${\displaystyle x^{n}}$${\displaystyle B_{n}/n!}$

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

Другой стиль доказательства был дан Ротой . ^[3] Напомним, что если x и n — неотрицательные целые числа, то число функций один к одному , которые отображают множество размера n в множество размера x, является убывающим факториалом

${\displaystyle (x)_{n}=x(x-1)(x-2)\cdots (x-n+1)}$

Пусть ƒ — любая функция из множества A размера n в множество B размера x . Для любого b  ∈  B пусть ƒ ⁻¹ ( b ) = { a  ∈  A  : ƒ ( a ) = b }. Тогда { ƒ ⁻¹ ( b ) : b  ∈  B } — разбиение A . Рота называет это разбиение « ядром » функции ƒ . Любая функция из A в B разлагается в

• одна функция, которая сопоставляет элемент A с элементом ядра, к которому он принадлежит, и
• другая функция, которая обязательно является однозначной, которая отображает ядро ​​в B.

Первый из этих двух факторов полностью определяется разбиением π, которое является ядром. Число функций один к одному из π в B равно ( x ) _{| π |} , где | π | — число частей в разбиении π . Таким образом, общее число функций из множества A размера n в множество B размера x равно

${\displaystyle \sum _{\pi }(x)_{|\pi |},}$

индекс π пробегает множество всех разбиений A. С другой стороны, число функций из A в B , очевидно, равно x ⁿ . Поэтому мы имеем

${\displaystyle x^{n}=\sum _{\pi }(x)_{|\pi |}.}$

Рота продолжает доказательство, используя линейную алгебру, но полезно ввести случайную величину X, распределенную по закону Пуассона, со средним значением 1. Уравнение выше подразумевает, что n- й момент этой случайной величины равен

${\displaystyle E(X^{n})=\sum _{\pi }E((X)_{|\pi |})}$

где E обозначает ожидаемое значение . Но мы покажем, что все величины E (( X ) _k ) равны 1. Из этого следует, что

${\ displaystyle E (X ^ {n}) = \ sum _ {\ pi} 1,}$

и это как раз число разбиений множества A.

Величина E (( X ) _k ) называется k-м факториальным моментом случайной величины X . Чтобы показать, что это равно 1 для всех k , когда X является распределенной по Пуассону случайной величиной со средним значением 1, напомним, что эта случайная величина принимает каждое значение целочисленного значения с вероятностью . Таким образом,${\displaystyle j\geq 0}$${\displaystyle 1/(ej!)}$

${\displaystyle \displaystyle {\begin{aligned}E((X)_{k})&=\sum _{j=0}^{\infty }{\frac {(j)_{k}}{ej!}}\\&={\frac {1}{e}}\sum _{j=0}^{\infty }{\frac {j(j-1)\cdots (j-k+1)}{j(j-1)\cdots 1}}\\&={\frac {1}{e}}\sum _{j=i}^{\infty }{\frac {1}{(j-i)!}}=1.\end{aligned}}}$