Wzór Dobińskiego

Wzór Dobińskiego – w kombinatoryce wzór wyrażający liczbę podziałów zbioru ${\displaystyle n}$-elementowego^[1]:

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

Liczbę ${\displaystyle B_{n}}$ nazywa się ${\displaystyle n}$-tą liczbą Bella, na cześć Erica Temple Bella.

Powyższy wzór może być postrzegany jako szczególny przypadek, dla ${\displaystyle x=0,}$ bardziej ogólnego stosunku:

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

Nazwą tą określa się również ogólniejszy wzór na wielomiany Bella:

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

Treść probabilistyczna

Wyrażenie dane przez wzór Dobińskiego jest ${\displaystyle n}$-tym momentem rozkładu Poissona z wartością oczekiwaną 1. Innymi słowy, wzór Dobińskiego stwierdza, że liczba podziałów zbioru mocy ${\displaystyle n}$ jest równa ${\displaystyle n}$-temu momentowi tego rozkładu.

Dowód

Dowód podany tu jest adaptacją do probabilistycznego języka dowodu danego przez Rotę^[2].

W kombinatoryce używa się symbolu Pochhammera ${\displaystyle (x)_{n}}$ na oznaczenie silni dolnej:

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

Podczas gdy w teorii funkcji specjalnych, ten sam zapis oznacza silnię górną. Jeśli ${\displaystyle x}$ i ${\displaystyle n}$ są nieujemnymi liczbami całkowitym, ${\displaystyle 0\leqslant n\leqslant x,}$ to ${\displaystyle (x)_{n}}$ jest liczbą tych funkcji różnowartościowych, które odwzorowują zbiór mocy ${\displaystyle n}$ w zbiór mocy ${\displaystyle x.}$

Niech ${\displaystyle f}$ będzie dowolną funkcją ze zbioru ${\displaystyle A}$ mocy ${\displaystyle n}$ na zbiór ${\displaystyle B}$ mocy ${\displaystyle x.}$ Dla dowolnego ${\displaystyle u\in B,}$ niech ${\displaystyle f^{-1}(u)=\{v\in A\colon f(v)=u\}.}$ Wtedy ${\displaystyle \{f^{-1}(u)\colon u\in B\}}$ jest podziałem zbioru ${\displaystyle A,}$ wprowadzonym przez relacji równoważności „bycia w tym samym włóknie”. Tę relację równoważności nazywa się jądrem funkcji ${\displaystyle f.}$ Dowolna funkcja z ${\displaystyle A}$ do ${\displaystyle B}$ rozkłada się na:

• jedną funkcję która mapuje element A do tej części jądra, do której on należy, oraz
• inną funkcję, która jest koniecznie różnowartościowa, która mapuje jądro w zbiór ${\displaystyle B.}$

Pierwszy z tych dwóch czynników jest całkowicie określony przez podział π, który jest jądrem. Liczba funkcji różnowartościowych z π do ${\displaystyle B}$ jest równa ${\displaystyle (x)_{|\pi |},}$ gdzie ${\displaystyle |\pi |}$ jest liczbą czynników podziału ${\displaystyle \pi .}$ Tak więc łączna liczba funkcji ze zbioru ${\displaystyle A}$ mocy ${\displaystyle n}$ w zbiór ${\displaystyle B}$ mocy ${\displaystyle x}$ jest równa:

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

indeks π przebiega przez zbiór wszystkich podziałów ${\displaystyle A.}$ Z drugiej strony, liczba funkcji z ${\displaystyle A}$ do ${\displaystyle B}$ jest równa ${\displaystyle x^{n}.}$ Stąd wynika:

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

Jeśli ${\displaystyle X}$ jest zmienną losową o rozkładzie Poissona z wartością oczekiwaną 1, wtedy ${\displaystyle n}$-ty moment tego rozkładu prawdopodobieństwa jest dany przez:

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

Ale wszystkie momenty silni ${\displaystyle \mathrm {E} ((X)_{k})}$ tego rozkładu prawdopodobieństwa są równe 1. Zatem:

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

i to jest właśnie liczba podziałów zbioru ${\displaystyle A,}$ q.e.d.

Przypisy

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Dobiński's Formula, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-13]  (ang.).