Kombinatorika - Combinatorics

Kombinatorika je oblast matematiky primárně zaměřená na počítání, a to jak jako prostředek, tak jako cíl při získávání výsledků, a určitých vlastností konečných struktur . Úzce souvisí s mnoha dalšími oblastmi matematiky a má mnoho aplikací od logiky po statistickou fyziku , od evoluční biologie po informatiku atd.

Celý rozsah kombinatoriky není všeobecně dohodnut. Podle HJ Rysera je definice předmětu obtížná, protože protíná tolik matematických členění. Pokud lze oblast popsat podle typů problémů, které řeší, kombinatorika zahrnuje:

  • výčet (počítání) z uvedených struktur, které se někdy označují jako uspořádání nebo uspořádání ve velmi obecném smyslu, spojený s konečnými systémy,
  • existence takových struktur, které splňují určitá daná kritéria,
  • konstrukce těchto staveb, snad v mnoha ohledech, a
  • optimalizace : nalezení „nejlepší“ struktury nebo řešení mezi několika možnostmi, ať už „největší“, „nejmenší“ nebo splnění nějakého jiného kritéria optimality .

Leon Mirsky uvedl: „Kombinatorika je řada propojených studií, které mají něco společného, ​​a přesto se velmi liší v cílech, metodách a míře soudržnosti, které dosáhli.“ Jedním ze způsobů, jak definovat kombinatoriku, je snad popsat její členění s jejich problémy a technikami. Toto je přístup, který se používá níže. Existují však také čistě historické důvody pro zahrnutí nebo nezahrnutí některých témat pod kombinatorický deštník. Ačkoli se primárně týká konečných systémů, některé kombinatorické otázky a techniky lze rozšířit na nekonečné (konkrétně spočetné ), ale diskrétní nastavení.

Kombinatorika je dobře známá pro šíři problémů, s nimiž se potýká. Kombinatorické problémy vznikají v mnoha oblastech čisté matematiky , zejména v algebře , teorii pravděpodobnosti , topologii a geometrii , stejně jako v mnoha aplikačních oblastech. Mnoho kombinatorických otázek bylo historicky zvažováno izolovaně, což poskytlo ad hoc řešení problému vznikajícího v nějakém matematickém kontextu. V pozdějším dvacátém století však byly vyvinuty silné a obecné teoretické metody, díky nimž se kombinatorika stala samostatným samostatným odvětvím matematiky. Jednou z nejstarších a nejdostupnějších částí kombinatoriky je teorie grafů , která sama o sobě má četné přirozené vazby na jiné oblasti. Kombinatorika se v počítačové vědě často používá k získání vzorců a odhadů při analýze algoritmů .

Matematik , který studuje kombinatorika se nazývá combinatorialist .

Dějiny

Příklad změny vyzvánění (se šesti zvony), jeden z prvních netriviálních výsledků v teorii grafů .

Základní kombinatorické koncepty a výčtové výsledky se objevily v celém starověkém světě . V 6. století BCE, starověký indický lékař Sushruta uplatňuje při Sushruta Samhita , že 63 kombinace mohou být vyrobeny ze 6 různých chutí, které bylo přijato po jednom, po dvou, atd, takže výpočet všech 2 6  - 1 možností. Řecký historik Plútarchos diskutuje o hádce mezi Chrysippem (3. století př. N. L. ) A Hipparchem (2. století před n. L.) O poměrně delikátním výčtu problémů, o kterém se později ukázalo, že souvisí s čísly Schröder – Hipparchus . Dříve, v Ostomachion , Archimedes (3. století BCE), může se zabývali počet konfigurací na obklady puzzle , zatímco kombinační zájmy případně byly přítomné v ztracených děl Apollonia .

