Wzór Dobińskiego

Wzór Dobińskiego – w kombinatoryce wzór wyrażający liczbę podziałów zbioru $n$-elementowego:

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

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

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

${\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:

$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 $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 $n$ jest równa $n$-temu momentowi tego rozkładu.

Dowód

Dowód podany tu jest adaptacją do probabilistycznego języka dowodu danego przez Gian-Carlo Rotę.

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

$(x)_{n}=x(x-1)(x-2)\dots (x-n+1),$

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

Niech $f$ będzie dowolną funkcją ze zbioru $A$ mocy $n$ na zbiór $B$ mocy $x.$ Dla dowolnego $u\in B,$ niech $f^{-1}(u)=\{v\in A\colon f(v)=u\}.$ Wtedy $\{f^{-1}(u)\colon u\in B\}$ jest podziałem zbioru $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 $f.$ Dowolna funkcja z $A$ do $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 $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 $B$ jest równa $(x)_{|\pi |},$ gdzie $|\pi |$ jest liczbą czynników podziału $\pi .$ Tak więc łączna liczba funkcji ze zbioru $A$ mocy $n$ w zbiór $B$ mocy $x$ jest równa:

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

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

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

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

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

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

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

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

Linki zewnętrzne

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