Kombinatorika
Ahoj Marku,
nevím si rady s jedním příkladem z kombinatoriky, mohl bych tě poprosit o nějaké pošťouchnutí?
Byl bych ti vděčný za jakoukoli informaci.
Úloha zní takto: "Kolik je možných šesticiferných přirozených čísel zapsaných jen pomocí jedniček a dvojek, kde se nemůže vedle sebe vyskytnout dvě dvojky? " Když se nad tím zamyslím, tak to bude variace 6- té třídy ze dvou prvků, ale s opakováním, protože i když tam například nebudou ty dvě dvojky vedle sebe, tak ty prvky musím použít vícekrát, abych jimi zaplnil všech šest pozic. Zkusil jsem postupovat takto - V'(6, 2) = 64 a od toho ještě musím odečíst všechny možnosti, kde jsou dvojky vedle sebe, ale nedaří se mi přijít na vzoreček, který tyto možnosti zahrnuje. Napadá tě něco?
Děkuji za odpověď a přeji hezký den.
S pozdravem Dominik Micka :)
Dominik M.
29. 08. 2020 14:03
3 odpovědi
Ahoj Dominiku,
když se snažíš vymyslet nějaký vzorec, tak se úplně vždycky vyplatí zjednodušit si problém.
Kolika způsoby můžeš složit 1-ciferné číslo podle zadaných pravidel?
Kolika způsoby můžeš složit 2-ciferné číslo podle zadaných pravidel?
Označím si počet variant n-ciferného čísla jako F(n) a platí:
F(1) = 2
F(2) = 3
Dále, v obecném případě, pro F(n) musí platit jedna ze dvou možností:
-
číslo začíná jedničkou, čili je ve tvaru 1xxx, takových možností je F(n-1)
-
číslo začíná dvojkou, ale pak následuje jednička, čili je ve tvaru 21xxx, takových možností je F(n-2)
Takže dostáváme, že F(n) = F(n-1) + F(n-2), což je součet kombinací obou variant.
Nepřipomíná ti to Fibonacciho čísla? ;-)
Aha, takže pokud budu postupovat podle tohoto vzorce, tak pro šesticiferné číslo budu pak mít F(6) = F(5) + F(4) = 21 možností.
Můžu se zeptat, jestli tady někdo nestudoval Matfyz?
S pozdravem Dominik Micka.