Ve středověku se kombinatorika nadále studovala, převážně mimo evropskou civilizaci . Indický matematik Mahavira (c. 850), za předpokladu, vzorce v počtu permutací a kombinací , a tyto vzorce mohou být známé indické matematiky již 6. století CE. Filozof a astronom rabi Abraham ibn Ezra (c. 1140) byla zavedena symetrii kombinační číslo , zatímco uzavřená vzorec byl získán později podle talmudista a matematik Levi ben Gerson (lépe známý jako Gersonides), v roce 1321. aritmetický trojúhelník-a grafický diagram ukazující vztahy mezi binomickými koeficienty - byl představen matematiky v pojednáních z 10. století a nakonec se stal známým jako Pascalův trojúhelník . Později, v roce středověké Anglii , kampanologie poskytnuty příklady toho, co je nyní známý jako Hamiltonian cyklů v některých grafech Cayley na permutací.

Během renesance si kombinatorika spolu se zbytkem matematiky a přírodních věd užívala znovuzrození. Práce Pascala , Newtona , Jacoba Bernoulliho a Eulera se staly základem v rozvíjející se oblasti. V moderní době pomohly práce JJ Sylvestera (konec 19. století) a Percyho MacMahona (počátek 20. století) položit základy enumerativní a algebraické kombinatoriky . Teorie grafů se také těšila explozi zájmu současně, zejména v souvislosti se čtyřbarevným problémem .

Ve druhé polovině 20. století zaznamenala kombinatorika rychlý růst, což vedlo k založení desítek nových časopisů a konferencí v tomto oboru. Částečně byl růst podpořen novými spoji a aplikacemi do jiných oborů, od algebry po pravděpodobnost, od funkční analýzy po teorii čísel atd. Tato spojení snižují hranice mezi kombinatorikou a částmi matematiky a teoretické informatiky, ale na zároveň vedlo k částečné fragmentaci pole.

Přístupy a podpole kombinatoriky

Enumerativní kombinatorika

Enumerativní kombinatorika je nejklasičtější oblastí kombinatoriky a soustředí se na počítání počtu určitých kombinatorických objektů. Ačkoli počítání počtu prvků v sadě je poměrně široký matematický problém , mnoho problémů, které vyvstávají v aplikacích, má relativně jednoduchý kombinatorický popis. Fibonacciho čísla jsou základním příkladem problému v enumerativní kombinatorice. Twelvefold způsob poskytuje jednotný rámec pro počítání permutace , kombinace a oddílů .

Analytická kombinatorika

Analytická kombinatorika se týká výčtu kombinatorických struktur pomocí nástrojů z komplexní analýzy a teorie pravděpodobnosti . Na rozdíl od enumerativní kombinatoriky, která k popisu výsledků používá explicitní kombinatorické vzorce a generující funkce , je cílem analytické kombinatoriky získání asymptotických vzorců .

Teorie dělení

Teorie oddílů studuje různé výčty a asymptotické problémy související s celočíselnými oddíly a úzce souvisí s řadami q , speciálními funkcemi a ortogonálními polynomy . Původně součást teorie čísel a analýzy je nyní považována za součást kombinatoriky nebo nezávislého pole. Zahrnuje bijektivní přístup a různé nástroje do analýzy a teorie analytických čísel a má vazby na statistickou mechaniku .

Teorie grafů

Grafy jsou základními objekty v kombinatorice. Úvahy o teorii grafů sahají od výčtu (např. Počtu grafů na n vrcholech s hranami k ) přes existující struktury (např. Hamiltonovské cykly) až po algebraické reprezentace (např. Vzhledem k grafu G a dvěma číslům x a y , dělá Tutte polynomiální T G ( x , y ) mají kombinatorickou interpretaci?). Ačkoli existují velmi silné vazby mezi teorií grafů a kombinatorikou, někdy jsou považovány za samostatné předměty. Zatímco kombinatorické metody se vztahují na mnoho problémů s teorií grafů, tyto dvě disciplíny se obvykle používají k hledání řešení různých typů problémů.

Teorie designu

Teorie designu je studie kombinatorických návrhů , což jsou sbírky podmnožin s určitými vlastnostmi průniku . Blokové vzory jsou kombinatorické vzory zvláštního typu. Tato oblast je jednou z nejstarších částí kombinatoriky, například v Kirkmanově školní úloze navržené v roce 1850. Řešením této úlohy je speciální případ Steinerova systému , který hraje důležitou roli při klasifikaci konečných jednoduchých skupin . Tato oblast má další vazby na teorii kódování a geometrickou kombinatoriku.

