11 Kombinatorika

Kombinatorika je jednou z nejstarších matematických disciplín, která se zabývá vnitřní strukturou tzv. konfigurací diskrétních prvků (například čísel nebo jiných objektů), jejich existencí, hledáním počtu různých typů těchto prvků v závislosti na daných podmínkách, atd. Typickými příklady takových konfigurací jsou kombinace, permutace a variace. Kombinatorické principy tvoří matematický základ definice tzv. statistických rozdělení, používaných k popisu chování fyzikálních systémů například v kvantové mechanice, statistické fyzice, atd.

Kombinace bez opakování

Počet $k$-členných kombinací (kombinací $k$-té třídy) bez opakování z $n$ prvků ($k,n\in\mathbb{N}\cup 0$), tj. každý prvek se v dané kombinaci může vyskytovat pouze jednou, je dán vztahem

$$ C(k,n)=\frac{n!}{k!\left(n-k\right)!}= \begin{pmatrix} n\\k \end{pmatrix}, $$

11.1

kdy poslední výraz v závorce, tzv. kombinační číslo, čteme $n$ nad $k$. Kombinační číslo je také určujícím faktorem v tzv. binomické větě,

$$ (x+y)^n=\sum_{k=0}^n \begin{pmatrix} n\\k \end{pmatrix} x^{n-k}y^k, $$

11.2

pomocí níž lze $n$-tou mocninu dvojčlenu $x+y$ rozložit na součet $n+1$ členů.

Kombinace bez opakování je matematickým základem tzv. Fermiho-Diracovy statistiky, popisující systémy složené z tzv. fermionů, tedy ze vzájemně nerozlišitelných kvantových částic s antisymetrickou vlnovou funkcí a poločíselným spinem (například protonů, neutronů, elektronů, neutrin, atd.). Typickým jednoduchým příkladem může být počet různých dvojic, které lze vytvořit z celkového počtu 30 lidí, kde podmínka bez opakování vyplývá z faktu, že každý určitý jedinec se v každé dvojici může vyskytovat pouze jednou. Zároveň lze na kombinaci pohlížet jako na variaci, kdy tzv. nezáleží na pořadí prvků, tj. dvojice $A$-$B$ je totožná s dvojicí $B$-$A$. Výsledkem je číslo 435.

nahoru

Kombinace s opakováním

Počet $k$-členných kombinací s opakováním z $n$ prvků, tj. daný prvek se v dané kombinaci může vyskytovat vícekrát (přičemž opět nezáleží na pořadí prvků), je dán vztahem

$$ C^\prime(k,n)=\frac{\left(n+k-1\right)!}{k!\left(n-1\right)!}= \begin{pmatrix} n+k-1\\k \end{pmatrix}. $$

11.3

Kombinace s opakováním je matematickým základem tzv. Boseho-Einsteinovy statistiky, popisující systémy složené z tzv. bosonů, tedy ze vzájemně nerozlišitelných kvantových částic sesymetrickou vlnovou funkcí a celočíselným spinem (například fotonů, mezonů, gluonů, jader $^4$He, atd.).

Typickým příkladem může být počet různých způsobů, kterými lze koupit sadu osmi sazenic salátu, pokud mají v obchodě (v dostatečném množství) 6 různých druhů sazenic (v každé sadě se může kterýkoli z šesti druhů sazenic vyskytovat v libovolném počtu od 1 do 8). Výsledkem je číslo 1287.

nahoru

Permutace bez opakování

Obecně definujeme permutaci jako uspořádanou $n$-tici prvků, kdy celkový počet prvků výběrové množiny je rovněž $n$. Pokud se tyto prvky v každé takové uspořádané $n$-tici nemohou opakovat, počet různých takových $n$-tic (permutací bez opakování) je dán vztahem

$$ P(n)=n! $$

11.4

Příklad: kolik různých uspořádání, obsahujících vždy všechna písmena, existuje pro pětici písmen $a,\,b,\,c,\,d,\,e$?

Počet takových uspořádaných pětic ($n=5$) bez opakování je dán vztahem $P(5)=5!$, celkový počet takových uspořádání (permutací) je tedy 120.

