Cesko.wiki Kombinatorika
Author
Albert FloresKombinatorika je matematická disciplína, která se zabývá studiem kombinací, aranžmá a permutací prvků v dané množině. V české Wikipedii je stránka Kombinatorika věnována popisu základních pojmů, metod a aplikací kombinatoriky. Stránka obsahuje definice základních kombinatorických pojmů, jako jsou kombinace, permutace, variace, množiny a další. Dále se věnuje metodám řešení kombinatorických problémů, jako je princip inkluze-exkluze, generuj a testuj, rekurzivní metody a další. Stránka také přináší přehled aplikací kombinatoriky v různých oblastech, jako je teorie grafů, kódování a dekódování, šifrování, algoritmické problémy a statistika. Další části stránky se zabývají historií kombinatoriky a významnými osobnostmi v této oblasti. Celkově je stránka Kombinatorika v české Wikipedii komplexním zdrojem informací o této matematické disciplíně.
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
+more5'>Pascalův trojúhelník pro určení počtu kombinací 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). “. +more 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. “. +more Tento příklad vede na počet dvouprvkových kombinací z čísla 15: : C(15,2) = {15 \choose 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ř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
Příklad obarvení mapy čtyřmi barvami 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í. +more 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ě. +more“ 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
Kombinace * Pascalův trojúhelník * Permutace * Ramseyova čísla * Stirlingova čísla * Teorie grafů * Variace (kombinatorika)
Odkazy
Externí odkazy
[url=http://www. realisticky. +morecz/kapitola. php. id=30]Realisticky. cz - on-line učebnice Mgr. Martina Krynického[/url] * [url=http://www. stancikova. cz/kombinatorika/index. html]Webová učebnice kombinatoriky, Monika Stančíková, diplomová práce na MU, 2015[/url] * [url=http://kam. mff. cuni. cz/~valla/kg. pdf]Kombinatorika a grafy I. , Tomáš Valla, Jiří Matoušek, KAM MFF UK, 2008[/url].