Konečná geometrie

Konečná geometrie je studium geometrických systémů, které mají pouze konečný počet bodů. Struktury analogické ke strukturám nalezeným v spojitých geometriích ( euklidovská rovina , skutečný projektivní prostor atd.), Ale definované kombinatoricky, jsou hlavními studovanými položkami. Tato oblast poskytuje bohatý zdroj příkladů pro teorii designu . To by nemělo být zaměňováno s diskrétní geometrií ( kombinatorická geometrie ).

Teorie objednávek

Hasseův diagram sady sil {x, y, z} seřazený podle zařazení .

Teorie řádu je studium částečně uspořádaných množin , konečných i nekonečných. Různé příklady dílčích řádů se objevují v algebře , geometrii, teorii čísel a v celé kombinatorice a teorii grafů. Pozoruhodné třídy a příklady dílčích objednávek zahrnují mřížky a booleovské algebry .

Teorie matroidů

Teorie matroidů abstrahuje část geometrie . Studuje vlastnosti množin (obvykle konečných množin) vektorů ve vektorovém prostoru , které nezávisí na konkrétních koeficientech ve vztahu lineární závislosti . Teorii matroidů patří nejen struktura, ale také enumerativní vlastnosti. Teorii matroidů představil Hassler Whitney a studoval ji jako součást teorie řádu. Nyní je to samostatný studijní obor s řadou spojení s ostatními částmi kombinatoriky.

Extrémní kombinatorika

Extrémní kombinatorika studuje extrémní otázky na množinových systémech . Typy otázek řešených v tomto případě se týkají největšího možného grafu, který splňuje určité vlastnosti. Například největší graf bez trojúhelníků na 2n vrcholech je kompletní bipartitní graf K n, n . Často je příliš těžké najít extrémní odpověď f ( n ) přesně a dá se uvést pouze asymptotický odhad .

Ramseyova teorie je další součástí extremální kombinatoriky. Uvádí, že každá dostatečně velká konfigurace bude obsahovat určitý druh pořadí. Jedná se o pokročilé zobecnění principu pigeonhole .

Pravděpodobnostní kombinatorika

V pravděpodobnostní kombinatorice jsou otázky následujícího typu: Jaká je pravděpodobnost určité vlastnosti pro náhodný diskrétní objekt, jako je náhodný graf ? Například jaký je průměrný počet trojúhelníků v náhodném grafu? Pravděpodobnostní metody se také používají k určení existence kombinatorických objektů s určitými předepsanými vlastnostmi (pro které může být obtížné najít explicitní příklady), jednoduše pozorováním, že pravděpodobnost náhodného výběru objektu s těmito vlastnostmi je větší než 0. Tento přístup ( často označované jako na pravděpodobnostní metoda ) se ukázal velmi účinný v aplikacích na extremální kombinatorika a teorie grafů. Úzce související oblastí je studium konečných Markovových řetězců , zejména na kombinatorických objektech. Zde se opět používají pravděpodobnostní nástroje k odhadu doby míchání .

Pravděpodobnostní kombinatorika, která byla často spojována s Paulem Erdősem , který na tomto předmětu provedl průkopnickou práci, byla tradičně považována za soubor nástrojů ke studiu problémů v jiných částech kombinatoriky. S růstem aplikací pro analýzu algoritmů v počítačové vědě , ale i s klasickou pravděpodobností, teorií aditivních čísel a pravděpodobnostní teorií čísel se oblast v poslední době stala nezávislým polem kombinatoriky.

Algebraická kombinatorika

Algebraická kombinatorika je oblast matematiky, která využívá metody abstraktní algebry , zejména teorii skupin a teorii reprezentace , v různých kombinatorických kontextech a naopak kombinatorické techniky aplikuje na problémy v algebře . Algebraická kombinatorika neustále rozšiřuje svoji působnost, a to jak v tématech, tak v technikách, a lze ji považovat za oblast matematiky, kde je interakce kombinatorických a algebraických metod obzvláště silná a významná.

Kombinatorika slov