nahoru

Permutace s opakováním

Pokud je mezi $n$ prvky výběrové množiny $k$ skupin, které mají postupně $n_1,\,n_2,\,\ldots,\,n_k$ stejných prvků, potom je počet tzv. permutací s opakováním dán vztahem

$P^{\,\prime}_{n_1,\,n_2,\,\ldots,\,n_k}(n)=\dfrac{n!}{n_1!\cdot n_2!\cdot\,\ldots\,\cdot n_k!}$, kdy $n=\sum_{i=1}^k n_i$.

11.5

Příklad: kolik různých permutací existuje pro sedmiprvkovou množinu čtyř písmen s možným opakováním $a,\,a,\,a,\,b,\,b,\,c,\,d$, kdy první písmeno se zde vyskytuje třikrát a druhé písmeno dvakrát?

Celkový počet takových permutací bude $7!/(3!\cdot 2!\cdot 1!\cdot 1!)=420$.

Výraz 11.5 tvoří rovněž matematický základ zobecněné binomické věty 11.2 pro libovolný počet členů $x_1+x_2+…+x_m$, kdy pro tzv. multinomický koeficient

$$ \begin{pmatrix} n\\k_1,k_2,\,…\,,k_m \end{pmatrix} =\frac{n!}{k_1!\,k_2!\,…\,k_m!} $$

11.6

musí pro všechna $m\in\mathbb{N}$ a $k_i,n\in\mathbb{N}\cup 0$ opět platit $k_1+k_2+\,…\,+k_m=n$. Takto rozšířenou binomickou větu 11.2 potom zapíšeme jako tzv. multinomickou větu ve formě

$$ (x_1+x_2+…+x_m)^n=\sum_{k_1+k_2+…+k_m=n} \begin{pmatrix} n\\k_1,k_2,\,…\,,k_m \end{pmatrix} x_1^{k_1}x_2^{k_2}…\,x_m^{k_m}, $$

11.7

kde součin $m$ prvků $x_1^{k_1}x_2^{k_2}…\,x_m^{k_m}$ lze zapsat pomocí symbolu pro násobení jako $\prod_{i=1}^m x_i^{k_i}$.

nahoru

Variace bez opakování

Variaci definujeme obecně jako uspořádanou $k$-tici (tj. $k$-tici, ve které tzv. záleží na pořadí prvků), vybranou ze sady, obsahující $n$ prvků. Pokud se tyto prvky v každé takové uspořádané $k$-tici nemohou opakovat, počet různých takových $k$-tic, $k\leq n$ (variací bez opakování), je dán vztahem

$$ V(k,n)=\frac{n!}{(n-k)!}. $$

11.8

Typickým příkladem může být následující úloha: kolik barevných trikolór lze vytvořit z celkem šesti barev? Variace bez opakování v tomto případě vyplývá z definice trikolóry (pokud by se některá ze tří barev opakovala, nepůjde o trikolóru). Zároveň záleží na pořadí jednotlivých prvků, tj. například trikolóra s pořadím barev červená-modrá-zelená je jiná trikolóra než trikolóra s pořadím barev zelená-modrá-červená. Celkový počet trikolór tedy bude ${6!}/{3!}=120$.

nahoru

Variace s opakováním

Počet uspořádaných $k$-tic (kdy opět záleží na pořadí prvků) s opakováním z $n$ prvků, tj. kdy se daný prvek v dané $k$-tici může vyskytovat vícekrát, je dán vztahem

$$ V^\prime(k,n)=n^k. $$

11.9

Typický příklad: kolik dvojciferných čísel lze vytvořit z číslic $1,\,2,\,3,\,4,\,5$? Opět zde záleží na pořadí jednotlivých prvků, tj. například číslo 21 je jiné číslo než číslo 12, zároveň ovšem musíme zahrnout i čísla 11, 22, atd., kde se číslice opakují. Celkový počet takových dvojciferných čísel bude $5^2=25$.

nahoru

Příklady

11.1

Kolik kružnic je definováno 12 body, ležícími v jedné rovině, pokud žádné 3 body neleží v jedné přímce?

