Matematické Fórum

Kein · 02. 12. 2009 17:59

Zdravím...

Mám jeden příklad, ale úplně si nejsem jist mým výsledkem...

Zadání zní:

Nechť $r,m,n \in N$ , $r \le m \le n$ . Dokažte, že platí ${m+n \choose r} = \sum_{k=0}^{r} {m \choose k} \cdot {n \choose r-k}$

Poté co jsem rozepsal sumu mi vyšlo:

${m \choose k} \cdot {n \choose r-k}+{m \choose k+1} \cdot {n \choose r-(k+1)}+...+{m \choose r}{n \choose r-r}={m+n \choose r}$

Tedy že se levá strana rovná pravé.

Tychi · 02. 12. 2009 19:27 — Editoval Tychi (02. 12. 2009 19:27)

↑ Kein:Tu sumu musíš rozepsat bez k. Tedy ${m \choose 0} \cdot {n \choose r-0}+{m \choose 1} \cdot {n \choose r-(1)}+...+{m \choose r}{n \choose r-r}$

Kein · 03. 12. 2009 16:04

↑ Tychi: Děkuji za upozornění...

Avšak měl bych ještě jeden dotaz ohledně kombinatoriky...

Měl bych takovéto zadání:

Pro $n \ge r$ přirozená čísla dokažte vzorec:

${r \choose r}+{r+1 \choose r}+...+{n-1 \choose r}+{n \choose r}={n+1 \choose r+1}$

Kombinatorika není zrovna můj "šálek kávy", nicméně šel jsem na to takto:

Definoval jsem si pevné $r=1$ a dal dohromady sumu $\sum_{i=r}^{n} {i \choose r}$ .

Pak jsem se to pokusil ověřit z principu matematické indukce:

$\sum_{i=r}^{n+1} {i \choose r} = \left ( \sum_{i=r}^{n} {i \choose r} \right )+{n+1 \choose r}={n+1 \choose r}+{n+1 \choose r+1}={n+2 \choose r+1}$

Chtěl bych se vás zeptat, zda je můj postup správný, nebo zda je to naprostá slátanina. Předem děkuji za případnou pomoc.

Kein · 03. 12. 2009 23:05

Připadám si trochu trapně, ale opravdu by mi nedokázal nikdo poradit?

Prohledal jsem zde skoro celé forum, ale nenašel jsem nic, co by mi pomohlo.

petrkovar

↑ Kein:To, co tu máš vyřešeno, je vlastně indukční krok. Ještě chybí základ indukce: ukázat platnost vztahu pro n=r.
Bonus: existuje i jiný postup. pokud si všimneme, že ${r\choose r} = 1 = {r+1 \choose r+1}$ , tak se tvrzení dá dokázat přímo opakovaným užitím kombinatorické identity ${a \choose b} + {a\choose b+1} = {a+1 \choose b+1}$ (tato identita se dobře pamatuje tak, že popisuje konstrukci Pascalova trojúhelníka).

Kein · 03. 12. 2009 23:36

↑ petrkovar: Děkuji za reakci :-)

Pokud jsem to pochopil dobře, je tedy můj postup správně - tedy to ověření indukčního předpokladu - pravda ten základ tam napsaný nemám.

add Bonus: S tou kombinatorikou nejsem ještě tak daleko, abych plně dokázal pochopit to znění, nicméně zítra se na to juknu a ještě na tý kombinatorice zapracuju.

Kein · 15. 12. 2009 18:43

Dostal jsem se k tomuto příkladu opět až nyní a chtěl bych se jen zeptat...

1. ${a \choose b} + {a+1 \choose b} = {a+1 \choose b+1}$ nemělo by toto být spíše ${a \choose b} + {a \choose b+1} = {a+1 \choose b+1}$

2. Jak by se dal definovat součet řady např. ${1 \choose 1}+{2 \choose 1}+{3 \choose 1}={4 \choose 2}$ z toho Pascalova trojúhelníku?

zdenek1 · 15. 12. 2009 19:05

↑ Kein:
Ke 2. Pomůže obrázek?

Kein · 15. 12. 2009 19:12

↑ zdenek1: obrázek určitě pomůže... a existuje pro toto i formální definice?

zdenek1 · 15. 12. 2009 20:16

↑ Kein:

Je to ta pětka. A dokazuje se to např. matematickou indukcí.

Kein · 15. 12. 2009 20:41

Matematickou indukci jsem pro toto použil, ale pohořel jsem a nemám ponětí, kde jsem udělal chybu, viz zadání i postup výše..

zdenek1 · 15. 12. 2009 21:08

↑ Kein:
1. Ověříme, že platí pro $n=k$
${k\choose k}={k+1\choose k+1}\Rightarrow\ 1=1$ platí
2. předpokládáme, že platí pro $n$
${k\choose k}+{k+1\choose k}+\dots+{n\choose k}={n+1\choose k+1}$
3. Dokážeme, že platí pro $n+1$
${k\choose k}+{k+1\choose k}+\dots+{n\choose k}+{n+1\choose k}={n+1\choose k+1}+{n+1\choose k}$ ale to je podle (4)
${n+2\choose k+1}$ . A to jsme měli dokázat.

Když budeš chtít být úplně košer, nejdřív si dokážeš (4).

Kein · 15. 12. 2009 21:15

Aha...mno mě tam chyběla ta první část... n=k...druhé dvě mám dle tebe správně...

petrkovar · 16. 12. 2009 08:12

↑ Kein:Samozrejme to byla moje chyba, už jsem to opravil.

Kein · 18. 12. 2009 01:03

↑ zdenek1: Ještě jsem si všimnul, že v tom mém vzorci jsem měl při dokazování špatně proveden součet kombinačních čísel.

↑ petrkovar: Stane se

Každopádně bych vám chtěl ještě jednou poděkovat za pomoc při řešení.

Matematické Fórum

#1 02. 12. 2009 17:59

Kombinatorika

#2 02. 12. 2009 19:27 — Editoval Tychi (02. 12. 2009 19:27)

Re: Kombinatorika

#3 03. 12. 2009 16:04

Re: Kombinatorika

#4 03. 12. 2009 23:05

Re: Kombinatorika

#5 03. 12. 2009 23:13 — Editoval petrkovar (16. 12. 2009 08:10)

Re: Kombinatorika

#6 03. 12. 2009 23:36

Re: Kombinatorika

#7 15. 12. 2009 18:43

Re: Kombinatorika

#8 15. 12. 2009 19:05

Re: Kombinatorika

#9 15. 12. 2009 19:12

Re: Kombinatorika

#10 15. 12. 2009 20:16

Re: Kombinatorika

#11 15. 12. 2009 20:41

Re: Kombinatorika

#12 15. 12. 2009 21:08

Re: Kombinatorika

#13 15. 12. 2009 21:15

Re: Kombinatorika

#14 16. 12. 2009 08:12

Re: Kombinatorika

#15 18. 12. 2009 01:03

Re: Kombinatorika