kombinatorika

Příklad 643

Kolika způsoby můžeme do řady seřadit $n$ bílých a $k$ černých kostek $(k\ge n)$ tak, aby žádné dvě kostky nebyly vedle sebe? Kostky stejné barvy jsou nerozlišitelné.

Řešení	Ukázat>
$k$ kostek v řadě vytváří $k+1$ pozic, z nichž musíme vybrat $n.$ To lze ${k+1\choose n}$ způsoby.

Příklad 644

Kolika způsoby můžeme posadit na $2n$ sedadel v řadě $n$ mužů a $n$ žen tak, aby vedle sebe neseděli dva lidé stejného pohlaví?

Řešení	Ukázat>
$2(n!)^2$

Příklad 645

Kolika způsoby můžeme posadit ke kulatému stolu $n$ mužů a $n$ žen tak, aby vedle sebe neseděli dva lidé stejného pohlaví?

Řešení	Ukázat>
Zobecnění příkladu 138. $n!(n-1)!$

Příklad 646

Kolika způsoby můžeme posadit ke kulatému stolu $m$ mužů a $n$ žen $(m>n)$ tak, aby vedle sebe neseděly žádné dvě ženy?

Řešení	Ukázat>
Nejprve udadíme muže. To lze $(m-1)!$ způsoby. Mezi muži se vytvoří $m$ míst pro ženy. Vybereme $n$ míst ${m\choose n}$ způsoby a usadíme na vybraná místa ženy. To lze $n!$ způsoby. Celkem ${m\choose n}(m-1)!n!=\dfrac{m!(m-1)!}{(m-n)!}$ způsobů.

Příklad 647

Na poradě vedení firmy se sešlo $n$ členů vedení včetně ředitele a jeho dvou asistentek. Kolika způsoby se mohou usadit u kulatého stolu, když obě asistentky musí sedět vedle ředitele?

Řešení	Ukázat>
$2\cdot(n-3)!$

Příklad 648

Určete počet způsobů, kterými se může usadit $r$ z $n$ lidí k jednomu kulatému stolu a zbytek ke druhému kulatému stolu.

Řešení	Ukázat>
Vybereme $r$ osob k prvnímu stolu. To můžeme udělat ${n\choose r}$ způsoby. Tyto lidi pak můžeme usadit $(r-1)!$ způsoby. Zbylé osoby můžeme usadit k druhému stolu $(n-r-1)!$ způsoby. Celkem ${n\choose r}(r-1)!(n-r-1)!$ způsobů.

Příklad 649

Na večírku se sešlo $n$ manželských párů. Každá osoba si potřásla rukou s každou jinou osbou s výjimkou svého partnera. Kolik potřesení rukou se odehrálo?

Řešení	Ukázat>
Mezi $2n$ lidmi můžeme vybrat ${2n\choose2}$ párů. Od tohoto počtu musíme odečíst počet manželských párů. ${2n\choose2}-n=\dfrac{2n(2n-1)}2-n=2n(n-1)$

Příklad 650

Chceme poslat pohlednice $k$ přátelům, každému právě dvě pohlednice. Na výběr je $n$ druhů pohlednic v dostatečném množství. Kolika způsoby můžeme rozeslat pohlednice?

Řešení	Ukázat>
Dvě pohlednice pro každého můžeme vybrat ${n\choose2}$ a musíme to udělat $k$ krát. Celkem ${n\choose2}^k.$

Příklad 651

V tenisovém klubu je $m$ mužů a $n$ žen. Určete počet všech možných utkání ve smíšené čtyhře.

Řešení	Ukázat>
Vybereme dva muže ${m\choose2}$ způsoby a dvě ženy ${n\choose2}$ způsoby. Muže k ženám můžeme přiřadit dvěma způsoby. Celkem $2{m\choose2}{n\choose2}$ možných utkání.

Příklad 652

Máme k dispozici $m$ hráčů a z nich $n$ může zastávat roli brankáře. Kolika způsoby můžeme sestavit $k$ -členné družstvo, v němž bude aspoň jeden brankář?

Řešení	Ukázat>
Od všech výběrů odečteme výběry bez brankáře. ${m\choose k}-{m-n\choose k}$

Příklad 653

Kolik existuje binárních sekvencí s $n$ jedničkami a $2n$ nulami, ve kterých se mezi každými dvěma jedničkami nalézají aspoň 2 nuly?

Řešení	Ukázat>
$n$ jedniček vytváří $n-1$ vnitřních míst. Na každé toto místo umístíme 2 nuly. Zůstanou nám $2n-2(n-1)=2$ nuly. Ty můžeme umístit libovolně do $n+1$ "přihrádek" (kombinace s opakováním) ${n+2\choose2}$

