Kombinatorika

Z Wikipédie

Kombinatorika (alebo aj kombinatorická matematika čí kombinatorická analýza) je súčasť diskrétnej matematiky, ktorá študuje (spravidla) konečné množiny objektov, ktoré vyhovujú zadaným kritériám a zaoberá sa najmä "počítaním" objektov v týchto množinách (enumeratívna kombinatorika) a rozhodovaním, či isté "optimálne" objekty a množiny objektov vôbec existujú (extremálna kombinatorika). Jedným z najvýznamejších kombinatorikov nedávnej doby bol Gian-Carlo Rota, ktorý pomohol sformalizovať kombinatoriku ako takú začiatkom šesťdesiatych rokov. Produktívny riešiteľ rôznych problémov Paul Erdös pracoval hlavne na extremálnych problémoch.

Typický príklad, na ktorý sa kombinatorika snaží nájsť odpoveď, je takýto: Aký je počet všetkých usporiadaní balíka 52 hracích kariet? Odpoveď je 52! (t.j. "päťdesiatdva faktoriál"), čo je súčin všetkých prirodzených čísel od jedna po 52. Je možno prekvapujúce, že toto číslo, približne 8.065817517094 × 10⁶⁷, je tak veľké. Je to o niečo viac než 8, za ktorou nasleduje 67 núl. Pri porovnaní s inými veľkými číslami je väčšie než druhá mocnina Avogadrovej konštanty (6.022 × 10²³), ktorá vyjadruje počet častíc v jednom mole látky.

[úprava] Definícia

Samotný predmet štúdia kombinatoriky možno vyjadriť na základe pojmu konfigurácie (pozri napr. I. Haverlík: Matematická informatika I):

Nech A a B sú dve konečné množiny. Ľubovoľné zobrazenie množiny A do množiny B, vyhovujúce určitým podmienkam, ktorý charakter dopredu nie je určený (v tejto definícii), sa nazýva konfigurácia.

Kombinatorika skúma otázky existencie, vytvárania a vyčíslenia (t.j. určenia počtu) konfigurácií, pričom sa často vyčísľujú nie samotné konfigurácie, ale iba im zodpovedajúce triedy ekvivalencie.

Príkladom konfigurácií sú variácie, kombinácie či permutácie.

[úprava] Vyčísľovanie konfigurácií

Vyjadrenie počtu všetkých konfigurácií sa dá považovať za centrálnu otázku kombinatoriky. Nech S je množina o n prvkoch. kombinácie (bez opakovania) k prvkov z množiny S sú podmožiny S majúce k prvkov (v reči konfiguácií sú to všetky zobrazenia f z množiny $\{1,2,\ldots,k\}$ do množiny S také, že $f (i) < f (j)$ pre $i < j$ ). Variácie k prvkov z tejto množiny S sú postupnosti k rôznych prvkov z S. Všimnite si, že pri variáciach zaleží na poradí, kým kombinácie, ktoré sa odlišujú len poradím prvkov, považujeme za totožné. Vzorce udávajúce počet variácií a kombinácií k prvkov (hovoríme o variáciach, resp. kombinácia k-tej triedy) sú známe a veľmi často používané.

Všeobecnejšie, nech je daná nekonečná trieda konečných mnoýín (S_i), typicky indexovaná prirodzenými číslami, enumeratívna kombinatorika hľadá rôzne spôsoby vyjadrenia vyčísľovacej funkcie, f(n), ktorá udáva ("vyčísľuje") počet prvkov v množine S_n pre každé n. V príkladoch v predchádzajúcom odstavci obsahovala množina S_n všetky kombinácie, resp. variácie n-tej triedy z množiny S.

Najjednoduchší spôsob vyjadrenia sú uzavreté tvary, t.j. konečná kompozícia elementárnych funkcií (v kombinatorike považujeme aj funkciu faktoriál za elementárnu). Ako už bolo spomenuté v úvode, počet všetkých rôznych usporiadaní n hracích kariet je presne n!.

