Kombinatorika

Zabývá se konečnými množinami

Základní kombinatorická pravidla:

  1. Pravidlo součtu:

    Mějme konečné množiny A1,A2,...,AnA_1, A_2, ..., A_n, které mají po řadě ∣A1∣,∣A2∣,...,∣An∣|A_1|, |A_2|, ..., |A_n| prvků, přičemž každé 2 množiny jsou disjunktní

    →\to Pak počet prvků množiny A1∪A2∪...∪AnA_1 \cup A_2 \cup ... \cup A_n je roven ∣A1∣+∣A2∣+...+∣An∣|A_1| + |A_2| + ... + |A_n|

  2. Pravidlo součinu:

    Vytváříme-li uspořádané kk-tice takové, že jejich první člen lze vybrat n1n_1 způsoby, 2. člen po výběru 1. členu n2n_2 způsoby, atd. až po kk-tý člen nkn_k způsoby, pak počet všech těchto kk-tic je roven součinu n1,n2,...,nkn_1, n_2, ..., n_k

  3. Přihrádkový princip:

    Také princip holubníku (pigeonhole principle) / zásuvkový princip / Dirichletův princip

    Umístíme-li mm předmětů do nn přihrádek, přičemž m,n∈N∧m>nm, n \in \N \land m > n, pak bude existovat alespoň 1 přihrádka, ve které budou alespoň 2 předměty

Permutace (pořadí)

Permutace z nn prvků = uspořádaná nn-tice z nn prvků, přičemž n∈Nn \in \N, sestavená tak, že se v ní žádný prvek neopakuje

Značení: P(n)P(n)

Počet permutací z nn prvků, přičemž n∈Nn \in \N:

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

Faktoriál

Faktoriál čísla n∈Nn \in \N je roven součinu všech čísel menších než nebo rovných nn; faktoriál čísla 00 je 11

Značí se n!n!

Variace

Uspořádáné kk-tice z nn prvků, přičemž k,n∈N∧k≤nk, n \in \N \land k \le n, sestavená tak, že se žádný prvek neopakuje

Značení: V(k,n)V(k, n) – variace kk-té třídy z nn prvků

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

Variace s opakováním

Uspořádané kk-tice z nn prvků, přičemž k,n∈N∧k≤nk, n \in \N \land k \le n; každý prvek se může oopakovat nejvýše kk-krát

Značení: V′(k,n)V'(k, n) – variace s opakováním kk-té třídy z nn prvků

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

Kombinace

Neuspořádané kk-tice z nn prvků, přičemž n,k∈N0∧k≤nn, k \in \N_0 \land k \le n, sestavená tak, že se žádný prvek neopakuje

Značení: K(k,n)K(k, n) – kombinace kk-té třídy z nn prvků

K(k,n)=n!(n−k)!⋅k!K(k, n) = \frac{n!}{(n - k)! \cdot k!}

Kombinační číslo

Značení: (nk)n \choose k – čteme "nn nad kk"

Definice (za předpokladu n,k∈N0∧n≤kn, k \in \N_0 \land n \le k):

(nk)=K(k,n)=n!(n−k)!⋅k!{n \choose k} = K(k, n) = \frac{n!}{(n - k)! \cdot k!}

Permutace s opakováním

Z nn prvků je uspořádaná kk-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje aspoň jednou

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

Kombinace s opakováním

kk-členná kombinace z nn prvků je neuspořádaná kk-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše kk-krát

K′(k,n)=(n+k−1k)K'(k, n) = {{n + k - 1} \choose k}

Kombinační čísla

Definice:

n,k∈Z0+, k≤n(nk)=n!k!(n−k)!\begin{align*} n, k &\in \Z_0^+, \ k \le n \\[0.5em] {n \choose k} &= \frac{n!}{k! (n - k)!} \end{align*}

Zvláštní případy:

(n0)=1(n1)=n(nn)=1\begin{align*} {n \choose 0} &= 1 \\[1em] {n \choose 1} &= n \\[1em] {n \choose n} &= 1 \\[1em] \end{align*}

Vztahy:

(nk)=(nn−k)(nk)+(nk+1)=(n+1k+1)\begin{align*} {n \choose k} &= {n \choose {n - k}} \\[1em] {n \choose k} + {n \choose {k + 1}} &= {{n + 1} \choose {k + 1}} \end{align*}

Pascalův trojúhelník

= Schéma vytvořené z kombinačních čísel tak, že v řádku číslo n+1n + 1 jsou všechna kombinační čísla (nk){n \choose k} pro k∈{0,...,n}k \in \{0, ..., n\}

Pascalův trojúhelník:

Pascalův trojúhelník

Binomická věta

Věta:

a,b∈R, n∈N(a+b)n=(n0)an+(n1)an−1b+(n2)an−2b2+...+(nn−1)abn−1+(nn)bn(a+b)n=∑k=0n(nk)an−kbk\begin{align*} a, b &\in \R, \ n \in \N \\[0.5em] (a + b)^n &= {n \choose 0} a^n + {n \choose 1} a^{n - 1} b + {n \choose 2} a^{n - 2} b^2 + ... + {n \choose {n - 1}} a b^{n - 1} + {n \choose n} b^n \\[1em] (a + b)^n &= \sum_{k = 0}^n {n \choose k} a^{n - k} b^k \end{align*}

Vyjádření daného členu v binomickém rozvoji:

Bk+1=(nk)an−kbkB_{k + 1} = {n \choose k} a^{n - k} b^k