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

  1. G. Dobiński. Der Reihe Summirung für = 1, 2, 3, 4, 5, .... „Grunert’s Archiv”. 61 (1877). s. 333–336.
  2. Gian-Carlo Rota. The Number of Partitions of a Set. „American Mathematical Monthly”. 71 (5), s. 498–504, maj 1964.

Linki zewnętrzne

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.