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

Liczbę nazywa się -tą liczbą Bella na cześć Erica Temple Bella.

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

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

Treść probabilistyczna Wyrażenie dane przez wzór Dobińskiego jest -tym momentem rozkładu Poissona z wartością oczekiwaną 1. Innymi słowy, wzór Dobińskiego stwierdza, że liczba podziałów zbioru mocy jest równa -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 na oznaczenie silni dolnej:

podczas gdy w teorii funkcji specjalnych ten sam zapis oznacza silnię górną. Jeśli i są nieujemnymi liczbami całkowitym, to jest liczbą tych funkcji różnowartościowych, które odwzorowują zbiór mocy w zbiór mocy

Niech będzie dowolną funkcją ze zbioru mocy na zbiór mocy Dla dowolnego niech Wtedy jest podziałem zbioru 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 do 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

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 jest równa gdzie jest liczbą czynników podziału Tak więc łączna liczba funkcji ze zbioru mocy w zbiór mocy jest równa:

indeks π przebiega przez zbiór wszystkich podziałów Z drugiej strony liczba funkcji z do jest równa Stąd wynika:

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

Ale wszystkie momenty silni tego rozkładu prawdopodobieństwa są równe 1. Zatem:

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

Przypisy

Linki zewnętrzne

Kategoria:Twierdzenia kombinatoryki