Kombinatorika slov se zabývá formálními jazyky . Vznikl nezávisle v několika oborech matematiky, včetně teorie čísel , teorie grup a pravděpodobnosti . Má aplikace na enumerativní kombinatoriku, fraktální analýzu , teoretickou informatiku , teorii automatů a lingvistiku . I když je mnoho aplikací nových, klasická Chomsky – Schützenbergerova hierarchie tříd formálních gramatik je možná nejznámějším výsledkem v oboru.

Geometrická kombinatorika

Geometrická kombinatorika souvisí s konvexní a diskrétní geometrií , zejména s polyedrickou kombinatorikou . Ptá se například, kolik tváří každé dimenze může mít konvexní polytop . Důležitou roli hrají také metrické vlastnosti polytopů, např. Cauchyova věta o tuhosti konvexních polytopů. Zvažují se také speciální polytopy , například permutohedra , asociatedra a Birkhoffovy polytopy . Kombinatorická geometrie je staromódní název pro diskrétní geometrii.

Topologická kombinatorika

Kombinatorické analogy konceptů a metod v topologii se používají ke studiu zbarvení grafů , spravedlivého dělení , oddílů , částečně uspořádaných množin , rozhodovacích stromů , problémů s náhrdelníky a diskrétní Morseovy teorie . To by nemělo být zaměňováno s kombinatorickou topologií, což je starší název pro algebraickou topologii .

Aritmetická kombinatorika

Aritmetická kombinatorika vznikla z interakce mezi teorií čísel , kombinatorikou, ergodickou teorií a harmonickou analýzou . Jde o kombinatorické odhady spojené s aritmetickými operacemi (sčítání, odčítání, násobení a dělení). Teorie aditivních čísel (někdy také nazývaná aditivní kombinatorika) odkazuje na speciální případ, kdy jsou zahrnuty pouze operace sčítání a odčítání. Jedna důležitá technika v aritmetických kombinatorika je ergodic teorie o dynamických systémů .

Nekonečná kombinatorika

Infinitary kombinatorika, nebo kombinatorická teorie množin, je rozšíření myšlenek v kombinatorice na nekonečné množiny. Je součástí teorie množin , oblasti matematické logiky , ale využívá nástroje a nápady jak z teorie množin, tak z extrémní kombinatoriky.

Gian-Carlo Rota používal název spojitá kombinatorika k popisu geometrické pravděpodobnosti , protože mezi počítáním a mírou existuje mnoho analogií .

Související pole

Kombinatorická optimalizace

Kombinatorická optimalizace je studium optimalizace na diskrétních a kombinatorických objektech. Začalo to jako součást kombinatoriky a teorie grafů, ale nyní se na ni díváme jako na obor aplikované matematiky a informatiky související s operačním výzkumem , teorií algoritmů a teorií výpočetní složitosti .

Teorie kódování

Teorie kódování začala jako součást teorie designu s časnými kombinatorickými konstrukcemi kódů opravujících chyby . Hlavní myšlenkou předmětu je navrhnout efektivní a spolehlivé metody přenosu dat. Nyní je to velký studijní obor, součást teorie informace .

Diskrétní a výpočetní geometrie

Diskrétní geometrie (nazývaná také kombinatorická geometrie) také začala jako součást kombinatoriky, s časnými výsledky na konvexních polytopech a číslech líbání . Se vznikem aplikací diskrétní geometrie na výpočetní geometrii se tato dvě pole částečně spojila a stala se samostatným studijním oborem. Zůstává mnoho spojení s geometrickými a topologickými kombinatoriky, které samy o sobě lze považovat za výrůstky rané diskrétní geometrie.

Kombinatorika a dynamické systémy

Dalším objevujícím se polem jsou kombinatorické aspekty dynamických systémů . Zde lze na kombinatorických objektech definovat dynamické systémy. Viz například dynamický systém grafů .

Kombinatorika a fyzika

Mezi kombinatorikou a fyzikou , zejména statistickou fyzikou, rostou interakce . Mezi příklady patří přesné řešení Isingova modelu a spojení mezi Pottsovým modelem na jedné straně a chromatickým a Tuttovým polynomem na straně druhé.

Viz také

Poznámky

Reference

externí odkazy