a pravděpodobnost
KOMBINATORIKA
L21: Variace s opakováním
<< Předchozí lekce | Seznam lekcí | Další lekce >>
V jedné z předchozích lekcí jsme se již seznámili s variací bez opakování, což je uspořádaná k-tice z n prvků, která je sestavena tak, že každý se v ní vyskytuje nejvýše jednou. Jak by se však situace změnila, když by se jednotlivé prvky v dané k-tici mohly opakovat?
a)
První cifru vybíráme ze dvou číslic, druhou také ze dvou číslic a stejným způsobem můžeme vybrat třetí. Použitím kombinatorického pravidla součinu zjistíme celkový počet možností.
Počet možných čísel tedy je:
$${2 \cdot 2 \cdot 2 = 8}$$
Bude se jednat o následující čísla:
111, 112, 121, 122, 211, 212, 221, 222
b)
První cifru vybíráme ze dvou číslic, druhou také ze dvou číslic a stejným způsobem můžeme vybrat třetí a čtvrtou. Použitím kombinatorického pravidla součinu zjistíme celkový počet možností.
Počet možných čísel tedy je:
$${2 \cdot 2 \cdot 2 \cdot 2 = 16}$$
Bude se jednat o následující čísla:
1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222
2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222
U variace bez opakování opět vybíráme prvky do uspořádané k-tice z n prvků. Prvek na 1. pozici můžeme vybrat n způsoby. Prvek na druhé pozici můžeme opět vybrat n způsoby. A když budeme pokračovat dále, tak prvek na k-té pozici vybereme opět n způsoby. Dle kombinatorického pravidla součinu tedy bude počet prvků ${n \cdot n \cdot ~ \dots ~ \cdot n}$.
Jedná se o variaci s opakováním 4. řádu (máme 4 kostky) ze 6 prvků (každá kostka má 6 různých hodnot).
$${V`(4, 6) = 6^4 = 1~296}$$
Čtyřmi různobarevnými kostkami můžeme hodit 1 296 různých hodů.
Morseova abeceda je skupina symbolů, která se využívala zejména v telegrafii, kde každý symbol se skládá z jednoho až čtyř krátkých, či dlouhých signálů (např. písmeno A ".-", B "-...", ...). Kolik různých symbolů této abecedy s délkou symbolu od 1 do 4 signálů může existovat?
Tvoříme variace s opakováním 1. až 4. řádu ze dvou prvků. $${V`(1, 2) = 2^1 = 2}$$ $${V`(2, 2) = 2^2 = 4}$$ $${V`(3, 2) = 2^3 = 8}$$ $${V`(4, 2) = 2^4 = 16}$$
Následným sečtením dle kombinatorického pravidla součtu zjistíme celkový počet možností: $${V`(1, 2) + V`(2, 2) + V`(3, 2) + V`(4, 2) = 2 + 4 + 8 + 16 = 30}$$
Pokud budeme brát symboly o délce 1 až 4 signály, můžeme mít celkem 30 různých symbolů. Abychom měli srovnání, znaků anglické abecedy je 26, takže pro ně tato délka plně dostačuje. Pro čísla a další znaky se následně používají i delší symboly (5 až 6 signálů).
Společnost České Dráhy a. s. nabízí při nákupu jízdenky přes Internet doručení jízdenky formou SMS kódu, který stačí při kontrole jízdenky ve vlaku nahlásit průvodčímu. SMS kód jízdenky je šestimístný a skládá se ze znaků anglické abecedy (26 znaků) a čísel (10 čísel). Kolik různých cestujících, kteří si koupili takovou jízdenku, může vlakem v jeden den cestovat, aníž by měli stejný kód jízdenky?
Tvoříme variace s opakováním z 36 prvků (26 + 10 = 36). Daný počet tedy je: $${V`(6, 36) = 36^6 = 2~176~782~336}$$
Autobusový dopravce chce zavést SMS jízděnky. Jízdenku obdrží cestující ve formě SMS zprávy, která bude obsahovat datum a čas a kód, který se bude skládat z určitého počtu písmen anglické abecedy (26 znaků). Na základě dlouhodobých statistik dopravce zjistil, že nepřepraví denně více než 200 000 osob. Kolik znaků musí mít kód jízdenky, aby byla jistota, že daný den nebudou dvě jízdenky se stejným kódem? Kolik by musel mít kód znaků, pokud bychom chtěli používat pouze znaky A - H?
(1) Jedná se o variaci s opakováním x-tého řádu z 26 prvků.
Daný počet tedy je:
$${V`(x, 26) = 26^x = 200~000}$$
Řešíme tedy exponenciální rovnici:
$${26^x = 200~000}$$
$${log~26^x = log~200~000}$$
$${x \cdot log~26 = log~200~000}$$
$${x = \frac{log~200~000}{log~26}}$$
$${x = \frac{5,301}{1,415} = 3,75}$$
Kód jízdenky musí v tomto případě obsahovat minimálně 4 znaky anglické abecedy.
(1) Jedná se o variaci s opakováním x-tého řádu z 8 prvků.
Daný počet tedy je:
$${V`(x, 8) = 8^x = 200~000}$$
Řešíme tedy exponenciální rovnici:
$${8^x = 200~000}$$
$${log~8^x = log~200~000}$$
$${x \cdot log~8 = log~200~000}$$
$${x = \frac{log~200~000}{log~8}}$$
$${x = \frac{5,301}{0,903} = 5,87}$$
Kód jízdenky musí v tomto případě obsahovat minimálně 6 znaků, pokud použijeme znaky A - H.
Z kolika prvků je možno vytvořit právě 1024 variací s opakováním páté třídy?
Pro variace s opakováním platí vzorec: $${V`(k, n) = n^k}$$
Dosadíme-li do výše uvedeného vzorce, získáme: $${V`(5, n) = n^5 = 1024}$$
Řešíme tedy následující rovnici: $${n^5 = 1024}$$ $${n = \sqrt[5]{1024}}$$ $${k = 4}$$
Jedná se o variaci ze čtyř prvků.
O kolikačlenné variace s opakováním ze čtyř prvků jde, je-li celkem 4096 variací?
Pro variace s opakováním platí vzorec: $${V`(k, n) = n^k}$$
Dosadíme-li do výše uvedeného vzorce, získáme: $${V`(k, 4) = 4^k = 4096}$$
Řešíme tedy následující rovnici: $${4^k = 4096}$$ $${4^k = 4^6}$$ $${k = 6}$$
Jedná se o šestičlenné variace ze čtyř prvků.
- Co je to "variace s opakováním"?
- Pomocí jakého vzorce vypočítáme počet variací s opakováním? Zdůvodněte.
- Kolik nejvýše čtyřciferných čísel lze sestavit z číslic 1, 2, 3, 4 a 5 tak, že se mohou opakovat?
- O kolikačlenné variace s opakováním ze dvou prvků jde, je-li celkem 2048 variací?
- k-členná variace s opakováním z n prvků je uspořádaná k-tice sestavená z těchto prvků tak, že každý se v ní může vyskytovat nejvýše k-krát.
- $${V`(k, n) = n^k}$$
- ${V`(1, 5) + V`(2, 5) + V`(3, 5) + V`(4, 5) = 780}$
- ${11}$