Cvičení z kombinatoriky Rekurence, opakovaní 3. 12. 2018 MA2BP_CKOM 9. cvičení 3. 12. 2018 Rekurence Rekurentní formule MA2BP_CKOM 9. cvičení 3. 12. 2018 2 /6 Rekurence Rekurentní formule MA2BP_CKOM 9. cvičení 3. 12. 2018 2 /6 Rekurence Rekurentní formule recurrere - vracet se rekurentní formule/rekurence /-tého řádu ... n-tý člen závisí na předchozích / členech; prvních / členů je třeba definovat, další členy lze dopočítat rekurentní formulí MA2BP_CKOM 9. cvičení 3. 12. 2018 2 /6 Rekurence Rekurentní formule recurrere - vracet se rekurentní formule/rekurence /-tého řádu ... n-tý člen závisí na předchozích / členech; prvních / členů je třeba definovat, další členy lze dopočítat rekurentní formulí sn = 2sn-i — 3sn-3] si = 2, S2 = 5, S3 = —3 - rekurence 3. řádu MA2BP_CKOM 9. cvičení 3. 12. 2018 2 /6 Rekurence Rekurentní formule recurrere - vracet se rekurentní formule/rekurence /-tého řádu ... n-tý člen závisí na předchozích / členech; prvních / členů je třeba definovat, další členy lze dopočítat rekurentní formulí sn = 2sn-i — 3sn-3] si = 2, S2 = 5, S3 = —3 - rekurence 3. řádu fn = fn-i + fn-2\ h — 1, h — 2 - rekurence 2. řádu (Fibonacciho posloupnost) MA2BP_CKOM 9. cvičení 3. 12. 2018 2 /6 Rekurence Rekurentní formule recurrere - vracet se rekurentní formule/rekurence /-tého řádu ... n-tý člen závisí na předchozích / členech; prvních / členů je třeba definovat, další členy lze dopočítat rekurentní formulí sn = 2sn-i — 3sn-3] si = 2, S2 = 5, S3 = —3 - rekurence 3. řádu fn = fn-i + fn-2\ h — 1, h — 2 - rekurence 2. řádu (Fibonacciho posloupnost) V uvedených příkladech lze jednoduše dopočítat např. hodnoty S4 = —12, S5 = —39, ..., sio = 372, ... resp. h — 3, U — 5, /~5 = 8, ... fio = 89, ... MA2BP_CKOM 9. cvičení 3. 12. 2018 2 /6 Příklady MA2BP_CK0M 9. cvičení 3. 12. 2018 3 /6 Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat si MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat si=l, MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat si=l, s2 MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat Si = l, 52=2(1 + 1,2), MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat si=l, s2=2 (1+1, 2), s3 MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat Sl=l, s2=2 (1+1, 2), s3=4 (1+1+1, 1+2, 2+1, 3). MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat Sl=l, s2=2 (1+1, 2), s3=4 (1+1+1, 1+2, 2+1, 3). S4 = 53 + 52 + Si MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat Sl=l, s2=2 (1+1, 2), s3=4 (1+1+1, 1+2, 2+1, 3). 54 = s3 + s2 + si = 4 + 2 + 1 = 7 MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 Příklady Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat Sl=l, s2=2 (1+1, 2), s3=4 (1+1+1, 1+2, 2+1, 3). 54 = s3 + s2 + si = 4 + 2 + 1 = 7 55 = 54 + s3 + s2 = 7 + 4 + 2 = 13 <□► •<[51^ 1 ^)Q,0 MA2BP_CKOM 9. cvičeni 3. 12. 2018 3 /6 Příklad: Určete, kolika způsoby je možné vyjít 15 schodů, jestliže můžeme dělat kroky délky 1, 2 nebo 3 schody. Označíme-li sn počet všech možností, jak zdolat n schodů povoleným způsobem, pak posledním krokem zdoláme ■ 1 schod - předchozích n — 1 schodů jsme mohli zdolat sn_i způsoby ■ 2 schody - n — 2 sn-2 způsoby ■ 3 schody - n — 3 sn_3 způsoby Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech způsobů, jak vyjít n schodů je sn = sn_i + sn_2 + sn_3. Potřebujeme ještě dopočítat Sl=l, s2=2 (1+1, 2), s3=4 (1+1+1, 1+2, 2+1, 3). 54 = s3 + s2 + si = 4 + 2 + 1 = 7 55 = 54 + s3 + s2 = 7 + 4 + 2 = 13 5i5 = 5768 <□► •<[51^ 1 ^)Q,0 MA2BP_CKOM 9. cvičení 3. 12. 2018 3 /6 MA2BP_CK0M 9. cvičení 3. 12. 2018 A i/6 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 = 4 (AA, AB, BA, BB), MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 = 4 (AA, AB, BA, BB), s3 = 7 (AAB, ABA, BAA, ABB, BAB, BBA, BBB), MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 = 4 (AA, AB, BA, BB), s3 = 7 (AAB, ABA, BAA, ABB, BAB, BBA, BBB), S4 = S3 + S2 + Si MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 = 4 (AA, AB, BA, BB), s3 = 7 (AAB, ABA, BAA, ABB, BAB, BBA, BBB), s4 = s3 + s2 + si = 7 + 4 + 2 = 13 MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 = 4 (AA, AB, BA, BB), s3 = 7 (AAB, ABA, BAA, ABB, BAB, BBA, BBB), s4 = s3 + s2 + si = 7 + 4 + 2 = 13 s5 = s4 + s3 + s2 = 13 + 7 + 4 = 24 MA2BP_CKOM 9. cvičení 3. 12. 2018 4 i/6 Příklady Příklad: Určete, kolik existuje slov délky 10 sestavených z písmen A, B, která neobsahují řetězec AAA. Označíme-li sn počet všech slov délky n, která neosah ují řetězec AAA, pak tato slova mohou končit ■_________B - takových slov je sn_i, ■________BA - takových slov je sn_2, ■_______BAA - takových slov je sns. Uvedené možnosti jsou všechny (další nejsou) a jsou navzájem disjunktní, proto všech vyhovujících slov délky n je sn = sn_i + sn_2 + sn_3. Nás zajímá sio, potřebujeme ale ještě dopočítat si = 2 (A, B), s2 = 4 (AA, AB, BA, BB), s3 = 7 (AAB, ABA, BAA, ABB, BAB, BBA, BBB), s4 = s3 + s2 + si = 7 + 4 + 2 = 13 s5 = s4 + s3 + s2 = 13 + 7 + 4 = 24 sio = 504 MA2BP_CKOM 9. cvičení 3. 12. 2018 Příklady □ Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C v nichž není obsažen řetězec AAA. B Určete, kolika způsoby lze z balíčku 32 karet (7-A, X 40 rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet b) libovolně, záleží na pořadí rozdaných karet c) třem hráčům tak, aby alespoň jeden z nich dostal eso d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") B Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním". Kolik různých vysvědčení tuto vlastnost splňuje? MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Příklady □ Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C v nichž není obsažen řetězec AAA. [s% = 2s$ + 2sg + 2sj = 5524] B Určete, kolika způsoby lze z balíčku 32 karet (7-A, X 40 rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet b) libovolně, záleží na pořadí rozdaných karet c) třem hráčům tak, aby alespoň jeden z nich dostal eso d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") B Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním". Kolik různých vysvědčení tuto vlastnost splňuje? MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Příklady □ Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C v nichž není obsažen řetězec AAA. [s% = 2s$ + 2sg + 2sj = 5524] B Určete, kolika způsoby lze z balíčku 32 karet (7-A, X 40 rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet (352) b) libovolně, záleží na pořadí rozdaných karet c) třem hráčům tak, aby alespoň jeden z nich dostal eso d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") B Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním". Kolik různých vysvědčení tuto vlastnost splňuje? MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Příklady □ Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C Určete, kolika způsoby lze z balíčku 32 karet (7-A, 4» 4) rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet [(5)] b) libovolně, záleží na pořadí rozdaných karet [\/(5,32) = 24165120] c) třem hráčům tak, aby alespoň jeden z nich dostal eso d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním". Kolik různých vysvědčení tuto vlastnost splňuje? v nichž není obsažen řetězec AAA. [s8 = 2s5 + 2s6 + 2s7 = 5524] MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C v nichž není obsažen řetězec AAA. [s% = 2s$ + 2sg + 2sj = 5524] Určete, kolika způsoby lze z balíčku 32 karet (7-A, X 40 rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet [(352)] b) libovolně, záleží na pořadí rozdaných karet [\/(5,32) = 24165120] c) třem hráčům tak, aby alespoň jeden z nich dostal eso J(?)(ľ)(f)-(?)(?)(?)] d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním". Kolik různých vysvědčení tuto vlastnost splňuje? MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Příklady □ Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C v nichž není obsažen řetězec AAA. [s% = 2s$ + 2sg + 2sj = 5524] B Určete, kolika způsoby lze z balíčku 32 karet (7-A, X 40 rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet [(352)] b) libovolně, záleží na pořadí rozdaných karet [\/(5,32) = 24165120] c) třem hráčům tak, aby alespoň jeden z nich dostal eso ;(352)(257)(25 )-(258)( 53)( 58)] d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") ;©(í)5©5©5; B Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním". Kolik různých vysvědčení tuto vlastnost splňuje? MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Určete, kolik existuje slov délky 8 sestavených z písmen A, B, C v nichž není obsažen řetězec AAA. [s% = 2s$ + 2sg + 2sj = 5524] Určete, kolika způsoby lze z balíčku 32 karet (7-A, X 40 rozdat 5 karet a) libovolně, nezáleží na pořadí rozdaných karet [(352) b) libovolně, záleží na pořadí rozdaných karet [\/(5,32) = 24165120] c) třem hráčům tak, aby alespoň jeden z nich dostal eso K?)(ľ)(?) "(?)(?)(?)] d) třem hráčům tak, aby všichni dostali stejné karty (až na "barvu") ©(t)5©5®5; Na vysvědčení je zapsáno 11 (konkrétních) předmětů a jejich hodnocení, je na něm i celkové hodnocení "prospěl s vyznamenáním" Kolik různých vysvědčení tuto vlastnost splňuje? Co1) + (?) + (?) + (?) + (?) + (V) MA2BP_CKOM 9. cvičení 3. 12. 2018 5 /6 Něco o relacích Určete, kolik existuje na r?-prvkové množině M všech relací reflexivních relací symetrických relací antisymetrických relací úplných relací MA2BP_CKOM 9. cvičení 3. 12. 2018 6 /6 Něco o relacích Určete, kolik existuje na r?-prvkové množině M všech relací reflexivních relací symetrických relací antisymetrických relací úplných relací 2ir MA2BP_CKOM 9. cvičení 3. 12. 2018 6 /6 Něco o relacích Určete, kolik existuje na r?-prvkové množině M všech relací reflexivních relací symetrických relací antisymetrických relací úplných relací 2ir irr — n MA2BP_CKOM 9. cvičení 3. 12. 2018 6 /6 Něco o relacích Určete, kolik existuje na r?-prvkové množině M všech relací 2ir reflexivních relací symetrických relací antisymetrických relací úplných relací irr — n 2~^ MA2BP_CKOM 9. cvičení 3. 12. 2018 6 /6 Něco o relacích Určete, kolik existuje na r?-prvkové množině M všech relací reflexivních relací symetrických relací antisymetrických relací úplných relací 2ir irr — n 2~^ n(n-l) 2"3 2 MA2BP_CKOM 9. cvičení 3. 12. 2018 6 /6 Něco o relacích Určete, kolik existuje na r?-prvkové množině M všech relací reflexivních relací symetrických relací antisymetrických relací úplných relací 2ir irr — n 2~^ n(n-l) 2"3 2 3 2 MA2BP_CKOM 9. cvičení 3. 12. 2018 6 /6