Kombinatorika

Z Wikipedie, otevřené encyklopedie

Kombinatorika (kombinatorická matematika) je část matematiky zabývající se kolekcemi prvků množin s definovanou vnitřní strukturou. Otázky, které kombinatorika řeší, se obvykle týkají počtu nějakých objektů (nebo skupin objektů) s definovanou strukturou, speciálně (pokud počet může být nulový) existencí objektu s definovanou strukturou.

[editovat] Příklady kombinatorických problémů

[editovat] Úlohy klasické kombinatoriky

Pascalův trojúhelník pro určení počtu kombinací

Příkladem jedné ze základních kombinatorických úloh je: „Kolika způsoby lze seřadit balíček mariášových karet (obsahující 32 navzájem různých karet)?“. Odpovědí je počet permutací z čísla 32, což je faktoriál čísla 32
$32! = 1.2.3. \ldots .32 \approx 2,6.10^{35} \,\!$

Dalším takovým problémem je otázka: „Kolik dvouprvkových podmnožin má patnáctiprvková množina?“. Tento příklad vede na počet dvouprvkových kombinací z čísla 15:
$C(15,2) = \frac{15.14}{2} = 105 \,\!$

Výše uvedené příklady patří do oblasti „klasických“ kombinatorických úloh, které jsou dnes součástí středeškolské matematiky. Úlohy podobného typu vedou obvykle na určení počtu variací, permutací nebo kombinací, případně na nějaké vhodné nakombinování vlastností výše uvedených struktur.

[editovat] Teorie grafů jako součást kombinatoriky

Problémy z teorie grafů (obvykle ty problémy, které nevedou na algoritmická řešení, ale na řešení existenčních nebo početních otázek) jsou tradičně považovány za (dnes již značně svébytnou) součást kombinatoriky.

Graf jako množina vrcholů se strukturou danou hranami odpovídá velice dobře volné „definici“ kombinatoriky, jak je podána v úvodním odstavci tohoto článku.

Typickým kombinatorickým problémem z teorie grafů je řešení otázky: „Kolik hran musí mít graf o 15 vrcholech, aby v něm musela existovat kružnice?“. Odpověď je v tomto případě jednoduchá: 15.

Méně triviální kombinatorické problémy z teorie grafů se týkají barvení grafu. Patří sem teprve nedávno dokázané tvrzení, že každý rovinný graf lze obarvit čtyřmi barvami (tj. každou rovinnou politickou mapu lze obarvit čtyřmi barvami tak, aby da sousední státy neměly stejnou barvu) nebo tvrzení na pomezí konečné a nekonečné kombinatoriky, podle kterého lze nekonečný graf obarvit $n \,\!$ barvami, právě když každý jeho konečný podgraf lze obarvit nejvýše $n \,\!$ barvami.

Tento směr kombinatoriky se nezabývá pouze grafy, ale také nejrůznějšími zobecněními struktury grafu. Opět se otázky týkají existence nebo počtu podstruktur určitých vlastností. Do této oblasti lze zahrnout například hledání Ramseyových čísel.

[editovat] Nekonečná kombinatorika

Zobecněním kombinatorických problémů na nekonečné množiny a úvah o počtu na úvahy o mohutnosti získáváme oblast nekonečné kombinatoriky, obvykle považované spíše za součást teorie množin.

Typickými úlohami řešenými v této oblasti jsou otázky typu: „Jaké mohutnosti může mít uniformní ultrafiltr na dané množině?“ nebo „Kolik je všech skoro disjunktních systémů na dané množině?“ Patří sem mimo jiné i celá Ramseyova teorie, která hledá vlastnosti (nikoliv již konečných, ale všech kardinálních) Ramseyových čísel.