Link Menu Expand Document (external link)

Kombinatorika a binomická věta

17 Feb 2023

Kombinatorika

Kombinatorika se zabývá pouze vlastnostmi konečných množin.

Kombinatorické pravidlo součtu

Pokud A1,A2,,AnA_{1}, A_{2}, \ldots ,A_{n} jsou neprázdné množiny, kde žádné dvě nemají společný prvek, který mají p1,p2,,pnp_{1}, p_{2},\ldots ,p_{n} prvků, potom počet prvků množiny A1A2AnA_{1} \cup A_{2} \cup \ldots \cup A_{n} je p1+p2++pnp_{1} + p_{2} + \ldots + p_{n}.

Kombinatorické pravidlo součinu

Počet všech uspořádaných kk-tic, kde první člen lze vybrat p1p_{1} způsoby, druhý člen p2p_{2} způsoby… až kk-tý člen pkp_{k} způsoby, je p1p2pkp_{1} \cdot p_{2} \cdot \ldots \cdot p_{k}.

Kombinatorické funkce

Permutace bez opakování

Permutace z nn prvků je každé libovolné seřazení těchto prvků tak, že každý se v ní vyskytuje právě jednou.

Počet permutací značíme P(n)P(n), platí:

P(n)=n!P(n) = n!

Faktoriál

Funkce na množině přirozených čísel. Značí se “!!”.

Permutace s opakováním

Permutace s opakováním z nn prvků je uspořádaná kk-tice sestavená z nn prvků tak, že každý se opakuje alespoň jednou.

Počet permutací s opakováním značíme P(k1,k2,,kn)P'(k_1, k_2, \ldots, k_n) a platí:

P(k1,k2,,kn)=(k1+k2++kn)!k1!k2!kn!P'(k_1, k_2, \ldots, k_n) = \frac{(k_1+k_2+ \ldots +k_n)!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!}

Kombinace

KK-členná kombinace z nn prvků je neuspořádaná kk-tice sestavená z těchto prvků, ve které se prvky neopakují.

Počet všech takových kombinací značíme K(k,n)K(k,n) a platí:

K(k,n)=(nk)=n!k!(nk)!K(k,n)= \binom{n}{k} = \frac{n!}{k!(n-k)!}

Kombinační číslo

Kombinační číslo je matematická funkce, která udává počet kombinací, tzn. způsobů, jak vybrat kk-prvkovou podmnožinu z nn-prvkové množiny. Kombinační čísla zapisujeme:

(nk)\binom{n}{k}

Základní pravidla pro počítání s kombinačními čísly:

(n0)=11=1(n1)=n(nn)=1(nn1)=n(nk)+(nk+1)=(n+1k+1)\begin{align} \binom{n}{0} &= \frac{1}{1} = 1\\ \binom{n}{1} &= n\\ \binom{n}{n} &= 1\\ \binom{n}{n-1} &= n\\ \binom{n}{k} + \binom{n}{k+1} &= \binom{n+1}{k+1} \end{align}

Kombinace s opakováním

Je to neuspořádaná kk-tice vybraná z n prvků, kde se prvky mohou opakovat.

Počet všech kombinací s opakováním značíme K(k,n)K'(k, n) a platí:

K(k,n)=(k+n1)!k!(n1)!=(n+k1k)K'(k,n) = \frac{(k+n-1)!}{k! \cdot (n-1)!} = \binom{n+k-1}{k}

Variace

KK-členná variace z nn prvků je libovolná uspořádaná kk-tice vybrána z těchto prvků, kde každý se z ní vyskytuje nejvýše jednou.

Počet všech kk-členných variací z nn prvků značíme V(k,n)V(k,n) a platí:

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

Variace s opakováním

Je to uspořádaná kk-tice z n prvků, kde se prvky mohou opakovat.

Počet všech variací s opakováním značíme V(k,n)V'(k,n) a platí:

V(k,n)=nkV'(k,n) = n^k

Pascalův trojúhelník

111121133114641151010511615201561172135352171\begin{array}{c} 1 \\ 1 \quad\, 1 \\ 1 \quad\, 2 \quad\, 1 \\ 1 \quad\, 3 \quad\, 3 \quad\, 1 \\ 1 \quad\, 4 \quad\, 6 \quad\, 4 \quad\, 1 \\ 1 \quad\, 5 \quad 10 \quad 10 \quad 5 \quad\, 1 \\ 1 \quad\, 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad\, 1 \\ 1 \quad\, 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad\, 1 \\ \vdots \end{array}

Binomická věta

Určuje rozvoj nn-té mocniny dvojčlenu.

(a+b)n=i=1n(ni)anibi(a+b)^n = \sum^{n}_{i=1} \binom{n}{i}a^{n-i}b^i