Matematik/Diskret matematik/Kombinatorik

Kombinatorik

Kombinatorik handlar om olika sätt att kombinera element. Kombinatorik är till god hjälp när man behöver beräkna sannolikheter och bedöma sina chanser vid spel av olika slag. Genom att tillämpa kombinatorik kan vi exempelvis räkna ut att vid kast med två tärningar är det lättare att få en sjua än något annat resultat, vilket är bra att veta när man spelar backgammon eller monopol.

Typiska problem som kombinatorik hjälper oss att lösa:

Hur många olika pokerhänder finns det?

På hur många sätt kan jag få par i knektar eller högre redan vid given?

Hur många olika pärlarmband med 24 pärlor kan jag göra om det finns fyra färger på pärlorna att välja på?

Hur många sätt finns det att välja ut sju av talen 1-35 om det inte spelar någon roll i vilken ordning man tar dem? Om ordningen har betydelse? Om det är tillåtet att välja samma tal flera gånger?

Binomialsatsen

$(a+b)^{n}=\sum _{k=0}^{n}\left({\begin{array}{c}n\\k\end{array}}\right)a^{k}b^{n-k}$.

Binomialsatsen kan generaliseras till multinomialsatsen: $\left(\sum _{k=0}^{m-1}x_{k}\right)^{n}=\sum _{\sum _{k=0}^{m-1}n_{k}=n}\left({n \choose {n_{0},\ldots ,n_{m-1}}}\prod _{k=0}^{m-1}x_{k}^{n_{k}}\right)$

Här används multinomialkoefficienten, definierad som ${n \choose {n_{0},\ldots ,n_{p}}}:={\frac {n!}{n_{0}!\cdots n_{p}!}}$

Multinomialsatsen åskådliggörs i nedanstående exempel. Exempel: Utveckla $(x+y+z)^{4}$. Lösning: $(x+y+z)^{4}=$${4 \choose {4,0,0}}x^{4}+{4 \choose {3,1,0}}x^{3}y+{4 \choose {3,0,1}}x^{3}z+{4 \choose {2,2,0}}x^{2}y^{2}+$${4 \choose {2,1,1}}x^{2}yz+{4 \choose {2,0,2}}x^{2}z^{2}+{4 \choose {1,3,0}}xy^{3}+{4 \choose {1,2,1}}xy^{2}z+$${4 \choose {1,1,2}}xyz^{2}+{4 \choose {1,0,3}}xz^{3}+{4 \choose {0,4,0}}y^{4}+{4 \choose {0,3,1}}y^{3}z+$${4 \choose {0,2,2}}y^{2}z^{2}+{4 \choose {0,1,3}}yz^{3}+{4 \choose {0,0,4}}z^{4}$ $=x^{4}+4x^{3}y+4x^{3}z+6x^{2}y^{2}12x^{2}yz+6x^{2}z^{2}+4xy^{3}+12xy^{2}z+12xyz^{2}+4xz^{3}+y^{4}+4y^{3}z+6y^{2}z^{2}+4yz^{3}+z^{4}$

Genererande funktioner

Definition: Den genererande funktionen till $\{a_{k}\}_{k=0}^{\infty }$ är $\sum _{k=0}^{\infty }a_{k}x^{k}$.