220

11.2

Určete, kolika způsoby lze ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu, v níž jsou právě dvě ženy.

210

11.3

V bedně je 54 výrobků, z nichž 21 je první jakosti, 27 je druhé jakosti a zbytek je vadných. Kolika způsoby lze vybrat skupinu 6 výrobků tak, aby obsahovala 3 výrobky první jakosti, 2 druhé jakosti a jeden vadný výrobek?

147 420

11.4

Hokejové mužstvo má celkem 24 hráčů: 13 útočníků, 8 obránců a 3 brankáře. Kolik různých sestav může trenér vytvořit, jestliže sestava má mít 3 útočníky, 2 obránce a 1 brankáře?

6 552

11.5

Kolik prvků budeme potřebovat, abychom vytvořili šestkrát více kombinací čtvrté třídy (bez opakování prvků) než kombinací druhé třídy?

11.6

Trenér curlingu má k dispozici sedm hráčů: Aleše, Bedřicha, Cyrila, Davida, Emila, Filipa a Gustava. Má sestavit čtyřčlenné družstvo.

kolik družstev může sestavit,
35
kolik družstev může sestavit, pokud z trojice Aleš, Bedřich a Cyril hraje jen jeden,
12
kolik družstev může sestavit, pokud z trojice Aleš, Bedřich a Cyril hrají nejvýše dva a z dvojice David a Emil jeden nehraje,
18
kolik družstev může sestavit, pokud z trojice Aleš, Bedřich a Cyril hrají nejvýše dva a nehraje současně Filip a Gustav.
21

11.7

Kolik existuje pěticiferných čísel?

90 000

11.8

Kolik čísel lze vytvořit ze sady neopakujících se číslic 7, 3, 5, 2, 4, 8, 1, 9 tak, aby čísla obsahovala letopočet objevení Ameriky?

1 680

11.9

Na Kypru se poznávací značky na autech skládají z bloku 3 písmen, za kterým následuje čtyřciferné číslo. První část se vybírá pouze ze čtrnácti písmen {A, B, E, H, I, J, K, M, N, P, T, X, Y, Z}.

Kolik existuje takových poznávacích značek?

$14^3\cdot 9\cdot 10^3=24\,696\,000$
Kolik značek má každé písmeno jiné?

$14\cdot 13\cdot 12\cdot 9\cdot 10^3=19\,656\,000$
V kolika značkách je na prvním místě samohláska?

$4\cdot 14^2\cdot 9\cdot 10^3=7\,056\,000$
V kolika značkách je samohláska pouze na 1. a 3. pozici?

$4^2\cdot 10\cdot 9\cdot 10^3=1\,440\,000$

11.10

Kolika způsoby můžeme sestavit z patnácti lidí libovolně velkou pracovní skupinu? Veskupině může být 1 až 15 lidí.

32 767

11.11

V nádobě se nachází $10^5$ částic ideálního plynu. Jaká je pravděpodobnost, že se všechny zcela náhodně se pohybující částice ocitnou v levé polovině nádoby, pokud částicemi budou

molekuly NH$_3$?

$2^{-10^5}$
jádra $^4$He?

$(10^5+1)^{-1}$

11.12

Uvažujme $k=3$ mince, kdy každá může nabývat dvou hodnot, tj. panna nebo orel. Je zřejmé, že pokud hodíme všemi mincemi zároveň, může nastat celkem $n=8$ možných výsledků: PPP, PPO, POP, OPP, OOP, OPO, POO, OOO.

Každý jednotlivý výsledek nazveme mikrostavem, který zohledňuje stav každé mince (nebo částice, pokud půjde o obecný fyzikální systém).

Pokud budeme rozlišovat pouze počet hozených panen nebo orlů, specifikujeme tzv. makrostav (označme ho například $E_i$), v tomto případě tedy máme 4 možné makrostavy: 3P, 2P+1O, 1P+2O, 3O.

