12 Kombinatorika, počet pravděpodobnosti a základy statistikyDoporučená literatura k této kapitole: Kvasnica (2004), Musilová & Musilová (2006).
12.1 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
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ě,
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.
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 vztahemKombinace 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 se symetrickou 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.
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ří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.
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ří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 (12.5) tvoří rovněž matematický základ zobecněné binomické věty (12.5) pro libovolný počet členů $x_1+x_2+…+x_m$, kdy pro tzv. multinomický koeficient
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 (12.2) potom zapíšeme jako tzv. multinomickou větu ve formě
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}$.
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
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$.
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
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$.
Příklady
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$
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$
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}$
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)
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$
-
jjaká 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
3
$1/25$, $1/7$, $0$makrostav
2/1
$12/25$, $4/7$, $0$makrostav
1/1/1
$12/25$, $2/7$, $1$