Příklad 654

Na polici je $m+n$ různých knih, z nichž $m$ je v černém obalu a $n$ v červeném.
(a) Kolik existuje možností jak tyto knihy uspořádat tak, aby knihy v černém obalu zaujímaly prvních $m$ míst?
(b) Kolik existuje uspořádání, ve kterých všechny knihy v černém obalu stojí vedle sebe?

Řešení	Ukázat>
(a) $m!n!$ (b) $n$ červených knih vytváří $n+1$ míst. Na každé místo můžeme umístit černé kniky a přerovnat. $(n+1)m!n!$

Příklad 655

Krotitel šelem chce přivést do manéže $n$ lvů a $k$ tygrů, přičemž žádní dva tygři nesmí jít bezprostředně za sebou. Kolika způsoby může šelmy seřadit?

Řešení	Ukázat>
$n$ lvů vytváří $n+1$ míst pro tygry. Takže musí platit $k\le n+1.$ Pak vybíráme pozice pro tygry a započítáme přerovnání ${n+1\choose k}k!n!$

Příklad 656

Kolik existuje trojúhelníků, jejichž vrcholy jsou totožné s vrcholy daného pravidelného $n$ -úhelníka a přitom žádná strana trojúhelníka není totožná se stranou $n$ -úhelníka?

Řešení	Ukázat>
Nutná podmínka je $n>3.$ Pak všech možných trojúhelníků je ${n\choose3}.$ Odečteme počet trojúhelníků s aspoň jednou totožnou stranou. Ke každé straně (těch je $n$ ) je k dispozici $n-2$ vrcholů. Tj. $n(n-2)$ nevhodných trojúhelníků. Mezi nimi jsou ale trojúhelníky se tvěma totožnými stranami (těch je $n$ ) a ty jsme odečetli dvakrát, musíme je proto jednou přičíst. Celkový počet $X(n)$ je $X(n)={n\choose3}-n(n-2)+n=\dfrac{n(n-4)(n-5)}6$

Řešení

Ukázat>

Nutná podmínka je

$n>3.$ Pak všech možných trojúhelníků je

${n\choose3}.$ Odečteme počet trojúhelníků s aspoň jednou totožnou stranou. Ke každé straně (těch je

$n$ ) je k dispozici

$n-2$ vrcholů. Tj.

$n(n-2)$ nevhodných trojúhelníků. Mezi nimi jsou ale trojúhelníky se tvěma totožnými stranami (těch je

$n$ ) a ty jsme odečetli dvakrát, musíme je proto jednou přičíst. Celkový počet

$X(n)$ je

$X(n)={n\choose3}-n(n-2)+n=\dfrac{n(n-4)(n-5)}6$

Příklad 657

V krabici jsou bílé, modré a červené kuličky, ze kterých náhodně vybereme $3n$ kuliček $(n\ge1).$ Kolik existuje různých barevných sestav (na pořadí nezáleží), jestliže je v krabici od každé barvy $3n$ kuliček?

Řešení	Ukázat>
Kombinace s opakováním: ${3n+2\choose2}=\dfrac{9n^2+9n+2}2$

Příklad 658

Kolika způsoby můžeme rozdělit $3n$ různých předmětů mezi osoby A, B a C, když A a B mají dohromady dostat $2n$ předmětů?

Řešení	Ukázat>
Zobecnění příkladu 163: $\displaystyle{3n\choose n}\cdot2^{2n}$

Příklad 659

Dvě osoby si rozdělují $2n$ identických předmětů prvního druhu, $2n$ identických předmětů druhého druhu a $2n$ identických předmětů třetího druhu a to tak, že každá dostane $3n$ předmětů. Kolika způsoby to mohou udělat?

Řešení	Ukázat>
Tím, že určíme rozdělení pro jednu osobu, automaticky určíme rozdělení i pro druhou osobu. Pro 1. osobu bude platit $x_1+x_2+x_3=3n,$ kde $x_i$ je počet předmětů $i$ -tého druhu. Tato rovnice má pro $x_i\in\mathbb N_0$ ${3n+2\choose2}$ řešení (příklad 377). V tomto počtu jsou ale i situace, kdy $x_i>2n.$ Jejich počet pro každé $x_i$ určíme tak, že do $x_i$ dáme (formálně) $2n+1$ předmětů a zbylé rozdělíme libovolně. Pak bude platit rovnice $x_1+x_2+x_3=3n-(2n-1)=n-1,$ která má pro $x_i\in\mathbb N_0$ ${n+1\choose2}$ řešení. Celkový počet $X(n)$ je $X(n)={3n+2\choose2}-3\cdot{n+1\choose2}=3n^2+3n+1.$

