Kombinatorika

Kombinatorika  (někdy nazývaná kombinatorická analýza ) je odvětví matematiky věnované řešení problémů souvisejících s výběrem a uspořádáním prvků nějaké (nejčastěji konečné) množiny podle daných pravidel. Každé takové pravidlo definuje určitý výběr z prvků původní sady, který se nazývá kombinatorická konfigurace . Nejjednoduššími příklady kombinatorických konfigurací [1] [2] jsou permutace , kombinace a umístění .

Typické problémy [1] kombinatoriky :

  1. Určete počet kombinatorických konfigurací odpovídajících daným pravidlům (zejména dokažte nebo vyvrátte jejich existenci).
  2. Najděte prakticky vhodný algoritmus pro jejich kompletní konstrukci.
  3. Určete vlastnosti dané třídy kombinatorických konfigurací.

Kombinatorika úzce souvisí s mnoha dalšími oblastmi matematiky - algebra , geometrie , teorie pravděpodobnosti , teorie čísel a další . Používá se v široké škále oblastí znalostí (například v genetice , informatice , statistice , statistické fyzice , lingvistice ).

Termín „kombinatorika“ zavedl do matematického použití Leibniz , který v roce 1666 publikoval svou práci „Discourses on Combinatorial Art“.

Příklady kombinatorických konfigurací a problémů

K formulaci a řešení kombinatorických problémů se používají různé modely kombinatorických konfigurací . Příklady kombinatorických konfigurací jsou:

Příklady kombinatorických problémů:

  1. Kolika způsoby je možné umístit n objektů do m polí, aby byla splněna daná omezení?
  2. Kolik funkcí je od m -prvkové množiny po n - prvkovou množinu , které splňují daná omezení?
  3. Kolik různých permutací 52 hracích karet existuje? Odpověď: 52! (52 faktoriál ), tj. 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000
nebo o
  2. Ve hře v kostky se hází dvěma kostkami a házené body se sečtou; kolik je kombinací, ve kterých je součet bodů na horních stranách roven dvanácti? Řešení: Každý možný výsledek odpovídá funkci (argumentem funkce je číslo kosti, hodnotou jsou body na horní straně). Je zřejmé, že pouze 6 + 6 nám dává požadovaný výsledek 12. Existuje tedy pouze jedna kombinace, ve které je součet bodů na horních plochách dvanáct.

Historie

Starověk a středověk

Základní kombinatorické koncepty a výpočetní výsledky se objevily ve starověku . Klasický úkol kombinatoriky: „kolik způsobů je možné extrahovat m prvků z N “ je zmíněn v sútrách starověké Indie (počínaje kolem 4. století př. n. l.) [3] . Indičtí matematici byli zřejmě první, kdo objevil binomické koeficienty a jejich souvislost s Newtonovým binomem [3] . Ve II století před naším letopočtem. E. Indové věděli, že součet všech binomických koeficientů stupně n je .

Kombinatorické motivy lze vidět v symbolice čínské „ Knihy proměn “ (5. století př. n. l.). Podle jejích autorů je vše na světě kombinováno z různých kombinací mužských a ženských principů a také osmi živlů: země, hory, voda, vítr, bouřka, oheň, mraky a nebe [4] . Historici také zaznamenali kombinatorické problémy v příručkách pro hraní Go a dalších her. Velký zájem matematiků v mnoha zemích od starověku neustále probouzel magické čtverce .

Staří Řekové také uvažovali o samostatných kombinatorických problémech, ačkoli jejich systematická prezentace těchto problémů, pokud existovala, se k nám nedostala. Chrysippus ( III. století př. n. l. ) a Hipparchos ( II. století př. n. l. ) vypočítali, kolik důsledků lze získat z 10 axiomů ; neznáme metodu počítání, ale Chrysippus dostal více než milion a Hipparchos - více než 100 000 [5] . Aristoteles při prezentaci své logiky neomylně vyjmenoval všechny možné typy tříčlenných sylogismů . Aristoxenus zvažoval různé střídání dlouhých a krátkých slabik v metrech . [5] Pythagorejci pravděpodobně používali při konstrukci své teorie čísel a numerologie některá kombinatorická pravidla ( dokonalá čísla , obrazná čísla , pythagorejské trojice atd.).

