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ů[editovat | editovat zdroj]

Úlohy klasické kombinatoriky[editovat | editovat zdroj]

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í, ve kterém prvky vybereme (zda máme nebo nemáme dbát na jejich uspořádání) – podle toho rozlišujeme variace a kombinace

– zda se jednotlivé prvky ve skupině mohou nebo nemohou vícekrát opakovat (vytváříme 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četpermutací z čísla 32, což je faktoriál čísla 32 = 263130836933693530167218012160000000

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:

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[editovat | editovat zdroj]

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 15 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 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 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  barvami, právě když každý jeho konečný podgraf lze obarvit nejvýše  barvami.

Tento směr kombinatoriky nestuduje pouze grafy, ale také nejrůznějšími zobecnění struktury grafu. Opět se vyšetřují 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.

Nekonečná kombinatorika[editovat | editovat zdroj]

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ří zde i celá Ramseyova teorie, která studuje vlastnosti (nikoli jen konečných, ale všech kardinálních) Ramseyových čísel.