Matematické Fórum

Andrejka3

Dobrý den.
Počet všech ekvivalencí $n$ prvkové množiny (n-té Bellovo číslo) mi vyšel
$B_n=\sum_{k=0}^{n} \frac{1}{k!} \sum_{j=0}^{k} (-1)^j {k \choose j} (k-j)^n$ .
Mám ověřit, že
$B_n=\frac{1}{e} \sum_{i=0}^{\infty} \frac{i^n}{i!}$ . (původně chyba - bylo n! ve jmenovateli.)

Příklad pochází z knížky Kapitoly z diskrétní matematiky, autorů Nešetřil, J. ; Matoušek, J., 4. vydání.
Cituji návod z knihy:

Autor skryl část textu. Zobrazit/skrýt!

Návodu nerozumím. Mohl by mi, prosím, někdo ukázat, jak se to dělá?

vanok · 30. 06. 2012 15:51

Ahoj ↑ Andrejka3:,
Tvoj vzorec je dokazany v tomto prispevku
http://en.wikipedia.org/wiki/Dobinski%27s_formula

Andrejka3 · 30. 06. 2012 16:00

↑ vanok:
Díky.
V druhém vzorci ve wikipedii je drobný přepis, že? V levé sumě se sčítá od nuly?
Jinak, používají se tam věci, kterým nerozumím, ale jsem ráda, že vím, odkud to pochází.

vanok · 06. 07. 2012 12:46 — Editoval vanok (09. 07. 2012 12:12)

Ahoj,
Ten dokaz sa da urobit aj takto.
Vieme, ze $B_n$ je pocet particii $n$ prvkovej mnoziny ( co je to iste ako pises "Počet všech ekvivalencí $n$ prvkové množiny")
Nie je tazke ukazat ze mame tuto recurentnu relaciu:
Pre kazde $n \in \mathbb{N}^*$ : $B_{n+1}= \sum_{k=0}^{n} {n \choose k} B_k$
Dohodou polozme $B_0=1$

Autor skryl část textu. Zobrazit/skrýt!

Teraz treba ukazat:
$B_n=\frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}$
Ako prve treba overit, ze rada
$S_n=\frac{1}{e} \sum_{k=0}^n{n \choose k}\sum_{p=0}^{\infty} \frac{p^k}{p!}$ konverguje.
To sa moze ukazat vdaka D'Alembert-ovmu testu.
Hladajme teraz, rekurecnu relaciu ktora plati pre $S_n$

Autor skryl část textu. Zobrazit/skrýt!

Toto znamena ze $S_{n+1}= \sum_{k=0}^{n} {n \choose k} S_k$
Takze pre $S_n$ a $B_n$ plati

Autor skryl část textu. Zobrazit/skrýt!

Konkluzia:
$S_n=B_n$ co je hladany vyrok.

Edit:oprava preklepov.

Andrejka3

↑ vanok:
Díky, moc hezky napsané. Ještě chvíli na zpracování...

V prvním příspěvku mám chybu. Mám dokázat, že
$B_n=\frac{1}{e}\sum_{i=0}^{\infty}\frac{i^n}{i!}$
v sumě jsem psala ve jmenovateli chybně $n!$ .

Rekurentní vztah pro Bellova čísla je hezký a důkaz taky :)
Budu pokračovat dál.

$C_k=\frac{1}{e}\sum_{p=0}^{\infty}\frac{p^k}{p!}$ , chci dokázat, že
$\sum_{k=0}^{n}{n \choose k} C_k=C_{n+1}$ pro $n \in \mathbb{N}^{*}$ a $C_0=1$ .
Je $C_0=1$ a
$\sum_{k=0}^{n}{n \choose k} C_k=\frac{1}{e} \sum_{p=0}^{\infty}\frac{(p+1)^{n+1}}{(p+1)!}=C_{n+1}$ . Poslední rovnost mě mátla, protože jsem si neuvědomila, že $0^{n+1}=0$ .

Ještě to projdu a pokud uvidím nějaké překlepy, pošlu opravu (nedivila bych se, když jsem měla chybně zadání).
Opravy?

Autor skryl část textu. Zobrazit/skrýt!

Tak a je to :)
Díky a hezký den.

vanok · 09. 07. 2012 12:19

↑ Andrejka3:

Poznamka o tejto rovnosti:
$\frac{1}{e} \sum_{p=0}^{\infty} \frac {(1+p)^n}{p!}= \frac{1}{e} \sum_{p=0}^{\infty} \frac{(1+p)^{n+1}}{(p+1)!}$

Treba si uvedomit, ze ide len o nasobenie jednotkou $\frac {p+1}{p+1}$

Inac som opravil, dufam vsetki male preklepy.

Andrejka3 · 09. 07. 2012 15:05

↑ vanok:
Ano, už to chápu a další překlepy nevidím.

Matematické Fórum

#1 30. 06. 2012 15:39 — Editoval Andrejka3 (08. 07. 2012 14:02)

Bellovo číslo, úprava sumy

#2 30. 06. 2012 15:51

Re: Bellovo číslo, úprava sumy

#3 30. 06. 2012 16:00

Re: Bellovo číslo, úprava sumy

#4 06. 07. 2012 12:46 — Editoval vanok (09. 07. 2012 12:12)

Re: Bellovo číslo, úprava sumy

#5 08. 07. 2012 10:37 — Editoval Andrejka3 (08. 07. 2012 16:55)

Re: Bellovo číslo, úprava sumy

#6 09. 07. 2012 12:19

Re: Bellovo číslo, úprava sumy

#7 09. 07. 2012 15:05

Re: Bellovo číslo, úprava sumy

Zápatí