Ve středověku se kombinatorika dále rozvíjela, a to především mimo evropskou civilizaci . Ve 12. století indický matematik Bhaskara ve svém hlavním díle Lilavati podrobně studoval problémy související s permutacemi a kombinacemi, včetně permutací s opakováním. Další indický matematik, Mahavira (polovina 9. století), publikoval vzorce pro počet permutací a kombinací , a tyto vzorce mohly být indickým matematikům známé již v 6. století našeho letopočtu. E. Filosof a astronom Rabbi Abraham ibn Ezra (kolem roku 1140) spočítal počet umístění s permutacemi v samohláskách jména Božího [6] . On také založil symetrii binomických koeficientů . Přesný vzorec pro ně později zveřejnil talmudista a matematik Levi ben Gershom (známější jako Gersonides) v roce 1321.

Několik kombinatorických problémů je obsaženo v knize Abacus ( Fibonacci , 13. století). Dal si například za úkol najít nejmenší počet závaží, který by stačil k navážení jakéhokoli produktu o hmotnosti od 1 do 40 liber.

Nový čas

Blaise Pascal udělal spoustu práce na binomických koeficientech a objevil jednoduchý způsob, jak je vypočítat: " Pascalův trojúhelník ". Později se ukázalo, že tato metoda byla známa již na východě (asi od 10. století) a nazývala se aritmetický trojúhelník . Pascal na rozdíl od svých předchůdců striktně uváděl a prokázal vlastnosti tohoto trojúhelníku. Aritmetický trojúhelník je grafický diagram ukazující vztahy mezi binomickými koeficienty. Později, ve středověké Anglii, Campanology poskytla příklady toho, co je nyní známé jako Hamiltonovské cykly v permutovaných Cayleyových grafech .

V renesanci se spolu s dalšími vědami začala rychle rozvíjet kombinatorika. Gerolamo Cardano napsal zasvěcenou matematickou studii hry v kostky , která byla vydána posmrtně. Teorií této hry se zabývali také Niccolo Tartaglia a Galileo Galilei . Historie teorie pravděpodobnosti začala korespondencí zaníceného hráče Chevaliera de Meret s Pierrem Fermatem a Blaise Pascalem , kde bylo vzneseno několik jemných kombinatorických otázek. Kromě hazardních her se v kryptografii používaly (a nadále používají) kombinatorické metody  , a to jak k vývoji šifer, tak k jejich prolamování.

Termín „kombinatorika“ vytvořil Leibniz , který je považován za zakladatele moderní kombinatoriky. V roce 1666 (tehdy mu bylo 20 let) vydal knihu Rozpravy o kombinatorickém umění. Pravda, Leibniz chápal termín „kombinatorika“ příliš široce, včetně veškeré konečné matematiky a dokonce i logiky [7] . Leibnizův žák Jacob Bernoulli , jeden ze zakladatelů teorie pravděpodobnosti, představil ve své knize The Art of Conjectures (1713) množství informací o kombinatorice.

Ve stejném období se formovala terminologie nové vědy. Termín " kombinace " ( kombinace ) se poprvé vyskytuje v Pascalu (1653, publikováno v roce 1665). Termín " permutace " ( permutace ) byl použit ve specifikované knize Jacoba Bernoulliho (ačkoli se s ním už dříve občas setkal). Bernoulli také používal termín “ uspořádání ” .

Po příchodu matematické analýzy byla nalezena úzká souvislost mezi kombinatorickými a řadou analytických problémů. Abraham de Moivre a James Stirling našli vzorce pro aproximaci faktoriálu [8] .

Konečně, kombinatorika jako nezávislé odvětví matematiky se formovalo v dílech Eulera . Podrobně se zabýval například těmito problémy:

Kromě permutací a kombinací Euler studoval oddíly , stejně jako kombinace a umístění s podmínkami.

Aktuální stav

Práce Pascala , Newtona , Jacoba Bernoulliho a Eulera se stala zásadní pro rozvoj tohoto oboru. V moderní době pomohla práce J. J. Sylvestra (konec 19. století) a Percyho McMahona (začátek 20. století) položit základy výčtové a algebraické kombinatoriky . Tam byl také rostoucí zájem o teorii grafů , obzvláště v souvislosti s čtyři-teorém barvy a problémy v ekonomii.

Ve druhé polovině 20. století zažila kombinatorika nový explozivní růst, který souvisel s rychlým rozvojem diskrétní matematiky, informatiky, kybernetiky a designu experimentů . Částečně byl tento růst stimulován objevenými souvislostmi a aplikacemi v jiných oblastech matematiky - v algebře, teorii pravděpodobnosti, funkcionální analýze , teorii čísel atd. Tyto souvislosti stírají hranice mezi kombinatorikou a jinými oblastmi matematiky, ale zároveň čas vést k určité fragmentaci kombinatoriky.

