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}^{\mathrm{\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}^{\mathrm{\infty }}\frac{k^n}{(k-x)!}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{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}^{\mathrm{\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⩽n⩽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:f(v)=u\}.$ Wtedy $\{f^{-1}(u):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

• Szablon:MathWorld