Řešení

Ukázat>

Tím, že určíme rozdělení pro jednu osobu, automaticky určíme rozdělení i pro druhou osobu. Pro 1. osobu bude platit

$x_1+x_2+x_3=3n,$

kde

$x_i$ je počet předmětů

$i$ -tého druhu. Tato rovnice má pro

$x_i\in\mathbb N_0$

${3n+2\choose2}$

řešení (příklad 377). V tomto počtu jsou ale i situace, kdy

$x_i>2n.$ Jejich počet pro každé

$x_i$ určíme tak, že do

$x_i$ dáme (formálně)

$2n+1$ předmětů a zbylé rozdělíme libovolně. Pak bude platit rovnice

$x_1+x_2+x_3=3n-(2n-1)=n-1,$

která má pro

$x_i\in\mathbb N_0$

${n+1\choose2}$

řešení.
Celkový počet

$X(n)$ je

$X(n)={3n+2\choose2}-3\cdot{n+1\choose2}=3n^2+3n+1.$

Příklad 660

Kolika způsoby můžeme rozdělit $m+n+p$ různých předmětů třem osobám tak, aby první dostal $m,$ druhý $n$ a třetí $p$ předmětů?

Řešení	Ukázat>
Vybereme $m$ předmětů z $m+n+p$ pro 1., pak $n$ předmětů z $n+p$ pro 2. a zbytek dostane 3. ${m+n+p\choose m}\cdot{n+p\choose n}=\dfrac{(m+n+p)!(n+p)!}{m!(n+p)!n!p!}=\dfrac{(m+n+p)!}{m!n!p!}$

Příklad 661

Jídelní lístek v bufetu se skládá z $n$ různých jídel. Aby strava byla rozmanitější, rozhodl se Petr vybírat oběd každý den jiným způsobem (může si vybrat libovolný počet jídel od $0$ do $n$ ). (a) Kolik dní se takto může stravovat? (b) Kolik jídel přitom sní?

Řešení	Ukázat>
(a) $\displaystyle \sum_{k=0}^n{n\choose k}=2^n$ (b) počet dní, kdy vybere $k$ jídel $\times$ počet jídel $(k)$ a posčítat: $\sum_{k=0}^nk{n\choose k}=\sum_{k=1}^nk\cdot\dfrac{n(n-1)!}{k!(n-k)!}=n\sum_{k=1}^n\dfrac{(n-1)!}{(k-1)!(n-k)!}=n\sum_{k=1}^n{n-1\choose k-1}=n\sum_{k=0}^{n-1}{n-1\choose k}=n\cdot2^{n-1}$

Příklad 662

Máme $3n+1$ předmětů, z nichž $n$ je nerozlišitelných a $2n+1$ rozlišitelných. Kolika způsoby z nich můžeme vybrat $n$ předmětů?

Řešení	Ukázat>
Když vybereme $k$ rozlišitelných předmětů - to lze ${2n+1\choose k}$ způsoby - musíme doplnit $n-k$ nerozlišitelných, ale to lze jen jedním způsobem. Takže musíme určit součet $\sum_{k=0}^n{2n+1\choose k}.$ To znamená, že sčítáme prvních $n+1$ členů v řádku Pascalova trojúhelníka. Příslušný řádek má $2n+2$ členů, takže sčítáme právě první polovinu. Protože Pascalův trojúhelník je symetrický dostáváme $\sum_{k=0}^n{2n+1\choose k}=\dfrac12\cdot2^{2n+1}=2^{2n}$

Řešení

Ukázat>

Když vybereme

$k$ rozlišitelných předmětů - to lze

${2n+1\choose k}$ způsoby - musíme doplnit

$n-k$ nerozlišitelných, ale to lze jen jedním způsobem. Takže musíme určit součet

$\sum_{k=0}^n{2n+1\choose k}.$

To znamená, že sčítáme prvních

$n+1$ členů v řádku Pascalova trojúhelníka. Příslušný řádek má

$2n+2$ členů, takže sčítáme právě první polovinu. Protože Pascalův trojúhelník je symetrický dostáváme

$\sum_{k=0}^n{2n+1\choose k}=\dfrac12\cdot2^{2n+1}=2^{2n}$

Příklad 663

Určete počet binárních palindromických čísel délky $n.$

