kombinatorika

Příklad 377

Určete počet řešení rovnice $x_1+\cdots+x_k=n,$ kde $x_i\in\mathbb N_0$ a $n,k\in\mathbb N.$

Řešení	Ukázat
Do $k$ přihrádek musíme rozmístit $n$ jedniček. Jedná se o kombinace s opakováním. Počet řešení je ${n+k-1\choose n}.$

Příklad 378

Určete počet řešení rovnice $x_1+\cdots+x_k=n,$ kde $x_i,n,k\in\mathbb N.$

Řešení	Ukázat
Substitucí $y_i=x_i-1$ převedeme problém na předchozí případ. $x_1-1+x_2-1+\cdots+x_k-1=n-k$ $y_1+y_2+\cdots+y_k=n-k$ Rovnice má ${n-k+k-1\choose n-k}={n-1\choose k-1}$ řešení.

Příklad 379

Kolik řešení mají dané rovnice v $\mathbb N$ ?

$x+y=20$
$x+y+z=20$
$x_1+\cdots+x_6=40$

Řešení	Ukázat
Podle příkladu 378 je ${20-1\choose2-1}=19$ ${20-1\choose3-1}={19\choose2}=171$ ${40-1\choose6-1}={39\choose5}$

Příklad 380

Kolik řešení mají dané rovnice v $\mathbb N_0$ ?

$x+y=18$
$x+y+z=17$
$a+b+c+d=20$
$x+\cdots+x_6=34$
$x_1+\cdots+x_n=n^2-n+1$

Řešení	Ukázat
Podle příkladu 377 je ${18+2-1\choose18}={19\choose18}=19$ ${17+3-1\choose17}={19\choose17}=171$ ${20+4-1\choose20}={23\choose20}$ ${34+6-1\choose34}={39\choose34}$ ${n^2-n+1+n-1\choose n^2-n+1}={n^2\choose n-1}$

Příklad 381

Najděte počet řešení rovnice $x+y+z=32$ v množině $\mathbb N_0,$ když $x\ge7$ a současně $y\ge15.$

Řešení	Ukázat
Substitucemi $x^\prime=x-7$ a $y^\prime=y-15$ převedeme rovnici na základní typ $x^\prime+y^\prime+z=32-7-15=10,$ která má v $\mathbb N_0$ ${10+3-1\choose10}={12\choose10}$ řešení.

Příklad 382

Kolik různých celočíselných řešení, která splňují $x_1\ge1,$ $x_2\ge0,$ $x_3>3,$ $x_4\ge2$ má rovnice $x_1+x_2+x_3+x_4=17$ ?

Řešení	Ukázat
Substituce $x_1^\prime=x_1-1,$ $x_3^\prime=x_3-4,$ $x_4^\prime=x_4-2$ převedou rovnici na $x_1^\prime+x_2+x_3^\prime+x_4^\prime=17-1-4-2=10.$ Ta má v $\mathbb N_0$ ${10+4-1\choose10}={13\choose10}$ řešení.

Příklad 383

Kolik řešení v lichých přirozených číslech má rovnice $x+y+z+t=2000?$

Řešení	Ukázat
Substituce $x=2k-1,$ $y=2l-1,$ $z=2m-1,$ $t=2n-1$ převedou rovnici na tvar $k+l+m+n=1002$ pro $k,l,m,n\in\mathbb N.$ Ta má ${1002-1\choose4-1}={1001\choose3}$ řešení.

Příklad 384

Kolik řešení mají dané rovnice v $\mathbb N$ ?

$x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5=512$
$x_1\cdot x_2\cdot x_3\cdot x_4=1024$
$x_1\cdot x_2\cdot x_3=2048$

Řešení	Ukázat
1. Platí $x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5=2^9.$ Musí tedy být $x_i=2^{a_i}$ pro $a_i\in\mathbb N_0.$ Proto musí platit $a_1+a_2+a_3+a_4+a_5=9.$ Ta má ${9+5-1\choose9}={13\choose9}$ řešení. Stejný postup i zbývající rovnice. 2. ${13\choose10}$ 3. ${13\choose11}$

Příklad 385

