Matematické Fórum

vanok · 18. 07. 2015 14:40 — Editoval vanok (19. 07. 2015 14:51)

Pozdravujem,
Pekne prazdninove cvicenie, ktore ma viac casti.
Tak 2 prve:
Nech k,l,n su cele kladne cisla $l \le k \le n$
1. Dokazte, ze $\binom {n}{k} \binom {k}{l}=\binom {n}{l} \binom {n-l}{k-l}$
2. Dokazte vdaka 1. ze pre $l < n, \sum_{k=l}^{n}(-1)^k \binom {n}{k} \binom {k}{l}=0$

vanok · 19. 07. 2015 14:04

Dokaz 1. je velmi jednoduchy.
Staci rozpisat lavy a pravy clen rovnosti a porovnat.

$\binom {n}{k} \binom {k}{l}=\frac {n!}{k!(n-k)!}\frac {k!}{l!(k-l)!}=\frac {n!}{(n-k)!l!(k-l)!}$
$\binom {n}{l} \binom {n-l}{k-l}=\frac {n!}{l!(n-l)!}\frac {(n-l)!}{(k-l)!(n-k)!}=\frac {n!}{l!(k-l)!(n-k)!}$

a dokaz 2. ?

Al1 · 19. 07. 2015 14:26 — Editoval Al1 (19. 07. 2015 14:29)

↑ vanok:

Zdravím,

podmínka pro daná kombinační čísla $k \le l \le n$ je zadaná chybně, kombinační číslo $\binom {k}{l}$ neexistuje, pokud $l>k$ , existuje při $l\le k$

vanok · 19. 07. 2015 14:54

↑ Al1:
Ahoj, preklep opraveny.
Dakujem.
Ak mas chut mozes aj pokracovat v dokazoch.
Pekny WE.

check_drummer · 21. 07. 2015 00:44

↑ vanok:
Ahoj, ad 2) použít 1, vhodně vytknout, přeindexovat a aplikovat (1-1)^k.

vanok · 21. 07. 2015 21:02 — Editoval vanok (22. 07. 2015 09:33)

↑ check_drummer:
Ahoj, ano aj ja som postupoval presne ako ty.
Napisem tu, pre kolegov stredoskolakov, podrobne dokaz

$\sum_{k=l}^{n}(-1)^k \binom {n}{k} \binom {k}{l}= \sum_{k=l}^{n}(-1)^k \binom {n}{l} \binom {n-l}{k-l}=$
vdaka 1.
$\binom {n}{l} \sum_{k=l}^{n}(-1)^k \binom {n-l}{k-l}=$
zmena premennej j=k-l da

$\binom {n}{l} \sum_{j=0}^{n-l}(-1)^{j+l} \binom {n-l}{j}=$

$(-1)^l\binom {n}{l} \sum_{j=0}^{n-l}(-1)^j \binom {n-l}{j}=$
a na koniec binomicka veta da
$(-1)^l \binom {n}{l}(1-1)^{n-l}=0$
lebo $n-l>0$
.............
Teraz; dufam, ze ste schopni dokazat
3. Nech $(a_n), (b_n)$ su dve realnepostupnosti take, ze
$\forall \in \mathbb{N}, b_n=\sum _{k=0}^{n} \binom {n}{k} a_k$ .
Potom
$\forall \in \mathbb{N}, a_n=(-1)^n\sum _{k=0}^{n} (-1)^k\binom {n}{k} b_k$ .

Poznamka: Posledny vzorec je znamy pod menom Pascal-ov inverzny vzorec.

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

vanok · 23. 07. 2015 14:10 — Editoval vanok (23. 07. 2015 16:44)

Dokaz vlasnosti 3. je celkom jednoduchy. (tento sa najde na wikipedii)

$\begin{align} (-1)^n \sum_{k=1}^n (-1)^k {n \choose k} b_k = (-1)^n \sum_{k=0}^n (-1)^k {n \choose k} \sum_{i=0}^k {k \choose i} a_i \\ = (-1)^n \sum_{k=0}^n \sum_{i=0}^k (-1)^k {n \choose k} {k \choose i} a_i \\ = (-1)^n \sum_{0 \le i \le k \le n} (-1)^k {n \choose k} {k \choose i} a_i \\ = (-1)^p \sum_{i=0}^n a_i \sum_{k=i}^n (-1)^k {n \choose k} {k \choose i} \\ \end{align}$

v poslednom vyraze skoro vsetki sucty su nulove, az pre $i=n\,,$ tak ostane len $(-1)^n \times a_n \times (-1)^n \times {n \choose n} {n\choose n}$

Co je presne $a_n$

Pripominam pouzite oznacenie v tomto vlakne

$\mathbb{N}= \{0; 1; 2;3; ....\}$
ako aj
$\mathbb{N}^*= \{1;2;3;... \}$

Poznamka: iny mozny dokaz je idukciou, a jeden iny ( nestredoskolsky) dokaz, pouziva matice. (a iste su zname aj dalsie...)

Dalsiu vlasnost, co pouzije vlasnost 3. sa tyka permutacii.
Vlasnost 4.
Oznacme $N_n$ pocet permutacii n prvkovej mnoziny ktore nemaju ziadny pevny bod.
Preto pochopitelne mame $n! = \sum_{k=0}^n{n\choose k}N_k$
Dokazte, ze vdaka vlasnosti 3. mame $N_n = n!\sum_{k=0}^n\frac{(-1)^k}{k!}$

vanok · 28. 07. 2015 21:16

pozdravujem,
Tak tu je cakany dokaz vlasnosti 4.
Pascal-ov inverzny vzorec nam da :

$N_n= \sum_{k=0}^n {n \choose k} (-1)^{n-k} k!$

co je po uprave

$N_n = n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ .

Nadherne, ze.

Dalsie mozne pouzitia vlasnosti 3. iste najdete sami.
Na priklad vycislenie poctu surjekcii p prvkovej mnoziny do n prvkovej mnoziny.

Matematické Fórum

#1 18. 07. 2015 14:40 — Editoval vanok (19. 07. 2015 14:51)

kombinatoricke identity

#2 19. 07. 2015 14:04

Re: kombinatoricke identity

#3 19. 07. 2015 14:26 — Editoval Al1 (19. 07. 2015 14:29)

Re: kombinatoricke identity

#4 19. 07. 2015 14:54

Re: kombinatoricke identity

#5 21. 07. 2015 00:44

Re: kombinatoricke identity

#6 21. 07. 2015 21:02 — Editoval vanok (22. 07. 2015 09:33)

Re: kombinatoricke identity

#7 23. 07. 2015 14:10 — Editoval vanok (23. 07. 2015 16:44)

Re: kombinatoricke identity

#8 28. 07. 2015 21:16

Re: kombinatoricke identity

Zápatí