Diskrétní matematika — prověrka 14.4.2021 — varianta 01
Každý přiklad je hodnocen 2 body. Vaším úkolem je správně vyřídit minimálně 60 procent úkolů, tj.
kousek. Nepoužívejte prosím v průběhu řešení internet ani telefon.
dva úkoly a
1. Kolika způsoby lze rozdělit 10 nerozlišitelných předmětů (např. zákusků jednoho druhu) do 5 nerozlišitelných šuplíků (neoznačených jménem, rozházených po zemi - je jedno, zda se např. tři zákusky nacházejí v daném šuplíku nebo nějakém jiném, rozhoduje jen jejich počet).
2. Kolik existuje navzájem různých injekcí pětiprvkové množiny X do osmiprvkové množiny Yl (prvky obou množin považujeme za rozlišitelné)
3. Dokažte vzorec pro konstrukci Stirlingova trojúhelníku druhého druhu
S{n + 1, k + 1) = S(n, k) + (k + 1) • S(n, k + 1).
Nápověda: nechte se inspirovat důkazem podobného vzorce pro konstrukci Pascalova trojúhelníku - celkový počet rozdělte na součet počtu konfigurací ve dvou možných situacích.
4. V algoritmu přemístění pětipatrové hanojské věže (n = 5) zaznamenejte všech 31 potřebných tahů. (vytvořte systém, ve kterém bude jasné, o jaké tahy se přesně jedná)