Pro $x_i\in\mathbb Z$ určete počet řešení rovnice $x_1\cdot x_2\cdot x_3\cdot x_4=81.$

Řešení	Ukázat
Protože $81=3^4,$ musí být řešení ve tvaru $x_i=\pm3^{a_i}.$ Počet řešení rovnice $a_1+a_2+a_3+a_4=4$ pro $a_i\in\mathbb N_0$ je ${7\choose4}.$ Protože výsledek je kladný, musí být v původní rovnici sudý počet znamének "mínus". Pro ně můžeme vybrat pozice ${4\choose0}+{4\choose2}+{4\choose4}$ způsoby. Celkem je pak ${7\choose4}\cdot\left[{4\choose0}+{4\choose2}+{4\choose4}\right]$ řešení.

Řešení

Ukázat

Protože

$81=3^4,$ musí být řešení ve tvaru

$x_i=\pm3^{a_i}.$ Počet řešení rovnice

$a_1+a_2+a_3+a_4=4$ pro

$a_i\in\mathbb N_0$ je

${7\choose4}.$
Protože výsledek je kladný, musí být v původní rovnici sudý počet znamének "mínus". Pro ně můžeme vybrat pozice

${4\choose0}+{4\choose2}+{4\choose4}$ způsoby. Celkem je pak

${7\choose4}\cdot\left[{4\choose0}+{4\choose2}+{4\choose4}\right]$ řešení.

Příklad 386

Kolik řešení $x_1,$ $x_2,$ $x_3\in\mathbb N_0$ rovnice $x_1+x_2+x_3=11$ splňuje podmínku $x_1\le3,$ $x_2\le4$ a $x_3\le6?$

Řešení	Ukázat
Všech řešení bez podmínek je ${13\choose11}=78.$ Nyní spočítáme opačné jevy: $A_1$ je množina řešení splňující podmínku $x_1\ge4,$ těch je ${9\choose7}=36.$ $A_2$ je množina řešení splňující podmínku $x_2\ge5,$ těch je ${8\choose6}=28.$ $A_1$ je množina řešení splňující podmínku $x_3\ge7,$ těch je ${6\choose4}=15.$ $\|A_1\cap A_2\|={11-4-5+2\choose2}=6.$ $\|A_1\cap A_3\|={11-4-7+2\choose0}=1.$ $\|A_2\cap A_3\|=0$ (z čísel 5 a 7 či větších není možné získat součet 11) a ze stejného důvodu i $\|A_1\cap A_2\cap A_3\|=0.$ Nyní podle PIE je počet vyhovovujících řešení $78-(36+28+15-(6+1))=6.$

Řešení

Ukázat

Všech řešení bez podmínek je

${13\choose11}=78.$
Nyní spočítáme opačné jevy:

$A_1$ je množina řešení splňující podmínku

$x_1\ge4,$ těch je

${9\choose7}=36.$

$A_2$ je množina řešení splňující podmínku

$x_2\ge5,$ těch je

${8\choose6}=28.$

$A_1$ je množina řešení splňující podmínku

$x_3\ge7,$ těch je

${6\choose4}=15.$

$|A_1\cap A_2|={11-4-5+2\choose2}=6.$

$|A_1\cap A_3|={11-4-7+2\choose0}=1.$

$|A_2\cap A_3|=0$ (z čísel 5 a 7 či větších není možné získat součet 11) a ze stejného důvodu i

$|A_1\cap A_2\cap A_3|=0.$
Nyní podle PIE je počet vyhovovujících řešení

$78-(36+28+15-(6+1))=6.$

Příklad 387

Kolik řešení pro $a,b,c,d\in\mathbb N_0$ má nerovnice $a+b+c+d\le16?$

