kombinatorika

Příklad 601

Určete počet osmiciferných palindromických čísel, v nichž se žádná cifra nevyskytuje více než dvakrát.

Řešení	Ukázat>
Stačí určit počet čtyřciferných čísel, v nichž se číslice neopakují: $9\cdot V_3(9)$

Příklad 602

Určete počet netriviálních dělitelů čísla $441\,000.$

Řešení	Ukázat>
Je $441\,000=2^3\cdot3^2\cdot5^3\cdot7^2.$ Dělitel bude ve tvaru $2^a\cdot3^b\cdot5^c\cdot7^d,$ kde $0\le a\le3,$ $0\le b\le2,$ $0\le c\le3,$ $0\le d\le2,$ Tj. pro výběr $a$ i $c$ máme 4 možnosti, $b$ i $d$ 3 možnosti. Musíme odečíst dva triviální dělitele ( $1$ a $441\,000$ ). Celkem $4\cdot3\cdot4\cdot3-2=142$ netriviálních dělitelů.

Příklad 603

Určete počet pěticiferných čísel, ve kterých se vyskytuje číslice $6$ právě jednou.

Řešení	Ukázat>
(a) cifra $6$ je na prvním místě: čísel je $9^4$ (b) cifra $6$ není na prvním místě: Na prvím místě je 8 možností, pro šestku jsou 4 možnosti, zbylé tři cifry mají 9 možností, $8\cdot4\cdot9^3$ Celkem $9^4+32\cdot9^3$ čísel.

Příklad 604

V určité loterii je losuje 6 čísel ze 48 a stejný počet čísel se vyznačuje na tiketu. Pokud se všechna vyznačená čísla na tiketu shodují s vylosovanými, tiket získává 1. cenu. Pokud se shoduje jen pět čísel, tiket získává 2. cenu a pokud se shodují čtyři čísla, pak tiket získává 3. cenu. Jiné ceny se nevyplácejí. Určete celkový počet různých tiketů, které je možné při jednom tahu vyplatit.

Řešení	Ukázat>
$1+{6\choose5}{42\choose1}+{6\choose4}{42\choose2}$

Příklad 605

Ve třech pokojích mohou být ubytovány v každém tři nebo čtyři lidi. Určete počet způsobů, kterými můžeme ubytovat 10 lidí.

Řešení	Ukázat>
Vybereme pokoj se čtyřmi lidmi, pak do něj 4 lidi z deseti, pak do prvního trojlůžkového 3 lidi ze šesti. Celkem ${4\choose3}{10\choose4}{6\choose3}$ způsobů.

Příklad 606

Z města A do B vedou 4 silnice a z B do C vede 6 silnic. Určete počet různých cest z A -> B -> C -> B -> A, když po žádné silnici nepojedem dvakrát.

Řešení	Ukázat>
$4\cdot6\cdot5\cdot3=360$

Příklad 607

Ze skupiny osmi mužů a šesti žen mezi nimiž je jeden manželský pár chceme vybrat skupinu tří mužů a tří žen tak, že je v ní nejvýše jeden z manželů. Kolik máme možností?

Řešení	Ukázat>
${7\choose2}{5\choose3}+{7\choose3}{5\choose2}+{7\choose3}{5\choose3}$

Příklad 608

Jedenáct studentů (3 dívky a 8 chlapců) spolu se svým učitelem sedí v restauraci u kulatého stolu a oslavují úspěšné maturity. Učitel má vyhrazené zvláštní čestné místo. Kolika způsoby se mohou studenti usadit u stolu, když žádné dvě studentky nesedí vedle sebe?

Řešení	Ukázat>
Studenti se můžou usadit $8!$ způsoby. Tím vznikne (i s učitelem) 9 pozic pro dívky. Z těchto pozic vybereme 3 a na ně se studentky můžou usadit $3!$ způsoby. Celkem $8!{9\choose3}3!$ způsobů.

Příklad 609

Najděte počet cest délky 20, začínajících i končících v počátku souřadnicové soustavy a skládajících se z úseček rovnoběžných se souřadnicovými osami, které mají koncové body v bodech s celočíselnými souřadnicemi.

Řešení	Ukázat>
Pokud uděláme $i$ kroků vlevo, musíme udělat $i$ kroků vpravo. Ze zbylých $20-2i$ jich bude polovina dolů a polovina nahoru. Každou takovou cestu tedy můžeme zakódovat jako řetězec délky 20, který se skládá z $i$ L, $i$ P, $10-i$ N a $10-i$ D. Takových řetězců je celkem $\sum_{i=0}^{10}\dfrac{20!}{[i!\cdot(10-i)!]^2}$