Avšak nie vždy je vhodné a praktické udávať vyčísľovaciu funkciu explicitným uzavretým tvarom (dokonca v niektorých prípadoch je to nemožné). Napríklad, nech f(n) označuje počet všetkých rôznych podmnožín celých čísel z intervalu <1,n>, ktoré neobsahujú dve po sebe idúce čísla; napríklad pre n=4 by sme mali {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, teda f(4)=8. Ukazuje sa, že f(n) je (n+2). Fibonacciho číslo, čo sa dá v uzavretom tvare vyjadriť ako

$f(n) = \frac{\phi^{n+2}}{\sqrt{5}} - \frac{(1-\phi)^{n+2}}{\sqrt{5}}$

kde φ = (1 + √5) / 2 je tzv. zlatý priemer. Avšak samotný fakt, že počítame množiny celých čísel, a vo výsledku nám vystupuje √5, je pri najmenšom neestetický z kombinatorického hľadiska. Navyše nie je celkom jasný súvis výsledku s problémom, dokonca ani na prvý pohľad nie je vidno, či oborom hodnôt tejto funkcie sú prirodzené čísla. Alternatívne môže byť funkcia f vyjadrená v rekurentnom tvare:

f (n) = f (n - 1) + f (n - 2)

f(0)=1, f(1)=2

čo vyzerá oveľa uspokojivešje (minimálne z kombinatorického pohľadu), keďže presne hovorí, prečo je výsledok taký aký je.

Iný prístup je nájsť tzv. asymptotickú formulu:

f(n) ~ g(n)

kde g je "známa" funkcia a f(n) sa blíži ku g(n) ako sa n blíži do nekonečna. V niektorých prípadoch je jednoduchá asymptotická funkcia preferovanejšia pred veľmi zložitým uvazretým vzorcom, ktorý neposkytuje žiadny náhľad na správanie počítaných objektov. Ak budeme pokračovať v našom príklade, tak asymptotická formula by bola

$f(n) \sim \frac{\phi^{n+2}}{\sqrt{5}}$

pre n rastúca do nekonečna.

Azda najužitočnejšie vyjadrenie je však prostredníctvom formálneho mocninového radu, nazývaného generujúca funkcia (alebo vytvárajúca funkcia), ktorá je najčastejšie buď tzv. obyčajná generujúca funkcia

$\sum f(n) x^n$

alebo exponenciálna generujúca funkcia

$\sum f(n) \frac{x^n}{n!}$

kde sumy idú cez n ≥ 0. Hneď ako určíme generujúcu funkciu, dovolíme nám vyjadriť všetky informácie, ktoré nám poskytli predchádzajúce prístupy. Naviac rôzne prirodzené operácie na generujúcich funkciách ako napr. sčítanie, násobenie, derivácia a pod. majú kombinatorický význam, čo dovoľuje preniesť výsledky z jedného kombinatorického problému na iný.

[úprava] Výsledky

Dajú sa zostrojiť niektoré veľmi rafinované konfigurácie a dokázať niektoré veľmi prekvapujúce tvrdenia. Jedným z takých príkladov pochádza od Franka Ramseyho:

Predpokladajme, že na oslave sa stretne šesť ľudí. Každý pár buď nazvájom pozná alebo nie. V každom prípade sa však vždy dajú nájsť traja ľudia, ktorí sa buď poznajú navzájom alebo sú si úplne neznámi.

Dôkaz je krátky a vedie sa sporom: predpokladajme, že takí traja ľudia neexistujú (teda takí, ktorí buď všetci nazvájom poznajú alebo nepoznajú). Uvažujeme teraz ľubovoľnú osobu na oslave, nazvime ju A: spomedzi zvyšných piatich ľudí musia byť aspoň traja, ktorí ju buď poznajú, alebo traja, ktorí ju nepoznajú (tento fakt vyplýva z Dirichletovho princípu). Bez ujmy na všeobecnosti, predpokladajme, že títo traja ľudia osobu A poznajú. Potom ale medzi týmito troma ľuďmi sú najmenej dvaja, ktorí sa poznajú (inak by sme mali troch ľudí, ktorí sa navzájom nepoznajú, čo by bol spor). Keďže však títo dvaja ľudia sa poznajú aj s A, máme troch ľudí, ktorí sa nazvájom poznajú, čo je spor. (Toto je špeciálny prípad Ramseyho vety.

Iný dôkaz používa dvojité vyčíslenie: spočítajte všetky usporiadané trojice ľudí (A,B,C), kde osoba B pozná osobu A, ale nepozná osobu C. Predpokladajme, že osoba K pozná k z piatich ostatných. Potom vystupuje ako druhá zložka (B) v presne k(5-k) takýchto trojíc, pretože človek v prvej zložke (A) musí byť jeden spomedzi k ľudí, ktorých pozná a človek v tretej zložke (C) musí byť jeden zo zvyšných 5-k ľudí, ktorých nepozná. Z toho vyplýva, že vystupuje v druhom komponente v buď 0*5=0, 1*4=4 alebo 2*3=6 takýchto trojiciach. Keďže spolu máme 6 ľudí a každý môže byť na druhom mieste v najviach šiestich trojiciach, spolu máme najviac 36 trojíc.

Teraz uvažujme trojicu ľudí, kde presne jeden pár sa nazvájom pozná. Je zrejmé, že ich môžeme vyjadriť ako našu trojicu (A,B,C) presne dvomi spôsobmi: nech C' je ten, ktorý je neznámy pre zvyšných dvoch a potom sa prvom a druhom mieste môžu vystriedať títo dvaja dvomi spôsobmi. Podobne, keď sa presne dva páry navzájom poznajú, potom sa dajú vyjadriť ako trojica tiež dvoma spôsobmi: nech A je osoba, ktorá pozná obidvoch zo zvyšných a B a C (v nejakom poradí) sú títo zvyšní dvaja. To znamená, že existuje najviach 36/2=18 trojíc, v ktorých buď presne jeden alebo dva páry sa poznajú nazvájom. Keďže je však len 20 trojích, existujú nejmenej dve trojice, ktoré sa buď poznajú navzájom alebo sú si neznámi.

Myšlienka hľadania usporiadania v náhodných konfiguráciách je základom Ramseyho teórie. Vo svojej podstate táto teórie hovorí, že ľubovoľná dostatočne veľká konfigurácia obsahuje najmenej jednu inštanciu nejakého iného typu konfigurácie.

[úprava] Pozrite tiež

Generujúca funkcia
Kombinatorické princípy
Metóda trajektórií
Princíp inklúzie a exklúzie

[úprava] Literatúra

Handbook of Combinatorics, Volumes 1 and 2, R.L. Graham, M. Groetschel and L. Lovász (Eds.), MIT Press, 1996. ISBN 026207169X
Enumerative Combinatorics, Volumes 1 and 2, Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1N
Haverlík, I. a kol.: Matematická informatika I. Bratislava, 1984, skriptum Matematicko-fyzikálnej fakulty Univerzity Komenského v Bratislave.
The solution of a combinatorial problem

Zdroj: "http://sk.wikipedia.org../../../k/o/m/Kombinatorika.html"

Kategórie: Kombinatorika | Diskrétna matematika