Na počátku 20. století začal vývoj kombinatorické geometrie : byly dokázány Radonovy , Hellyho , Youngovy , Blaschkeovy věty a důsledně dokázána i izoperimetrická věta . Borsuk- Ulamova a Lyusternik-Shnirelmanova věta byla prokázána na průsečíku topologie, analýzy a kombinatoriky . Ve druhé čtvrtině 20. století vznikl Borsuk problém a Nelson-Erdős-Hadwiger problém . Ve čtyřicátých letech se zformovala Ramseyho teorie . Za otce moderní kombinatoriky je považován Pal Erdős , který do kombinatoriky zavedl pravděpodobnostní analýzu. Od druhé poloviny 20. století, kdy se objevily počítače , výrazně vzrostla pozornost konečné matematice a zejména kombinatorice . Nyní je to extrémně bohatá a rychle se rozvíjející oblast matematiky.

Metody a sekce kombinatoriky

Enumerativní kombinatorika

Enumerativní kombinatorika (nebo enumerativní kombinatorika ) uvažuje o problému výčtu nebo počítání počtu různých konfigurací (například permutací ) tvořených prvky konečných množin, na které mohou být uvalena určitá omezení, jako: rozlišitelnost nebo nerozlišitelnost prvků, možnost opakování stejných prvků atd.

Počet konfigurací vytvořených několika manipulacemi na množině se počítá podle pravidel sčítání a násobení .

Fibonacciho čísla jsou typickým příkladem problému v enumerativní kombinatorice, stejně jako známý Letter Problem . Duodecimální cesta poskytuje jednotnou strukturu pro počítání permutací , kombinací a rozdělení .

Analytická kombinatorika

Analytická kombinatorika se odkazuje na výčet 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í sekvenční funkce , analytická kombinatorika si klade za cíl odvodit asymptotické vzorce .

Teorie dělení

Teorie rozdělení studuje různé enumerativní a asymptotické problémy související s rozdělováním přirozených čísel a je úzce spjata s q-sériemi , speciálními funkcemi a ortogonálními polynomy . Původně byla součástí teorie čísel a analýzy a nyní je považována za součást kombinatoriky nebo nezávislého oboru. Zahrnuje bijektivní přístup , různé nástroje analýzy a analytické teorie čísel a má také spojení se statistickou mechanikou .

Teorie grafů

Grafy jsou základními objekty kombinatoriky. Teorie grafů uvažuje výčty (například počet n vrcholů s k hranami grafu), existující struktury (například Hamiltonovské cykly), algebraické reprezentace (například vezměte graf G a dvě čísla x a y , Tattův polynom T G (x, y ) kombinatorické zobrazení?). Přestože mezi teorií grafů a kombinatorikou existují velmi silné vazby, někdy se s nimi zachází jako se samostatnými předměty. Zatímco kombinatorické metody jsou použitelné na mnoho problémů v teorii grafů, tyto dvě disciplíny se běžně používají k nalezení řešení různých typů problémů.

Teorie schémat

Teorie schémat je studie o kombinatorických schématech , což jsou soubory podmnožin s jistými průsečíkovými vlastnostmi . Bloková schémata  jsou kombinatorická schémata speciálního typu. Tato oblast je jednou z nejstarších částí kombinatoriky, jako je Kirkmanův problém školačky navržený v roce 1850 . Řešením problému je speciální případ Steinerova systému, jehož systémy hrají důležitou roli při klasifikaci jednoduchých konečných grup . Tato oblast má další souvislosti s teorií kódování a geometrickou kombinatorikou.

Konečná geometrie

Konečná geometrie je studium geometrických systémů , které mají pouze konečný počet bodů. Struktury jsou podobné těm, které se nacházejí v spojité geometrii ( euklidovská rovina , skutečný projektivní prostor atd.), ale hlavní studované prvky jsou definovány kombinatoricky. Tato oblast poskytuje bohatý zdroj příkladů pro teorii obvodů . Nemělo by se zaměňovat s diskrétní geometrií ( kombinatorická geometrie ).

Teorie řádu

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

Teorie matroidů

Matroid teorie 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 lineárně závislým způsobem. Nejen struktura, ale i výčetní vlastnosti patří do teorie matroidů. Teorii matroidů představil Hassler Whitney a studoval ji jako součást teorie řádu. V současnosti se jedná o samostatnou oblast výzkumu, která má řadu návazností na další úseky kombinatoriky.

Extrémní kombinatorika