Příklad 610

Kolika způsoby můžeme rozmístit 10 stejných židlí k šesti stolům označeným A až F, když chceme aby součet židlí u stolů A a B nepřevýšil 4?

Řešení	Ukázat>
$i$ židlí $(0\le i\le4)$ můžeme ke stolům A a B přidělit ${2+i-1\choose i}={i+1\choose i}=i+1$ způsoby. Zbylých $10-i$ židlí pak k ostatním stolům ${4+10-i-1\choose10-i}={13-i\choose3}$ způsoby. Možnosti musíme posčítat $\sum_{i=0}^4(i+1)\cdot{13-i\choose3}$

Příklad 611

Kolika způsoby můžeme ubytovat 10 studentů do šesti pokojů označených A až F, když chceme aby celkový počet studentů v pokojích A a B nepřevýšil 4? Pokoje jsou dostatečně velké, takže by se všichni studenti dali ubytovat v libovolném pokoji.

Řešení	Ukázat>
Vybereme $i$ $(0\le i\le4)$ studentů ${10\choose i}$ způsoby. Tyto studenty můžeme rozdělit do pokojů A a B $2^i$ způsoby. Zbylých $10-i$ studentů můžeme rozdělit do zbylých čtyř pokojů $4^{10-i}$ způsoby. Celkem $\sum_{i=0}^4{10\choose i}\cdot2^i\cdot4^{10-i}$

Příklad 612

Určete počet řešení rovnice

$a+b+c+d+e+f=20$

v nezáporných celých číslech, když žádná neznámá není větší než 8.

Řešení	Ukázat>
Všech možných řešení je ${6+20-1\choose20}={25\choose20}.$ Řešení, kdy aspoň jedna neznámá je větší než 8 je ${6\choose1}{6+11-1\choose11}={6\choose1}{16\choose11}.$ Řešení, kdy aspoň dvě neznámé jsou větší než 8 je ${6\choose2}{6+2-1\choose2}={6\choose2}{7\choose2}.$ Podle PIE je počet hledaných řešení ${25\choose20}-{6\choose1}{16\choose11}+{6\choose2}{7\choose2}.$

Řešení

Ukázat>

Všech možných řešení je

${6+20-1\choose20}={25\choose20}.$
Řešení, kdy aspoň jedna neznámá je větší než 8 je

${6\choose1}{6+11-1\choose11}={6\choose1}{16\choose11}.$
Řešení, kdy aspoň dvě neznámé jsou větší než 8 je

${6\choose2}{6+2-1\choose2}={6\choose2}{7\choose2}.$
Podle PIE je počet hledaných řešení

${25\choose20}-{6\choose1}{16\choose11}+{6\choose2}{7\choose2}.$

Příklad 613

Určete počet čtyřciferných čísel, jejichž ciferný součet je 31.

Řešení	Ukázat>
Potřebujeme určit počet řešení rovnice $x_1+x_2+x_3+x_4=31$ s podmínkymi $x_i\in\mathbb N_0,\ 0\le x_i\le9.$ Není potřeba se zabývat situací, kdy je $x_1=0,$ protože pak se za daných podmínek nedá rovnice splnit. Všech možných řešení je ${4+31-1\choose31}={34\choose3}$ Řešení, kdy aspoň jedno $x_i\ge10:$ ${4\choose1}{24\choose3}$ Řešení, kdy aspoň dvě $x_i\ge10:$ ${4\choose2}{14\choose3}$ Řešení, kdy aspoň tři $x_i\ge10:$ ${4\choose3}{4\choose3}$ Podle PIE je počet čísel ${34\choose3}-{4\choose1}{24\choose3}+{4\choose2}{14\choose3}-{4\choose3}{4\choose3}$

Řešení

Ukázat>

Potřebujeme určit počet řešení rovnice

$x_1+x_2+x_3+x_4=31$

s podmínkymi

$x_i\in\mathbb N_0,\ 0\le x_i\le9.$ Není potřeba se zabývat situací, kdy je

$x_1=0,$ protože pak se za daných podmínek nedá rovnice splnit.
Všech možných řešení je

${4+31-1\choose31}={34\choose3}$
Řešení, kdy aspoň jedno

$x_i\ge10:$

${4\choose1}{24\choose3}$
Řešení, kdy aspoň dvě

$x_i\ge10:$

${4\choose2}{14\choose3}$
Řešení, kdy aspoň tři

$x_i\ge10:$

