Wzór Dobińskiego

Wzór Dobińskiego jest wzorem w matematyce kombinatorycznej, który określa liczbę podziałów zbioru n-elementowego:

$B_n={1 \over e}\sum_{k=0}^\infty {k^n \over 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:

${1 \over e}\sum_{k=x}^\infty {k^n \over (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 {k^n \over 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 ilość 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 Rotę.

Kombinatorycy używają symbolu Pochhammera $(x)_n$ na oznaczenie silni dolnej:

$(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 x i n są nieujemnymi liczbami całkowitym, 0≤n≤x, wtedy $(x)_n$ jest liczbą funkcji różnowartościowych, które odwzorowują zbiór mocy n w zbiór mocy x .

Niech ƒ będzie dowolną funkcją ze zbioru A mocy n na zbiór B mocy x. Dla dowolnego u∈B, niech ƒ^-1(u)={v∈A: ƒ(v)=u}. Wtedy {ƒ^-1(u): u ∈ 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 ƒ. 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)_|π|, gdzie |π| jest liczbą czynników podziału π. 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ⁿ. 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 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 ilość podziałów zbioru A, q.e.d.

Linki zewnętrzne

• Wolfram MathWorld: Dobiński's Formula