Řešení	Ukázat
Musíme sečíst počty řešení rovnic $a+b+c+d=0\\ a+b+c+d=1\\ a+b+c+d=2\\ \vdots\\ a+b+c+d=16$ Podle příkladu 377 je to ${3\choose0}+{4\choose1}+{5\choose2}+\cdots+{19\choose16}$ Tento výraz můžeme ještě zjednodušit. Vzhledem k tomu, že ${3\choose0}={4\choose0}$ můžeme psát $\underbrace{{4\choose0}+{4\choose1}}_{{5\choose1}}+{5\choose2}+\cdots+{19\choose16}=\\ \underbrace{{5\choose1}+{5\choose2}}_{{6\choose2}}+{6\choose3}+\cdots+{19\choose16}=\\\vdots\\ {19\choose15}+{19\choose16}={20\choose16}$ Nerovnice má ${20\choose16}$ řešení.

Řešení

Ukázat

Musíme sečíst počty řešení rovnic

$a+b+c+d=0\\ a+b+c+d=1\\ a+b+c+d=2\\ \vdots\\ a+b+c+d=16$

Podle příkladu 377 je to

${3\choose0}+{4\choose1}+{5\choose2}+\cdots+{19\choose16}$

Tento výraz můžeme ještě zjednodušit. Vzhledem k tomu, že

${3\choose0}={4\choose0}$ můžeme psát

$\underbrace{{4\choose0}+{4\choose1}}_{{5\choose1}}+{5\choose2}+\cdots+{19\choose16}=\\ \underbrace{{5\choose1}+{5\choose2}}_{{6\choose2}}+{6\choose3}+\cdots+{19\choose16}=\\\vdots\\ {19\choose15}+{19\choose16}={20\choose16}$

Nerovnice má

${20\choose16}$ řešení.

Příklad 388

Kolika způsoby rozložímeme číslo 7 na součet tří přirozených sčítanců? (Na jejich pořadí záleží.)

Řešení	Ukázat
Podle příkladu 378 je ${7-1\choose3-1}={6\choose2}$ rozkladů.

Příklad 389

Určete, kolik existuje trojciferných přirozených čísel s ciferným součtem rovným 16.

Řešení	Ukázat
Určujeme počet celočíselných řešení rovnice $x_1+x_2+x_3=16$ s podmínkami (1) $x_1>0$ a (2) $x_i\le9.$ (1) po substituci $y_1=x_1+1$ dostaneme $y_1+x_2+x_3=15$ Tato rovnice má ${15+3-1\choose15}={17\choose2}$ řešení. Počet řešení, která nesplňují (2): Vždy porušuje podmínku (2) jen jeden ze členů. (a) $x_1>9$ substituce $y_1=x_1+10$ $y_1+x_2+x_3=6$ Tato rovnice má ${6+3-1\choose6}={8\choose2}$ řešení. (b) $x_2>9\$ (pro $x_3$ stejně) substituce $y_1=x_1+1,$ $y_2=x_2+10$ $y_1+y_2+x_3=5$ Tato rovnice má ${5+3-1\choose16}={7\choose2}$ řešení. Celkem ${17\choose2}-{8\choose2}-2{7\choose2}$ čísel.

Řešení

Ukázat

Určujeme počet celočíselných řešení rovnice

$x_1+x_2+x_3=16$
s podmínkami (1)

$x_1>0$ a (2)

$x_i\le9.$
(1) po substituci

$y_1=x_1+1$ dostaneme

$y_1+x_2+x_3=15$
Tato rovnice má

${15+3-1\choose15}={17\choose2}$ řešení.
Počet řešení, která nesplňují (2):
Vždy porušuje podmínku (2) jen jeden ze členů.
(a)

$x_1>9$
substituce

$y_1=x_1+10$

$y_1+x_2+x_3=6$
Tato rovnice má

${6+3-1\choose6}={8\choose2}$ řešení.
(b)

$x_2>9\$ (pro

$x_3$ stejně)
substituce

$y_1=x_1+1,$

$y_2=x_2+10$

$y_1+y_2+x_3=5$
Tato rovnice má

${5+3-1\choose16}={7\choose2}$ řešení.
Celkem

${17\choose2}-{8\choose2}-2{7\choose2}$ čísel.

Příklad 390

Kolik je trojciferných čísel, které mají ciferný součet roven 14.

Řešení	Ukázat
Stejné jako předchozí příklad: ${15\choose2}-{6\choose2}-2{5\choose2}$ čísel.

Příklad 391