${4\choose3}{4\choose3}$
Podle PIE je počet čísel

${34\choose3}-{4\choose1}{24\choose3}+{4\choose2}{14\choose3}-{4\choose3}{4\choose3}$

Příklad 6144

Určete počet anagramů slova "MISSISSIPPI", ve kterých žádná dvě "S" nesousedí.

Řešení	Ukázat>
Písmena bez "S" můžeme uspořádat $\dfrac{7!}{4!\cdot2!}.$ Tím vytvoříme 8 pozic pro "S", z nichž vybereme 4. Celkem $\dfrac{7!}{4!\cdot2!}{8\choose4}$

Příklad 615

Určete počet anagramů slova "TALLAHASSEE", ve kterých žádná dvě "A" nesousedí.

Řešení	Ukázat>
Písmena bez "A" můžeme uspořádat $\dfrac{8!}{2!\cdot2!\cdot2!}.$ Tím vytvoříme 9 pozic pro "A", z nichž vybereme 3. Celkem $\dfrac{8!}{2!\cdot2!\cdot2!}{9\choose3}$

Příklad 616

Určete počet způsobů, kterými můžeme 10 barevných lamp (4 červené, 3 bílé a 3 zelené, lampy stejné barvy jsou identické) do dvanácti místností tak, že v každé místnosti je nejvýše jedna lampa.

Řešení	Ukázat>
${12\choose4}{8\choose3}{5\choose3}$

Příklad 617

Určete počet způsobů, kterými můžeme rozdělit 20 studentů do čtyř stejně početných skupin.

Řešení	Ukázat>
$\frac1{4!}{20\choose5}{15\choose5}{10\choose5}$

Příklad 618

Určete počet způsobů, kterými můžeme rozdělit 10 různých knih čtyřem studentům tak, že každý dostane aspoň dvě knihy.

Řešení	Ukázat>
Když každý dostane dvě knihy, zbydou ještě dvě, které můžeme rozdělit dvěma způsoby (a) obě dostane jeden student: ${4\choose1}{10\choose4}{6\choose2}{4\choose2}$ (b) rozdělíme je mezi dva studenty: ${4\choose2}{10\choose3}{7\choose3}{4\choose2}$ Celkem ${4\choose1}{10\choose4}{6\choose2}{4\choose2}+{4\choose2}{10\choose3}{7\choose3}{4\choose2}$ způsobů.

Příklad 619

Určete počet způsobů, kterými můžeme umístit 12 různých knih do tří různých tašek (konkrétní pořadí knih v tašce není důležité), tak, že v některé tašce jsou 3 knihy a v jiné 4 knihy.

Řešení	Ukázat>
Rozdělit knihy na tři hromádky s počty 3, 4, 5 knih můžeme ${12\choose3}{9\choose4}$ způsoby. Tyto hromádky pak můžeme přiřadit taškám $3!$ způsoby. Celkem $3!{12\choose3}{9\choose4}$ způsobů.

Příklad 620

Určete počet způsobů, kterými můžeme vybrat tři různá čísla z množiny $X=\{1,2,\dots,100\}$ tak, aby jejich součet byl dělitelný třemi.

Řešení	Ukázat>
Množinu $X$ rozdělíme na tři disjunktní podmnožiny tak, že v množině $X_i$ jsou čísla se zbytkem po dělení třemi $i.$ Je $\|X_0\|=33,$ $\|X_1\|=34$ a $\|X_2\|=33.$ Součet tří čísel může být dělitelný třemi jen když buď všechna tři čísla jsou ze stejné podmnožiny, nebo z každé podmnožiny je právě jedno. Počet výběrů je prpto ${33\choose3}+{34\choose3}+{33\choose3}+{33\choose1}{34\choose1}{33\choose1}$

Řešení

Ukázat>

Množinu

$X$ rozdělíme na tři disjunktní podmnožiny tak, že v množině

$X_i$ jsou čísla se zbytkem po dělení třemi

$i.$ Je

$|X_0|=33,$

$|X_1|=34$ a

$|X_2|=33.$ Součet tří čísel může být dělitelný třemi jen když buď všechna tři čísla jsou ze stejné podmnožiny, nebo z každé podmnožiny je právě jedno. Počet výběrů je prpto

${33\choose3}+{34\choose3}+{33\choose3}+{33\choose1}{34\choose1}{33\choose1}$

Příklad 621

Určete počet 4-ciferných čísel sestavených z číslic $\{1,2,\dots,6\},$ v nichž je každá z cifer $\{1,2,3\}$ aspoň jednou.

