Wzór Dobińskiego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

B_n={1 \over e}\sum_{k=0}^\infty {k^n \over k!}.

Liczbę Bn 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Dowód podany tu jest adaptacją do probabilistycznego języka dowodu danego przez Rotę[2].

W kombinatoryce używa się 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≤nx, to (x)n jest liczbą tych 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 uB, niech ƒ-1(u) = {vA: ƒ(v) = u}. Wtedy {ƒ-1(u): uB} 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 xn. 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 liczba podziałów zbioru A, q.e.d.

Przypisy

  1. G. Dobiński. Der Reihe Summirung \textstyle\sum\frac{n^m}{n!} für m = 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[edytuj | edytuj kod]