Dôkaz matematickou indukciou

Dôkaz matematickou indukciou

• Dôkaz matematickou indukciou

• N – faktoriál

• Kombinačné čísla

• Pascalov trojuholník

• Binomická veta

• K-ty člen binomického rozvoja

• Definičné obory

• Úvod do kombinatoriky

• Kombinačné úlohy

• Variácie

• Permutácie

• Kombinácie

• Variácie s opakovaním

• Permutácie s opakovaním

• Kombinácie s opakovaním

• Pravidlo súčtu

• Pravidlo súčinu

Využívame pre mat. vety, kt. treba dokázať alebo pre prir. čísla od nejakého

• Využívame pre mat. vety, kt. treba dokázať alebo pre prir. čísla od nejakého

• Dôkaz mat. indukciou pozostáva z 2 krokov:

• Vetu dokážeme pre prvé prirodzené číslo
• Indukčný krok
• Z predpokladu, že veta platí pre n=k dokážeme platnosť vety

Využíva sa pri výpočtoch v kombinatorických úlohách

• Využíva sa pri výpočtoch v kombinatorických úlohách

• Definujeme ho ako

• Vyjadrenie niektorých n!

Kombinačné číslo

• Kombinačné číslo

• Majú niekoľko základných vlastností:

• Pre každé platí:
• Pre každé platí:
• Pre každé platí:
• Určitá vlastnosť umožňuje vypočítať kombinačné čísla len za pomoci sčítavania, bez vyčísľovania faktoriálov.

• Často sa vyskytujú v kombinatorike.

Je zostavený z kombinačných čísel.

• Je zostavený z kombinačných čísel.

• V tejto schéme sa všetky krajné čísla rovnajú 1 a každé ďalšie číslo sa rovná súčtu dvoch čísel bezprostredne nad ním, využívame 3 základnú vlastnosť a to:

• Pascalov trojuholník má zvislú os súmernosti.

• Číslo na k-tom mieste v n-tom riadku má hodnotu

Kombinačné čísla majú ešte množstvo zaujímavých vlastností.

• Kombinačné čísla majú ešte množstvo zaujímavých vlastností.

• Jedna z nich vyplýva z binomickej vety:

Čísla v jednom riadku Pascalovho trojuholníka sú vlastne koeficienty rozvoja pre odpovedajúce n.

• Čísla v jednom riadku Pascalovho trojuholníka sú vlastne koeficienty rozvoja pre odpovedajúce n.

• Binomický rozvoj má sčítancov.

• Pre k-ty člen binomického rozvoja platí:

Pre n-faktoriál

• Pre n-faktoriál

• Vyjadruje sa z najmenšieho n-faktoriálu
• n≥ 0

• Pre kombinačné čísla

• V kombinačnom čísle musí byť n väčšie rovné k
• n ≥k

Kombinatorika:

• Kombinatorika:

• Je oblasť matematiky, ktorá sa zaoberá riešením úloh typu:

• „Koľkými spôsobmi možno vybrať isté objekty? ”
• „ Koľkými spôsobmi možno usporiadať isté objekty? ”
• „ Koľkými spôsobmi zoradiť isté objekty? ”

• Ponúka niekoľko pravidiel na riešenie jednoduchých úloh:

• Pravidlo súčtu.
• Pravidlo súčinu.

• Ak sa vyskytnú zložitejšie, je treba si ich rozdeliť na jednoduché podúlohy.

Delíme na 6 základných typov:

• Delíme na 6 základných typov:

• Permutácie
• Kombinácie
• Variácie
• Permutácie s opakovaním
• Kombinácie s opakovaním
• Variácie s opakovaním

Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• „Koľkými spôsobmi možno spomedzi n rôznych objektov vybrať k objektov, ak záleží na poradí vyberania?“
• „Koľko usporiadaných k-tic možno vytvoriť z n prvkov?“

• Každú usporiadanú k-ticu z daných n prvkov nazývame k-prvkovou variáciou z n prvkov.

• Počet všetkých takýchto variácií označujeme V(k,n)

• Platí:

Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• „Koľkými spôsobmi možno zoradiť do radu prvky neprázdnej konečnej n-prvkovej množiny? ”

• Každé jedno zoradenie nazývame permutáciou (poradím) prvkov danej množiny.

• Permutácie možno reprezentovať usporiadanými n-ticami prvkov danej n-prvkovej množiny.

• Počet všetkých permutácií n prvkov označujeme P(n).

• Pre ich počet platí:

Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• „ Koľkými spôsobmi možno spomedzi n rôznych objektov vybrať objektov, ak nezáleží na poradí vyberania? ”
• „ Koľko k-prvkových množín má n-prvková množina? ”

• Každý jeden výber k prvkov z daných n-prvkov nazývame k-prvkovou kombináciou z n-prvkov.

• Keďže nezáleží na poradí vyberania, možno kombinácie chápať ako neusporiadané k-tice, t.j. k-prvkové podmnožiny.

• Počet k-prvkových kombinácií z n prvkov označujeme

• Pre ich počet platí:

Základný typ kombinačnej úloh, ktorá rieši úlohy typu:

• Základný typ kombinačnej úloh, ktorá rieši úlohy typu:

• “Koľkými spôsobmi možno z daných n objektov vybrať k objektov, ak záleží na poradí vyberania a pripúšťame, že objekty môžu byť vybraté viackrát?“

• Každý taký výber nazývame k-prvkovou variáciou s opakovaním z n prvkov a ich celkový počet označujeme V’(k, n).

• Platí:

Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• Základný typ kombinačnej úlohy, ktorá rieši úlohy typu:

• Majme n1 objektov prvého druhu, n2 objektov druhého druhu, ... atď. ak nk objektov k-teho druhu tak koľkými spôsobmi možno týchto n1 + n2 + ... + nk objektov usporiadať do radu?“

• Každé také usporiadanie nazývame permutáciou s opakovaním, ich celkový počet označujeme

• Počítame ho zo vzorca:

Základný typ kombinačnej úlohy ktorá rieši úlohy typu:

• Základný typ kombinačnej úlohy ktorá rieši úlohy typu:

• Koľkými spôsobmi môžeme z daných n objektov vybrať k objektov, ak nezáleží na poradí vyberania a pripúšťame, že objekty môžu byť vybraté viackrát?“

• Každý z možných výberov nazývame k-prvkovou kombináciou s opakovaním z n prvkov.

• Ich celkový počet označujeme K’(k, n)

• Počítame podľa vzorca:

Ak je úlohou zistiť počet prvkov nejakej množiny M, môžeme množinu M rozložiť na niekoľko disjunktných podmnožín M = M1  M2  …  Mk a určiť počty prvkov množín Mi.

• Ak je úlohou zistiť počet prvkov nejakej množiny M, môžeme množinu M rozložiť na niekoľko disjunktných podmnožín M = M1  M2  …  Mk a určiť počty prvkov množín Mi.

• Potom platí: |M| = |M1| + |M2| + ... + |Mk|

Predpokladáme, že máme vybrať dva prvky a, b, pričom prvý vyberáme z konečnej neprázdnej množiny A a druhý z konečnej neprázdnej množiny B.

• Predpokladáme, že máme vybrať dva prvky a, b, pričom prvý vyberáme z konečnej neprázdnej množiny A a druhý z konečnej neprázdnej množiny B.

• V prípade, že výber prvku b nezávisí od výberu prvku a, je spolu |A|.|B| možností, ako vybrať tieto dva prvky.