Extrémní kombinatorika studuje extremální otázky o soustavách množin . Typy otázek zvažovaných v tomto případě odkazují na největší možný graf, který splňuje určité vlastnosti. Například největší graf bez trojúhelníků na 2n vrcholech je úplný bipartitní graf K n, n . Často je příliš obtížné najít extrémní odpověď f(n) dokonce i přesně a lze dát pouze asymptotický odhad .

Ramseyho teorie

Ramseyho teorie  je další součástí extremální kombinatoriky. Tvrdí, že každá dostatečně velká konfigurace bude obsahovat určitý řád a studuje přítomnost pravidelných struktur v náhodných konfiguracích prvků. Toto je rozšířené zobecnění Dirichletova principu („princip holubů a krabic“). Příklad výroku z Ramseyho teorie je následující:

ve skupině 6 lidí se vždy najdou tři lidé, kteří se buď znají ve dvojici, nebo se ve dvojici neznají.

Pokud jde o strukturální kombinatoriku, stejné tvrzení je formulováno takto:

v každém grafu se 6 vrcholy je buď klika , nebo nezávislá množina velikosti 3.

Pravděpodobnostní kombinatorika

Tato část odpovídá na otázky jako: Jaká je pravděpodobnost, že určitá vlastnost je přítomna pro náhodný diskrétní objekt, jako je náhodný graf ? Jaký je například 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 daný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 pravděpodobnostní metoda ) se ukázal jako vysoce účinný v aplikacích extremální kombinatoriky a teorie grafů. Úzce příbuznou oblastí je studium konečných Markovových řetězců , zejména na kombinatorických objektech. K odhadu doby míchání se opět používají pravděpodobnostní nástroje .

Pravděpodobnostní kombinatorika, často spojovaná s Palem Erdősem , který na tomto tématu odvedl průkopnickou práci, byla tradičně považována za soubor nástrojů pro studium problémů v jiných částech kombinatoriky. Nicméně, s růstem aplikací pro analýzu algoritmů ve vědě o počítačích , stejně jako klasická teorie pravděpodobnosti, aditivní teorie čísel a pravděpodobnostní teorie čísel , pole nedávno rostlo se stát polem kombinatoriky v jeho vlastní pravý.

Algebraická kombinatorika

Algebraická kombinatorika je odvětví matematiky , které využívá metody abstraktní algebry , zejména teorie grup a teorie reprezentace , v různých kombinatorických kontextech a naopak aplikuje kombinatorické metody na problémy v algebře . Algebraická kombinatorika neustále rozšiřuje svůj záběr jak v tematických směrech, tak v metodách a lze ji považovat za oblast matematiky, kde je interakce kombinatorických a algebraických metod zvláště silná a významná.

Kombinatorika slov

Kombinatorika slov se zabývá formálními jazyky . Vzniklo nezávisle v několika oblastech matematiky, včetně teorie čísel , teorie grup a teorie pravděpodobnosti . Má aplikace v enumerativní kombinatorice, fraktální analýze , teoretické informatice , teorii automatů a lingvistice. Ačkoli je mnoho aplikací nových, klasická hierarchie tříd Chomsky formálních gramatik je možná nejznámějším výsledkem v oboru.

Kombinatorická geometrie

Geometrická kombinatorika je příbuzná konvexní a diskrétní geometrii , zejména kombinatorice mnohostěnů . Například se zeptá, kolik ploch každé dimenze může mít konvexní mnohostěn . Důležitou roli hrají i metrické vlastnosti mnohostěnů, např. Cauchyho věta o tuhosti konvexních mnohostěnů. Zvažují se také speciální mnohostěny, jako jsou permutační mnohostěny , asociační stěny a Birkhoffovy mnohostěny . Kombinatorická geometrie  je staromódní název pro diskrétní geometrii.

Topologická kombinatorika

Topologická kombinatorika aplikuje myšlenky a metody kombinatoriky v topologii , při studiu zbarvení grafu , spravedlivého dělení , dělení , rozhodovacích stromů , částečně uspořádaných množin , problémů s náhrdelníkem 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 se vynořila ze vzájemného ovlivňování mezi teorií čísel , kombinatorikou, ergodickou teorií a harmonickou analýzou . Jedná se o kombinatorická hodnocení spojená s aritmetickými operacemi (sčítání, odčítání, násobení a dělení). Aditivní teorie čísel (někdy také nazývaná aditivní kombinatorika) označuje speciální případ, kdy se jedná pouze o sčítání a odčítání. Jednou z důležitých metod aritmetické kombinatoriky je ergodická teorie dynamických systémů .

Nekonečná kombinatorika