Máıne k dispozici pět bonbónů malinových, tři ponıerančové a pět citrónových. Chceme-li si vzít devět bonbónů, kolika způsoby je to možné? (Bonbóny stejného druhu považujeme za nerozlišitelné.)

Řešení	Ukázat
Řešíme rovnici $m+p+c=9$ s podmínkami $m\le5,$ $p\le3,$ $c\le5$ pro $m,p,c\in\mathbb N_0.$ Stejně jako v příkladu 386 budeme postupovat přes opačné jevy. Všech řešení bez podmínek je ${9+3-1\choose9}={11\choose9}.$ $A_m$ označuje množinu řešení, v nichž $m\ge6.$ Pak $\|A_m\|={3+3-1\choose3}={5\choose3}$ $A_p$ označuje množinu řešení, v nichž $p\ge4.$ Pak $\|A_p\|={5+3-1\choose5}={7\choose5}$ $\|A_c\|=\|A_m\|$ Průniky jednotlivých množin jsou prázdné. Ze dvou čísel, z nichž jedno je větší než 5 a druhé větší než 4, nesložíme součet 9. A ostatní možnosti jsou ještě větší. Celkový počet řešení je ${11\choose9}-2\cdot{5\choose3}-{7\choose5}=14.$

Řešení

Ukázat

Řešíme rovnici

$m+p+c=9$ s podmínkami

$m\le5,$

$p\le3,$

$c\le5$ pro

$m,p,c\in\mathbb N_0.$ Stejně jako v příkladu 386 budeme postupovat přes opačné jevy.
Všech řešení bez podmínek je

${9+3-1\choose9}={11\choose9}.$

$A_m$ označuje množinu řešení, v nichž

$m\ge6.$ Pak

$|A_m|={3+3-1\choose3}={5\choose3}$

$A_p$ označuje množinu řešení, v nichž

$p\ge4.$ Pak

$|A_p|={5+3-1\choose5}={7\choose5}$

$|A_c|=|A_m|$
Průniky jednotlivých množin jsou prázdné. Ze dvou čísel, z nichž jedno je větší než 5 a druhé větší než 4, nesložíme součet 9. A ostatní možnosti jsou ještě větší.
Celkový počet řešení je

${11\choose9}-2\cdot{5\choose3}-{7\choose5}=14.$

Příklad 392

Test se skládá z pěti otázek, každá maximálně za 20 bodů. Student získal postupně 10, 5, 18, 5 a 2 body. Kolika způsoby může opravující přidat studentovi 5 bodů?

Řešení	Ukázat
Jedná se o příklad 246 řešený jiným způsobem. Problém můžeme řešit tak, že určíme počet řešení rovnice $x_1+x_2+x_3+x_4+x_2=5$ s podmínkou $x_3\le2$ pro $x_i\in\mathbb N_0.$ Počet řešení bez podmínky je ${5+5-1\choose5}={9\choose5}.$ Pro opačný jev $x_3\ge3$ dostaneme rovnici $x_1+x_2+(x_3-3)+x_4+x_5=5-3$ a ta má ${2+5-1\choose2}={6\choose2}$ řešení. Celkový počet řešení je ${9\choose5}-{6\choose2}.$

Řešení

Ukázat

Jedná se o příklad 246 řešený jiným způsobem.
Problém můžeme řešit tak, že určíme počet řešení rovnice

$x_1+x_2+x_3+x_4+x_2=5$

s podmínkou

$x_3\le2$ pro

$x_i\in\mathbb N_0.$
Počet řešení bez podmínky je

${5+5-1\choose5}={9\choose5}.$
Pro opačný jev

$x_3\ge3$ dostaneme rovnici

$x_1+x_2+(x_3-3)+x_4+x_5=5-3$

a ta má

${2+5-1\choose2}={6\choose2}$ řešení.
Celkový počet řešení je

${9\choose5}-{6\choose2}.$

Příklad 393

Určete počet všech pěticiferných čísel dělitelných devíti, jejichž dekadickém zápisu se vyskytují pouze cifry $\{2,4,6\}.$