Řešení	Ukázat>
U palindromu první polovina čísla jednoznačně určuje druhou polovinu. Na první pozici musí být jednička. Nyní čísla rozdělíme do dvou skupin (a) $n$ je sudé: zbývá $\frac n2-1$ pozic a na každé máme vždy dvě požnosti -> $2^{\frac{n-2}2}$ čísel (b) $n$ je liché: Pomineme-li prostřední pozici, zbývá $\frac{n-1}2-1$ pozic a na každé máme dvě možnosti a na prostřední také dvě možnosti -> $2^{\frac{n-1}2}$ čísel

Řešení

Ukázat>

U palindromu první polovina čísla jednoznačně určuje druhou polovinu. Na první pozici musí být jednička. Nyní čísla rozdělíme do dvou skupin
(a)

$n$ je sudé: zbývá

$\frac n2-1$ pozic a na každé máme vždy dvě požnosti ->

$2^{\frac{n-2}2}$ čísel
(b)

$n$ je liché: Pomineme-li prostřední pozici, zbývá

$\frac{n-1}2-1$ pozic a na každé máme dvě možnosti a na prostřední také dvě možnosti ->

$2^{\frac{n-1}2}$ čísel

Příklad 664

Určete počet dělitelů přirozeného čísla $N$ , jehož prvočíselný rozklad je

$N=p_1^{n_1}\cdot p_2^{n_2}\cdots p_k^{n_k}$

Řešení	Ukázat>
Každý dělitel musí být možné zapsat ve formě $p_1^{x_1}\cdot p_2^{x_2}\cdots p_k^{x_k},$ kde $0\le x_i\le n_i,$ $i\in\{1..k\}.$ Takže $i$ -tý exponent můžeme vybrat $n_i+1$ způsoby. Počet dělitelů je pak $(n_1+1)(n_2+1)\cdots(n_k+1)$

Příklad 665

Řetězec písmen, ve kterém žádné písmeno není (někde) před písmenem, které ho v abecedě předchází, nazveme "neklesající" řetězec. Např. AABBBZ, XXXZZZ jsou "neklesající" řetězce délky 6, ale AAABZE není "neklesající" řetězec. Kolik existuje "neklesajících" řetězců délky $n$ , které můžeme vytvořit z prvních $m$ písmen anglické abecedy?

Řešení	Ukázat>
V řetězci se vyskytne $x_i;\ i=1,\ 2\dots m,$ $x_i\in\mathbb N_0$ písmen jednotlivých druhů. Jejich pořadí je jednoznačně dáno. Potřebujeme jen určit počet řešení rovnice $x_1+x_2+\cdots+x_m=n$ To je $\displaystyle {m+n-1\choose n}$ požadovaných řetězců.

Příklad 666

Určete počet způsobů, kterými můžeme z prvních $n$ přirozených čísel vybrat $r$ čísel tak, aby ve výběru nebyla žádná dvě po sobě jdoucí čísla.

Řešení	Ukázat>
Seřadíme všechna čísla do řady vzestupně od jedné do $n.$ Nyní pod tuto řadu připíšeme "A" pod číslo, které je vybrané a "N" pod nevybraná čísla. Písmena "A" tak vytváří hranice $r+1$ "přihrádek", do nichž rozmisťujeme $n-r$ symbolů "N" s podmínkou, že ve vnitřních $r-1$ přihrádkách musí být aspoň jedno "N". Zbylých $n-r-(r-1)=n-2r+1$ "N" pak rozmístíme libovolně (kombinace s opakováním). Počet možností je ${r+1+n-2r+1-1\choose n-2r+1}={n-r-1\choose n-r-1-(n-2r+1)}={n-r-1\choose r}$

Řešení

Ukázat>

Seřadíme všechna čísla do řady vzestupně od jedné do

$n.$ Nyní pod tuto řadu připíšeme "A" pod číslo, které je vybrané a "N" pod nevybraná čísla. Písmena "A" tak vytváří hranice

$r+1$ "přihrádek", do nichž rozmisťujeme

$n-r$ symbolů "N" s podmínkou, že ve vnitřních

$r-1$ přihrádkách musí být aspoň jedno "N". Zbylých

$n-r-(r-1)=n-2r+1$

"N" pak rozmístíme libovolně (kombinace s opakováním). Počet možností je

${r+1+n-2r+1-1\choose n-2r+1}={n-r-1\choose n-r-1-(n-2r+1)}={n-r-1\choose r}$

666 příkladů z kombinatoriky

Úlohy bez čísel

Příklad 643

Příklad 644

Příklad 645

Příklad 646

Příklad 647

Příklad 648

Příklad 649

Příklad 650

Příklad 651

Příklad 652

Příklad 653

Příklad 654

Příklad 655

Příklad 656

Příklad 657

Příklad 658

Příklad 659

Příklad 660

Příklad 661

Příklad 662

Příklad 663

Příklad 664

Příklad 665

Příklad 666

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