kombinatorika

Příklad 225

Kolik různých přirozených čísel menších než $3\,000$ lze sestavit z číslic 0, 2, 6, 7, 8? Žádná z číslic se neopakuje.

Řešení	Ukázat
Jednociferná čísla jsou $4$ (nula není přirozené číslo). Dvouciferných čísel je $4\cdot4=16$ . Trojciferných čísel je $4\cdot4\cdot3=48$ Čtyřciferných čísel je $1\cdot4\cdot3\cdot2=24$ Celkem $4+16+48+24=92$ vhodných čísel.

Příklad 226

Bezpečnostní zámek se otevírá bezpečnostním kódem. Kód je tvořen třemi nebo čtyřmi číslicemi a žádná číslice se nesmí opakovat. Kolik existuje bezpečnostních kódů?

Řešení	Ukázat
Trojmístných kódů je $10\cdot9\cdot8=720.$ Čtyřmístných kódů je $10\cdot9\cdot8\cdot7=5040.$ Celkem je $720+5040=5760$ kódů.

Příklad 227

Kolik existuje tříciferných čísel, která mají všechny cifry různé a mají sudý ciferný součet?

Řešení	Ukázat
Čísla se sudým ciferným součtem můžeme rozdělit na 4 typy (S - sudá cifra, L - lichá cifra) SSS - těchto čísel je $4\cdot4\cdot3=48$ SLL - těchto čísel je $4\cdot5\cdot4=80$ LSL - těchto čísel je $5\cdot5\cdot4=100$ LLS - těchto čísel je $5\cdot4\cdot5=100$ Celkem existuje 328 čísel požadované vlastnosti.

Příklad 228

Kolik pěticiferných čísel neobsahuje žádnou číslici právě jednou? (11111 a 10010 jsou dobré, ale 10111 a 12312 ne.)

Řešení	Ukázat
Čísla jsou dvou základních typů - (I) všechny cifry stejné, nebo (II) 2 stejné cifry + 3 jiné stejné cifry. (I) - těchto čísel je $9.$ (II) tuto kategorii si dále rozdělíme (a) dvě nuly + tři jiná čísla (X00XX) (b) tři nuly + dvě jiná čísla (X000X) (c) nula tam není (XXYYY) (a) Na prvním místě je nenulová cifra. Zbylé cifry můžeme libovolně proházet (permutace s opakováním). $9\cdot\frac{4!}{2!\cdot2!}=54$ (b) Na prvním místě je nenulová cifra. Zbylé cifry můžeme libovolně proházet. $9\cdot\frac{4!}{3!}=36$ (c) Vybereme cifru, která je 2 krát (9 možností), pak vybereme cifru, která je 3 krát (8 možností), proházíme. $9\cdot8\cdot\frac{5!}{3!\cdot2!}=720$ Celkem $9+54+36+720=819$

Řešení

Ukázat

Čísla jsou dvou základních typů - (I) všechny cifry stejné, nebo (II) 2 stejné cifry + 3 jiné stejné cifry.
(I) - těchto čísel je

$9.$
(II) tuto kategorii si dále rozdělíme
(a) dvě nuly + tři jiná čísla (X00XX)
(b) tři nuly + dvě jiná čísla (X000X)
(c) nula tam není (XXYYY)
(a) Na prvním místě je nenulová cifra. Zbylé cifry můžeme libovolně proházet (permutace s opakováním).

$9\cdot\frac{4!}{2!\cdot2!}=54$
(b) Na prvním místě je nenulová cifra. Zbylé cifry můžeme libovolně proházet.

$9\cdot\frac{4!}{3!}=36$
(c) Vybereme cifru, která je 2 krát (9 možností), pak vybereme cifru, která je 3 krát (8 možností), proházíme.

$9\cdot8\cdot\frac{5!}{3!\cdot2!}=720$
Celkem

$9+54+36+720=819$

Příklad 229

Kolik existuje přirozených trojciferných čísel dělitelných pěti, v jejichž zápisu se každá cifra vyskytuje nejvýše jednou?

Řešení	Ukázat
Čísla si rozdělíme na dvě kategorie - (a) končí nulou, nebo (b) končí pětkou. (a) čísel je $9\cdot8=72$ (b) čísel je $8\cdot8=64$ Celkem $72+64=136$ čísel.

Příklad 230

Kolik existuje čtyřciferných přirozených čísel dělitelných pěti, která můžeme sestavit z číslic $\{0, 1, 2, 3, 4, 5, 6\}$ ?

Řešení	Ukázat
Stejný postup jako v příkladu 229. Rozdělíme na dvě kategorie podle koncového čísla. $5\cdot6^2+5\cdot6^2=360$