Nekonečná kombinatorika  - aplikace myšlenek a metod kombinatoriky na nekonečné (včetně nespočitatelných ) množin. Je součástí teorie množin , oboru matematické logiky , ale využívá nástroje a myšlenky jak teorie množin, tak extremální kombinatoriky.

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

Související oblasti

Kombinatorická optimalizace

Kombinatorická optimalizace  je studium optimalizace diskrétních a kombinatorických objektů. Začalo to jako součást kombinatoriky a teorie grafů, ale nyní je vnímáno jako odvětví 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 obvodů s ranými kombinatorickými konstrukcemi kódů opravujících chyby . Hlavní myšlenkou předmětu je vyvinout efektivní a spolehlivé metody přenosu dat. Nyní je to velká oblast výzkumu, součást teorie informace .

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

Diskrétní geometrie (také nazývaná kombinatorická geometrie) také začala jako součást kombinatoriky, s časnými výsledky na konvexních mnohostěnech a kontaktních číslech . S příchodem aplikací diskrétní geometrie ve výpočetní geometrii se tyto dva obory částečně sloučily a staly se samostatným studijním oborem. Přetrvává mnoho souvislostí s geometrickou a topologickou kombinatorikou, která sama o sobě může být považována za výtvory rané diskrétní geometrie.

Kombinatorika a dynamické systémy

 Další nově vznikající oblastí jsou kombinatorické aspekty dynamických systémů . Zde mohou být dynamické systémy definovány kombinatorickými objekty. Viz například dynamický grafový systém .

Kombinatorika a fyzika

Existuje rostoucí vztah mezi kombinatorikou a fyzikou , zejména statistickou fyzikou . Příklady zahrnují přesné řešení Isingova modelu a spojení Pottsova modelu na jedné straně a chromatických polynomů a Tattetových polynomů na straně druhé.

Otevřené problémy

Kombinatorika (zejména Ramseyova teorie) obsahuje mnoho dobře známých otevřených problémů , někdy s velmi jednoduchou formulací. Například není známo, jaké minimum v kterékoli skupině lidí bude 5 lidí, buď párově známých mezi sebou, nebo párů neznámých (i když je známo, že stačí 49 lidí) [9] .

Existují také další nevyřešené problémy a neprokázané hypotézy:

Kombinatorika v lingvistice

Kombinatorika (lingvistika) je vlastnost jazykových jednotek a jim odpovídajících jednotek řeči vstupovat do syntagmatických vztahů, tedy do vztahů kompatibility.

Poznámky

  1. ↑ 1 2 Sachkov V. N. Kombinatorická analýza // Mathematical Encyclopedia (v 5 svazcích). - M .: Sovětská encyklopedie , 1979. - T. 2. - S. 974-979. — 1104 s.
  2. ↑ BRE .
  3. ↑ 1 2 Amulya Kumar Bag . Binomická věta ve starověké Indii. Archivováno 3. srpna 2021 na Wayback Machine Indian J. History Sci., 1:68-74, 1966.
  4. ↑ Vilenkin N. Ya., 1975 , s. 7.
  5. ↑ 1 2 Vilenkin N. Ya., 1975 , str. 9.
  6. ↑ Stručný komentář k Exodus 3:13.
  7. ↑ Vilenkin N. Ya., 1975 , s. 19.
  8. ↑ O'Connor, John; Edmund Robertson. Abraham de Moivre . Archiv historie MacTutora matematiky . Datum přístupu: 31. května 2010. Archivováno z originálu 27. dubna 2012.
  9. ↑ Weisstein, Eric W. Ramsey čísla  (anglicky) na webu Wolfram MathWorld .
  10. ↑ ADAMARSKÉ MATICE . Archivováno z originálu 21. ledna 2022.
  11. ↑ Norek X. Trvalky .. - Svět. - 1982. - 211 s.
  12. ↑ Rybnikov, 1972 , s. 96.
  13. ↑ Rybnikov, 1972 , s. 110.
  14. ↑ Kapitonova Yu. V., Krivoy S. L., Letichevsky A. A. Přednášky o diskrétní matematice. - Petrohrad. : BHV-Petersburg, 2004. - S. 530. - 624 s. — ISBN 5-94157-546-7 .

Literatura

Odkazy

  Přejděte na položku Wikidata  Slovníky a encyklopedie
 Odvětví matematiky
Portál "Věda"
Základy matematiky teorie množin matematická logika algebra logiky
Teorie čísel ( aritmetika )
  • Portál "Matematika"
  • Kategorie "Matematika"