Formuła Dobińskiego

W matematyce kombinatorycznej wzór Dobińskiego stwierdza, że ​​n -ta liczba Bell B _n (tj. liczba podziałów zbioru o rozmiarze n ) jest równa

$\ Displaystyle B_ {n} = {1 \ ponad e} \ suma _ {k = 0} ^ {\ infty} {\ Frac {k ^ {n}} {k!}}}$

gdzie $Eulera$ liczbę . _ Formuła nosi imię G. Dobińskiego, który opublikował ją w 1877 roku.

Treść probabilistyczna

W układzie rachunku prawdopodobieństwa wzór Dobińskiego reprezentuje n -ty moment rozkładu Poissona ze średnią 1. Czasami formuła Dobińskiego mówi, że liczba podziałów zbioru o rozmiarze n jest równa n- temu momentowi tego rozkładu.

Zredukowana formuła

Obliczenie sumy szeregu Dobińskiego można sprowadzić do skończonej sumy warunków $)}$ biorąc pod uwagę informację, że $n$ jest liczbą całkowitą. Dokładnie jeden ma dla dowolnej liczby całkowitej ${\ Displaystyle K> 1}$

${\ Displaystyle B_ {n} = \ lewo \ lceil {1 \ nad e} \ suma _ {k = 0} ^ {K-1} {\ Frac {k ^ {n}} {k!}} \ prawo \ceil }$

pod warunkiem ${K!}} \ równoważnik 1}$$\ Displaystyle K> n$ (warunek, który oczywiście implikuje ale jest spełniony przez niektórych $} \ Displaystyle K}$ o rozmiarze ${\ Displaystyle n + o (n)}$ ). Rzeczywiście, odkąd ma się ${\ displaystyle K> n}$

${\ Displaystyle {\ Duży (}{\ Frac {K + j} {K}}} {\ Duży)} ^ {n} \ leq {\ Duży (} {\ Frac {K + j} {K}}}}} Big )}^{K}={\Big (}1+{\frac {j}{K}}{\Big )}^{K}\leq {\Big (}1+{\frac {j}{ 1}}{\Big )}{\Big (}1+{\frac {j}{2}}{\Big )}\dots {\Big (}1+{\frac {j}{K}}{ \Big )}={\frac {1+j}{1}}{\frac {2+j}{2}}\dots {\frac {K+j}{K}}={\frac {(K +j)!}{K!j!}}.}$

Dlatego ${\ Displaystyle {\ Frac {(K + j) ^ {n}} {(K + j)!}} \ leq {\ Frac {K ^ {n}} {K!}} {\ Frac {1} j!}} \ leq {\ Frac {1} {j!}}}$ dla wszystkich ${\ Displaystyle j \ geq 0}$ tak, że ogon ${\ Displaystyle \ suma _ {k \ geq K} {\ Frac {k ^ {n}}} {k!}} = \ suma _ {j \ geq 0} {\ frac {(K + j) ^ {n} }{(K+j)!}}}$ jest zdominowane przez szereg ${\ Displaystyle \ suma _ {j \ geq 0} {\ Frac {1} {j!}} = e}$ , co implikuje ${\ Displaystyle 0 <B_ {n} - {\ Frac {1} {e}} \ suma _ {k = 0} ^ {K-1} {\ Frac {k ^ {n}} {k!} }<1}$ , stąd zredukowana formuła.

Uogólnienie

Formułę Dobińskiego można postrzegać jako szczególny przypadek bardziej ogólnej relacji: ${\ displaystyle x = 0}$

${\ Displaystyle {1 \ nad e} \ suma _ {k = x} ^ {\ infty} {\ Frac {k ^ {n}} {(kx)!}} = \ suma _ {k = 0} ^ { n}{\binom {n}{k}}B_{k}x^{nk}.}$

Dowód

Jeden dowód opiera się na wzorze funkcji generującej liczby Bella ,

${\ Displaystyle e ^ {e ^ {x} -1} = \ suma _ {n = 0} ^ {\ infty} {\ Frac {B_ {n}} {n!}} x ^ {n}.}$

Szeregi potęgowe dla wykładniczych daje

