Wzór Dobińskiego – w kombinatoryce wzór wyrażający liczbę podziałów zbioru -elementowego[1]:
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ę[2].
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
- ↑ G. Dobiński. Der Reihe Summirung für = 1, 2, 3, 4, 5, .... „Grunert’s Archiv”. 61 (1877). s. 333–336.
- ↑ Gian-Carlo Rota. The Number of Partitions of a Set. „American Mathematical Monthly”. 71 (5), s. 498–504, maj 1964.
Linki zewnętrzne
- Eric W. Weisstein , Dobiński’s Formula, [w:] MathWorld, Wolfram Research [dostęp 2020-12-13] (ang.).