Příklad 231

Kolik čtyřciferných čísel je dělitelných pěti a přitom mají různé cifry.

Řešení	Ukázat
$9\cdot8\cdot7+8\cdot8\cdot7=952$

Příklad 233

Určete počet všech osmipísmenných slov, která lze vytvořit záměnou písmen slova "ARMATURA" a která začínají i končí samohláskou. Slova nemusí mít žádný skutečný význam.

Řešení	Ukázat
Čísel typu A-A je $\dfrac{6!}{2!}.$ Čísel typu A-U je $\dfrac{6!}{2!\cdot2!}.$ Čísel typu U-A je také $\dfrac{6!}{2!\cdot2!}.$ Celkem je čísel $\dfrac{6!}{2!}+\dfrac{6!}{2!\cdot2!}+\dfrac{6!}{2!\cdot2!}$

Příklad 234

Máme posloupnost délky 6, která je tvořená písmeny "A" nebo "B". Kolik je takových posloupností, v nichž žádná dvě "A" nesousedí?

Řešení	Ukázat
(a) v posloupnosti není "A": $1$ posloupnost (b) v poloupnosti je jedno "A": ${6\choose1}=6$ posloupností (c) v posloupnosti jsou 2 "A": ${5\choose2}=10$ posloupností (d) v posloupnosti jsou 3 "A": ${4\choose3}=4$ posloupností Celkem 21 možných posloupností.

Příklad 235

Kolem kulatého stolu je připraveno 7 židlí, na které má usednout 7 hostů (A, B, C, D, E, F a G). Určete, kolika různými způsoby můžete hosty rozmístit kolem stolu, jestliže A má pevně určené místo, B a C musí sedět vedle sebe a D nesmí sedět vedle A.

Řešení	Ukázat
První varianta: B nebo C sedí vedle A - $4$ možnosti. Pak má D $3$ možnosti, kam si sednout a zbytek můžeme usadit $3!$ způsoby. Druhá varianta: B ani C nesedí vedle A - $6$ možností. Pak má D jen $2$ možnosti, kam si sednout a zbytek můžeme usadit $3!$ způsoby. Celkem $4\cdot3\cdot3!+6\cdot2\cdot3!$ způsobů.

Příklad 236

Na karate chodí šest děvčat a čtyři chlapci. Trenér potřebuje připravit soupisku soutěžících na turnaj. Družstvo má být šestičlenné a musí v něm být aspoň čtyři děvčata. Kolik různých soupisek může trenér vytvořit?

Řešení	Ukázat
4 děvčata a dva chlapci ${6\choose4}\cdot{4\choose2}$ 5 děvčat a 1 chlapec ${6\choose5}\cdot{4\choose1}$ 6 děvčat ${6\choose6}\cdot{4\choose0}$ Celkem ${6\choose4}\cdot{4\choose2}+{6\choose5}\cdot{4\choose1}+{6\choose6}\cdot{4\choose0}$

Příklad 237

Mezi 10 studenty jsou 3 dívky. Kolika způsoby z nich můžeme vybrat 5 tak, aby
a) mezi nimi byla právě 1 dívka?
b) mezi nimi byla nejvýše 1 dívka?

Řešení	Ukázat
(a) ${3\choose1}\cdot{7\choose4}$ (b) ${3\choose0}\cdot{7\choose5}+{3\choose1}\cdot{7\choose4}$

Příklad 238

Ze 16 chlapců a 10 dívek máme sestavit šestičlenné družstvo, ve kterém mají být aspoň dva chlapci a aspoň dvě dívky. Kolika způsoby to můžeme udělat?

Řešení	Ukázat
${16\choose2}\cdot{10\choose4}+{16\choose3}\cdot{10\choose3}+{16\choose4}\cdot{10\choose2}$

Příklad 239

Kolika způsoby můžeme ze skupiny dvou dívek a sedmi chlapců vybrat 4 lidi tak, aby mezi nimi byla aspoň jedna dívka?

Řešení	Ukázat
${2\choose2}\cdot{7\choose2}+{2\choose1}\cdot{7\choose3}$

Příklad 240

Ze skupiny 7 chlapců a 4 dívek chceme vybrat šestičlenné volejbalové družstvo, v němž musí být aspoň dvě dívky. Kolika způsoby to lze učinit?

Řešení	Ukázat
${4\choose2}\cdot{7\choose4}+{4\choose3}\cdot{7\choose3}+{4\choose4}\cdot{7\choose2}$

666 příkladů z kombinatoriky

Kombinatorický součet