${\ Displaystyle e ^ {e ^ {x}} = \ suma _ {k = 0} ^ {\ infty} {\ Frac {e ^ {kx}} {k!}} = \ suma _ {k = 0} ^{\infty}{\frac {1}{k!}}\sum _{n=0}^{\infty}{\frac {(kx)^{n}}{n!}}}$

Więc

${\ Displaystyle e ^ {e ^ {x} -1} = {\ Frac {1} {e}} \ suma _ {k = 0} ^ {\ infty} {\ Frac {1} {k!}} \ suma _{n=0}^{\infty}{\frac {(kx)^{n}}{n!}}}$

Współczynnik w ${\ Displaystyle B_ {n} / n!}$$!$ musi wynosić , więc

${\ Displaystyle B_ {n} = {\ Frac {1} {e}} \ suma _ {k = 0} ^ {\ infty} {\ Frac {k ^ {n}} {k!}}.}$

Rota podał inny styl dowodu . Przypomnijmy, że jeśli x i n są nieujemnymi liczbami całkowitymi, to liczba funkcji jeden do jednego , które odwzorowują zbiór rozmiarów- n na zbiór rozmiarów- x , jest silnią opadającą

${\ Displaystyle (x) _ {n} = x (x-1) (x-2) \ cdots (x -n+1)}$

Niech ƒ będzie dowolną funkcją ze zbioru rozmiar- n A do zbioru rozmiar- x B . Dla dowolnego b ∈ b , niech ƒ ⁻¹ ( b ) = { za ∈ ZA : ƒ ( za ) = b }. Wtedy { ƒ ⁻¹ ( b ) : b ∈ B } jest podziałem A . Rota nazywa tę partycję „ jądrem ” funkcji ƒ . Każda funkcja z A do B rozkłada się na

• jedna funkcja, która odwzorowuje element A na element jądra, do którego należy, oraz
• inna funkcja, która jest koniecznie jeden do jednego, która odwzorowuje jądro na B .

Pierwszy z tych dwóch czynników jest całkowicie określony przez podział π , czyli jądro. Liczba funkcji jeden do jednego od π do B wynosi ( x ) _{| π |} , gdzie | π | jest liczbą części w podziale π . Zatem całkowita liczba funkcji ze zbioru rozmiar- n A do zbioru rozmiar- x B wynosi

$\ Displaystyle \ suma _ {\ pi} (x) _ {|\ pi |},}$

indeks π biegnący przez zbiór wszystkich partycji A . Z drugiej strony liczba funkcji z A do B wynosi wyraźnie x ⁿ . Dlatego mamy

${\ Displaystyle x ^ {n} = \ suma _ {\ pi} (x) _ {|\ pi |}.}$

Rota kontynuuje dowód za pomocą algebry liniowej, ale pouczające jest wprowadzenie zmiennej losowej X o rozkładzie Poissona ze średnią 1. Z powyższego równania wynika, że ​​n- tym momentem tej zmiennej losowej jest

${\ Displaystyle E (X ^ {n}) = \ suma _ {\ pi} E ((X) _ {|\ pi |})}$

gdzie E oznacza wartość oczekiwaną . Ale pokażemy, że wszystkie wielkości E (( X ) _k ) są równe 1. Wynika z tego

${\ Displaystyle E (X ^ {n}) = \ suma _ {\ pi} 1,}$

a to jest po prostu liczba podziałów zbioru A .

Wielkość E (( X ) _k ) nazywana jest k- tym momentem silni zmiennej losowej X . Aby pokazać $,$ że jest to równe 1 dla wszystkich k gdy X jest zmienną losową o rozkładzie Poissona ze średnią 1, przypomnijmy, że ta zmienna losowa przyjmuje każdą wartość całkowitą wartość z ${\ Displaystyle 1 / (ej!)}$ . Zatem

${\ Displaystyle E ((X) _ {k}) = \ suma _ {j = 0} ^ {\ infty} {\ Frac {(j) _ {k}} {ej!}} = {\ frac {1}{e}}\sum _{j=0}^{\infty}}{\frac {j(j-1)\cdots (j-k+1)}{j(j-1)\cdots 1}}={\frac {1}{e}}\sum _{j=i}^{\infty}{\frac {1}{(ji)!}}=1.}$