Řešení	Ukázat>
Všech čísel je $6^4.$ Čísel, v nichž není aspoň jedna z cifer 1,2,3 je ${3\choose1}5^4.$ Čísel, v nichž nejsou aspoň dvě z cifer 1,2,3 je ${3\choose2}4^4.$ Čísel, v nichž nejsou aspoň tři z cifer 1,2,3 je ${3\choose3}3^4.$ Podle PIE je hledaných čísel $6^4-\left[{3\choose1}5^4-{3\choose2}4^4+{3\choose3}3^4\right]$

Příklad 622

Určete počet řešení rovnice

$x_1+x_2+x_3+x_4+x_5=20$

v nezáporných celých číslech, takových, že

$x_1>x_5.$

Řešení	Ukázat>
Je zřejmé, že řešení, pro která platí $x_1>x_5,$ je stejně jako řešení, pro která platí $x_1<x_5,$ protože záměnou $x_1\leftrightarrow x_5$ dostáváme opět řešení. Všech řešení je ${5+20-1\choose20}={24\choose20}.$ Určíme počet řešení, kdy $x_1=x_5.$ Nechť $x_1=x_5=i$ $(0\le i\le10).$ Rovnice pak přejde na tvar $x_2+x_3+x_4=20-2i,$ která má ${3+20-2i-1\choose20-2i}={22-2i\choose2}$ řešení. Počet hledaných řešení je $\dfrac12\left[{24\choose20}-\sum_{i=0}^{10}{22-2i\choose2}\right]$

Řešení

Ukázat>

Je zřejmé, že řešení, pro která platí

$x_1>x_5,$ je stejně jako řešení, pro která platí

$x_1<x_5,$ protože záměnou

$x_1\leftrightarrow x_5$ dostáváme opět řešení. Všech řešení je

${5+20-1\choose20}={24\choose20}.$
Určíme počet řešení, kdy

$x_1=x_5.$
Nechť

$x_1=x_5=i$

$(0\le i\le10).$ Rovnice pak přejde na tvar

$x_2+x_3+x_4=20-2i,$

která má

${3+20-2i-1\choose20-2i}={22-2i\choose2}$ řešení.
Počet hledaných řešení je

$\dfrac12\left[{24\choose20}-\sum_{i=0}^{10}{22-2i\choose2}\right]$

Příklad 623

Z pytlíku, v němž jsou 3 žluté 1 modrá, 10 červených a 19 zelených kuliček, nabereme hrst deseti kuliček. Kolik různých hrstí můžeme dostat?

Řešení	Ukázat>
V hrsti buďto je, nebo není modrá kulička. (a) Není modrá a je $i$ žlutých $(0\le i\le3):$ Zbylých $10-i$ kuliček můžeme rozdělit do dvou kategorií ${2+10-i-1\choose10-i}=11-i$ způsoby. (b) Je modrá je $i$ žlutých $(0\le i\le3):$ Zbylých $9-i$ kuliček můžeme rozdělit do dvou kategorií ${2+9-i-1\choose9-i}=10-i$ způsoby. Celkový počet možností je $\sum_{i=0}^3(11-i)+\sum_{i=0}^3(10-i)=\sum_{i=0}^3(21-2i)=\dfrac42(21+15)=72$

Řešení

Ukázat>

V hrsti buďto je, nebo není modrá kulička.
(a) Není modrá a je

$i$ žlutých

$(0\le i\le3):$ Zbylých

$10-i$ kuliček můžeme rozdělit do dvou kategorií

${2+10-i-1\choose10-i}=11-i$ způsoby.
(b) Je modrá je

$i$ žlutých

$(0\le i\le3):$ Zbylých

$9-i$ kuliček můžeme rozdělit do dvou kategorií

${2+9-i-1\choose9-i}=10-i$ způsoby.
Celkový počet možností je

$\sum_{i=0}^3(11-i)+\sum_{i=0}^3(10-i)=\sum_{i=0}^3(21-2i)=\dfrac42(21+15)=72$

666 příkladů z kombinatoriky

Komplexní úlohy X

Příklad 601

Příklad 602

Příklad 603

Příklad 604

Příklad 605

Příklad 606

Příklad 607

Příklad 608

Příklad 609

Příklad 610

Příklad 611

Příklad 612

Příklad 613

Příklad 6144

Příklad 615

Příklad 616

Příklad 617

Příklad 618

Příklad 619

Příklad 620

Příklad 621

Příklad 622

Příklad 623

Napsat komentář Zrušit odpověď na komentář