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 :)

✓   Téma bylo vyřešeno.

Obtížnost: Střední škola
Kategorie: Kombinatorika
Dominik M.

Dominik M.

29. 08. 2020   14:03

3 odpovědi

Tomáš B.
Tomáš B.
29.08.2020 22:41:41

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? ;-)

Souhlasí: 1    
Dominik M.
Dominik M.
01.09.2020 20:00:46

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í.

Dominik M.
Dominik M.
01.09.2020 20:06:54

Můžu se zeptat, jestli tady někdo nestudoval Matfyz?

S pozdravem Dominik Micka.

Pro napsání komentáře se musíte přihlásit.