Skip to content
{ 2008 11 10 }

Kombinatorika

Abych nemusel pořád hledat na internetu, když si zrovna nemůžu vzpomenout na nějaký kombinatorický vzorec, rozhodl jsem se, že si tady napíšu takové malé shrnutí. Většina informací (včetně příkladů) pochází z téhle stránky – je to součást diplomové práce, publikované na webu. Kromě teorie se tam dá najít i spousta příkladů. V případě zájmu o kombinatoriku rozhodně doporučuju – jako úvod je to opravdu vynikající.

Text je také přístupný (stejně jako všechny ostatní matematické texty) přes položku Teaching-Lehre v postranním menu.

Variace

K-členná variace z n prvků je uspořádaná k-tice vytvořená z těchto prvků, ve které se každý prvek vyskytuje maximálně jednou.

První prvek vybíráme z n možností, druhý z (n-1) možností, k-tý pak z (n-k+1) možností – celkový počet variací je pak dán jako součin

\displaystyle V(k,n) = n\cdot (n-1)\cdot (n-2)\dots (n-k+1) = \frac{n!}{(n-k)!}

protože

\displaystyle V(k,n) = n \cdot (n-1) \cdot (n-2) \dots (n-k+1) \cdot \frac{(n-k)\cdot(n-k-1)\dots 3\cdot 2\cdot 1}{(n-k)\cdot(n-k-1)\dots 3\cdot 2\cdot 1} =\\= \frac{n!}{(n-k)!}

Příklad: Výběr barevné kombinace vlajky se třemi různobarevnými pruhy z 5 barev (na pořadí záleží) – celkem 60 možností (V(3,5)=60).

Permutace

Permutace z n prvků je n-členná variace z n prvků. Počet permutací je pak zjevně

\displaystyle P(n) = n \cdot (n-1) \cdot (n-2) \dots 3 \cdot 2 \cdot 1 = n! = V(n,n) = \frac{n!}{0!}

z čehož vyplývá i definice faktoriálu pro hodnotu nula – 0!=1

Příklad: Počet permutací ze 3 prvků je 3.2.1=6 (abc, acb, bac, bca, cab, cba).

Kombinace

K-členná kombinace z n prvků je neuspořádaná k-tice vytvořená z těchto prvků, ve které se každý prvek vyskytuje maximálně jednou. Každé k-členné kombinaci odpovídá k! k-členných variací.

V(k,n) = k! K(k,n)

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

Dvě užitečné vlastnosti kombinačních čísel jsou

\displaystyle \binom{n}{n-k} = \frac{n!}{(n-k)!(n-(n-k))!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}

\displaystyle \binom{n}{k} + \binom{n}{k+1} = \frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-(k+1))!} = \frac{n!}{k!(n-k-1)!}\left(\frac{1}{n-k} + \frac{1}{k+1}\right) =\\= \frac{n!}{k!(n-k-1)!}\cdot \frac{k+1+n-k}{(n-k)(k+1)} = \frac{n! (n+1)}{(k+1)k! (n-k)(n-k-1)!} = \frac{(n+1)!}{(k+1)!(n-k)!} =\\= \frac{(n+1)!}{(k+1)!(n+1-(k+1))!} = \binom{n+1}{k+1}

Kombinační čísla se také vyskytují v binomickém rozvoji (a+b)^n, kde určují koeficienty jednotlivých členů

\displaystyle (a+b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-1}b^2 + \dots + \binom{n}{n} b^n

k-tý člen lze tedy napsat jako \displaystyle \binom{n}{k-1}a^{n-(k-1)}b^{k-1} pro k hodnoty z intervalu 1, 2, …, n+1.

Příklad: Výběr 2 prvků z množiny o 10 prvcích – celkem 45 možností.

Variace s opakováním

K-členná variace s opakováním z n prvků je uspořádaná k-tice vytvořená z těchto prvků, ve které se každý prvek vyskytuje maximálně k-krát. Pro každý člen k-tice tak máme na výběr z n možností (nezávislý výběr) a proto

V'(k,n) = n^k

Příklad: Celkový počet barevných kombinací tříbarevné vlajky z 5 barev, kde se barvy mohou opakovat a záleží na pořadí – 5.5.5=625.

Permutace s opakováním

K-členná permutace s opakováním z n prvků je uspořádaná k-tice vytvořená z těchto prvků, ve které se každý prvek vyskytuje alespoň jednou.

Počet opakování jednotlivých prvků n_i) si označíme k_1, k_2, …, k_n. Počet všech prvků jejichž pořadí zkoumáme je

k = k_1 + k_2 + \dots + k_n

Počet pořadí těchto prvků je dán permutací bez opakování P(k) = k!. Každý z prvků n_i lze umístit k_i! způsoby, které jsou však ekvivalentní. Z toho vyplývá, že skutečný počet pořadí je menší a pro počet permutací s opakováním lze psát

\displaystyle P'(k,n) = \frac{(k_1 + k_2 + \dots + k_n)!}{k_1! k_2! \dots k_n!}

Příklad: Kolika způsoby je možné srovnat do řady 2 šedé, 2 modré a 2 černé kostky?(6!/2!2!2!=780/8=90)

Kombinace s opakováním

K-členná kombinace s opakováním z n prvků je neuspořádaná k-tice vytvořená z těchto prvků, ve které se každý prvek vyskytuje maximálně k-krát. Lze je vysvětlit pomocí následujícího příkladu. Určujeme počet možností, kterými je možno rozdělit k kuliček do n krabiček. Situaci lze znázornit tak, že pro kuličku použijeme znak “.” a pro hranice krabičky znak “|”. Pro n krabiček máme n-1 hranic. Pro k=3, n=4 může jedno z rozdělení vypadat např. takto: “..|.||” (2 kuličky v první krabičce, 1 ve druhé, 3. a 4. krabička prázdné). Počet těchto možností lze určit jako šestičlenné permutace s opakováním ze dvou prvků a odpovídá počtu k-členných kombinací s opakováním z n prvků.

Pro obecné hodnoty “k” a “n” lze situaci modelovat použitím (k+n-1)-tic – jde o permutaci s opakováním pro 2 prvky s výskytem k a n-1. Matematicky potom plyne

\displaystyle K'(k,n) = P'(k,n-1) = \frac{(n+k-1)!}{k!(n-1)!} = \binom{n+k-1}{k}

Příklad: Kolika způsoby je možné rozmístit sedm stejných kuliček do tří krabiček? (36)

Abstract in English: Summary of the most important combinatorial expressions (variations, permutations, combinations).

Posted by wpmaster on Monday, November 10, 2008, at 18:23. Filed under Česky, Professional. Follow any responses to this post with its comments RSS feed. Both comments and trackbacks are currently closed.