Kombinatorika

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.

Příklady kombinatorických problémů

Úlohy klasické kombinatoriky

Mezi základní úlohy klasické kombinatoriky patří určování počtu definovaných skupin prvků sestavených z dané množiny.

Při tom je vždy třeba uvážit:

zda záleží nebo nezáleží na pořadí výběru prvků (zda se má nebo nemá dbát na jejich uspořádání) – podle toho se rozlišují variace a kombinace;
zda se jednotlivé prvky ve skupině mohou nebo nemohou vícekrát opakovat (vznikají skupiny s opakováním nebo bez opakování prvků).

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\cdot 2\cdot 3\cdots 32\approx 2{,}6\cdot 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)={15 \choose 2}={\frac {15\cdot 14}{2!}}=105

Výše uvedené příklady patří do oblasti „klasických“ kombinatorických úloh, které jsou dnes součástí středoš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.

Teorie grafů jako součást kombinatoriky

Problémy z teorie grafů (obvykle ty problémy, které vedou na řešení existenčních nebo početních otázek, nikoli na algoritmická řešení) 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: „Kolik hran musí mít graf o patnácti vrcholech, aby v něm musela existovat kružnice?“.

Netriviální kombinatorické problémy z teorie grafů se týkají barvení grafu. Patří sem teprve v roce 1976 dokázané tvrzení, že každý rovinný graf lze obarvit čtyřmi barvami (takže každou rovinnou politickou mapu lze obarvit čtyřmi barvami tak, aby dva 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 nestuduje pouze grafy, ale také nejrůznější zobecnění struktury grafu. Opět se zkoumají otázky týkající se existence nebo počtu podstruktur určitých vlastností. Do této oblasti lze zahrnout například hledání Ramseyových čísel.

Nekonečná kombinatorika

Zobecněním kombinatorických problémů na nekonečné množiny a úvah o počtu na úvahy o mohutnosti vznikne 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ří zde i celá Ramseyova teorie, která studuje vlastnosti (nikoli jen konečných, ale všech kardinálních) Ramseyových čísel.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu kombinatorika na Wikimedia Commons
Realisticky.cz - on-line učebnice Mgr. Martina Krynického
Webová učebnice kombinatoriky, Monika Stančíková, diplomová práce na MU, 2015
Kombinatorika a grafy I., Tomáš Valla, Jiří Matoušek, KAM MFF UK, 2008