Řešení	Ukázat
Ciferný součet pěticiferných čísel vytvořených z daných číslic leží v intervalu $\langle10;30\rangle.$ Protože ciferný součet musí být dělitelný devíti, přicházejí do úvahu jen možnosti $\{18;27\}.$ Ale součet sudých čísel je vždy sudý, takže ciferný součet musí být 18. Dále můžeme postupovat tak, že si určíme počet přirozených řešení rovnice $x_1+x_2+x_3+x_4+x_5=18$ Jelikož je $x_i=2k_i$ pro $k_i\in\{1;2;3\},$ můžeme rovnici upravit na $k_1+k_2+k_3+k_4+k_5=9$ pro $k_i\in\mathbb N$ a $k_i\le3.$ Rovnice bez podmínky má (příklad 378) ${9-1\choose5-1}={8\choose4}$ řešení. Množina $A_i$ označuje množinu řešení, v nichž $k_i>3.$ Je $\|A_i\|={6-1\choose5-1}={5\choose4}$ Průniky jednotlivých množin jsou prázdné (nejmenší možný součet $4+4+1+1+1>9$ ). Celkový počet hledaných čísel je ${8\choose4}-5\cdot{5\choose4}.$

Řešení

Ukázat

Ciferný součet pěticiferných čísel vytvořených z daných číslic leží v intervalu

$\langle10;30\rangle.$ Protože ciferný součet musí být dělitelný devíti, přicházejí do úvahu jen možnosti

$\{18;27\}.$ Ale součet sudých čísel je vždy sudý, takže ciferný součet musí být 18. Dále můžeme postupovat tak, že si určíme počet přirozených řešení rovnice

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

Jelikož je

$x_i=2k_i$ pro

$k_i\in\{1;2;3\},$ můžeme rovnici upravit na

$k_1+k_2+k_3+k_4+k_5=9$

pro

$k_i\in\mathbb N$ a

$k_i\le3.$
Rovnice bez podmínky má (příklad 378)

${9-1\choose5-1}={8\choose4}$ řešení.
Množina

$A_i$ označuje množinu řešení, v nichž

$k_i>3.$ Je

$|A_i|={6-1\choose5-1}={5\choose4}$
Průniky jednotlivých množin jsou prázdné (nejmenší možný součet

$4+4+1+1+1>9$ ).
Celkový počet hledaných čísel je

${8\choose4}-5\cdot{5\choose4}.$

Příklad 521

Kolik řešení $x_i\in\mathbb N_0$ rovnice $x_1+x_2+x_3=15$ splňuje podmínky $x_1,x_2\le5$ a $x_3\le7?$

Řešení	Ukázat
Příklad můžeme řešit podobně jako příklad 386 pomocí PIE. Ale je i jiná cesta (ta se dá použít i u příkladu 386). Představme si, že máme tři přihrádky. Do prvních dvou dáme pět kuliček a do třetí 7 kuliček. Celkem máme nyní 17 kuliček, to znamená, že musíme dvě ubrat. Problém se změnil na otázku "Kolika způsoby můžeme rozdělit dvě "záporné" kuličky do tří přihrádek?" Jedná se o klasický příklad na kombinace s opakováním. Odpověď: ${4\choose2}$ vhodných řešení.

Řešení

Ukázat

Příklad můžeme řešit podobně jako příklad 386 pomocí PIE. Ale je i jiná cesta (ta se dá použít i u příkladu 386).
Představme si, že máme tři přihrádky. Do prvních dvou dáme pět kuliček a do třetí 7 kuliček. Celkem máme nyní 17 kuliček, to znamená, že musíme dvě ubrat. Problém se změnil na otázku "Kolika způsoby můžeme rozdělit dvě "záporné" kuličky do tří přihrádek?" Jedná se o klasický příklad na kombinace s opakováním.
Odpověď:

${4\choose2}$ vhodných řešení.

666 příkladů z kombinatoriky

Rovnice

Příklad 377

Příklad 378

Příklad 379

Příklad 380

Příklad 381

Příklad 382

Příklad 383

Příklad 384

Příklad 385

Příklad 386

Příklad 387

Příklad 388

Příklad 389

Příklad 390

Příklad 391

Příklad 392

Příklad 393

Příklad 521

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