Počet mikrostavů, tvořících makrostav, nazýváme statistická váha (násobnost mikrostavu) $W(E_i)$. Pro 4 makrostavy dostáváme v našem případě $W_0=1,\,W_1=3,\,W_2=3,\,W_3=1$, kde pořadová čísla jednotlivých makrostavů odpovídají počtu např. panen v daném makrostavu.

Pravděpodobnost výskytu určitého makrostavu $P(E_i)$ je dána podílem jeho statistické váhy $W(E_i)$ a celkového počtu mikrostavů $n$.

Entropie $S$ určitého makrostavu $E_i$ bude $S=\ln W$.

Vypište počet možných mikrostavů a pravděpodobnosti jednotlivých makrostavů v případě, že házíme

čtyřmi mincemi

$n=16$, $P_0=1/16$, $P_1=1/4$, $P_2=3/8$, $P_3=1/4$, $P_4=1/16$
dvaceti mincemi, který makrostav je nejpravděpodobnější?

$n=2^{20}$, $P_0=1/2^{20}$, $P_1=20/2^{20}$, $P_2=190/2^{20}$, $\ldots$, $P(E_i)=\dfrac{20!}{i!(20-i)!\,2^{20}}$, $\ldots$, $P_{20}=1/2^{20}$, $P_{\max}=P_{10}$
jaká je pravděpodobnost makrostavu s 12 pannami a 8 orly?

přibližně $0,12$
sto mincemi, který makrostav je nejpravděpodobnější?

$n=2^{100}$, $P_0=1/2^{100}$, $P_1=100/2^{100}$, $P_2=4950/2^{100}$, $\ldots$, $P(E_i)=\dfrac{100!}{i!(100-i)!\,2^{100}}$, $\ldots$, $P_{100}=1/2^{100}$, $P_{\max}=P_{50}$
napište entropii makrostavů $E_0$, $E_1$, $E_{\max}$

$0$, $\ln 100\approx 4,6$, $\ln 100!-2\ln 50!\approx 66,78$ – nejpravděpodobnější makrostav má tedy nejvyšší entropii, nejméně pravděpodobný nejnižší (nulovou)

11.13

Mějme $3$ částice ideálního plynu a $5$ přihrádek – kvantových krabic, označme je například $a,\,b,\,c,\,d,\,e$. Částice mohou být do jednotlivých přihrádek rozmístěny libovolným způsobem, odpovídajícím ovšem jejich typu (například není možné aby více fermionů bylo v jedné přihrádce).

Každou jednotlivou variaci, případně kombinaci, systému částic označme jako mikrostav. Jako makrostav označme soubor mikrostavů, kdy jsou buď všechny tři částice v jedné přihrádce (označme jej jako makrostav 3), nebo jsou dvě částice v jedné přihrádce a třetí v jiné (označme jej jako makrostav 2/1), nebo je každá částice v jedné samostatné přihrádce (označme jej jako makrostav 1/1/1). V uvedeném systému se tedy mohou vyskytovat nejvýše 3 makrostavy.

kolik mikrostavů může nastat postupně pro molekuly NH$_3$, jádra $^4$He, protony?

125, 35, 10
kolik makrostavů může nastat postupně pro molekuly NH$_3$, jádra $^4$He, protony?

3, 3, 1
jaká je pravděpodobnost výskytu mikrostavu, kdy všechny tři částice budou v jedné určité přihrádce (například $a$), postupně pro molekuly NH$_3$, jádra $^4$He, protony?

1/125, 1/35, 0
jaká je pravděpodobnost výskytu mikrostavu, kdy každá ze tří částic bude samostatně v přihrádkách $a,\,c,\,e$, postupně pro molekuly NH$_3$, jádra $^4$He, protony?

6/125, 1/35, 1/10
jaká je pravděpodobnost výskytu jednotlivých makrostavů postupně pro molekuly NH$_3$, jádra $^4$He, protony?

makrostav molekuly NH$_3$ jádra $^4$He protony

3 1/125 1/7 0

2/1 12/25 4/7 0

1/1/1 12/25 2/7 1

makrostav	molekuly NH$_3$	jádra $^4$He	protony
3	1/125	1/7	0
2/1	12/25	4/7	0
1/1/1	12/25	2/7	1