Co je kombinatorika a čím se zabývá

Kombinatorika je matematická disciplína zabývající se uspořádáním množin logických prvků.

Základní pojmy

• Kauzalita, počet možných n a výběr z počtu možných k.
• Uspořádání prvků do k-tic a n-tic.
• Vazby mezi prvky a pořadí prvků.
• Kombinační, variační a permutační princip.
• Kombinace, variace, permutace, faktoriál a partition.
• Enumerační vzorce a výpočty.
• Unikátní hodnoty (UV) k-tic a n-tic.
• Grafické reprezentace a tabulky.
• Pascalův trojúhelník.

Počet možných, výběr a kauzalita

Počet možných n je číslo z oboru celých kladných čísel (N), které reprezentuje počet všech prvků. Konkrétně prvků, které jsou stejné, ale netotožné. Obecně jde o stejné jednicové prvky bez odlišení. Z těchto možných můžeme vybrat pouze 0, … až maximálně n prvků. Toto pravidlo nazveme kauzálním předpokladem.

Kauzalita

Kauzálním předpokladem je skutečnost, kterou lze dokázat například schematicky. Všechny pojmy uváděné s opakováním (kombinace, variace a permutace) jsou nekauzální, přes to mají kauzalitu podobně jako pojmy bez opakování. O takové kauzalitě budeme hovořit jako o nepřímé.

Problém výrazů n^k

Je logické, že nemůžeme vybrat více, nežli n, ať už vybíráme jakýmkoliv způsobem. Počet možných je skalár. Na to klademe důraz. Množiny prvků s opakováním jsou nekauzální, protože uvádějí podmnožiny jako prvky.

Důsledkem je k > n, což nelze kauzálně dokázat. Příčina tkví v tom, že pojmy s opakováním vznikly ze vzorce, který maximálně zjednodušuje zápis (syntaxi) funkce. Z tohoto zjednodušeného zápisu byla vytvořena definice.

Příklady nepřímé kauzality pro n^k

binární množina například 8 mincí 2⁸ :

heximální množina 3 hrací kostky 6³ :

Poznámka : Máme – li například n = 2 prvky, nemůžeme vybrat více nežli tyto dva prvky. Ve skutečnosti máme opravdu 8 prvků, které jsou ale binární, tedy p^1,0, které mohou mít pouze jediný stav ve stejném okamžiku – buď jednička, nebo nula, ale nikdy ne současně.

Jiný příklad se třemi hracími kostkami. Hrací kostka má 6 stěn označených puntíky (značky). Značky můžeme zapsat jinak – místo puntíků například čísla 1 až 6. Za prvky můžeme považovat i jednotlivé puntíky, kterých je celkem 21 (1+2+3+4+5+6) na každé kostce.

Zde je bezesporný pouze výběr k = 3 značky. To, že všechny kostky mají stejné značení stran neznamená, že budeme jednotlivé kostky považovat za prvky n, protože to jsou ve skutečnosti podmnožiny n. Totéž platí o jednotlivých puntících 3*21 = 63. Proto n = 3, nebo 63 je špatně.

Při hře lze dosáhnout náhodně některou trojici jedniček, nebo dvojek, … až šestek. Při tom jde o prvky nikoliv s opakováním, ale o stejně značené prvky různých kostek (podmnožin, které můžeme odlišit například barvou).

Správně je součet prvků n = 18 (3*6), tedy stejně jako součet stěn ze všech krychlí.

Pro nekauzální množiny platí, že jednotlivé podmnožiny, respektive prvky, jsou navzájem vyloučené jako jev pravděpodobnosti zevnitř (kombinace 1. třídy). Když si uvědomíme, že vzorec kombinací je v rámci Pascalova trojúhelníku často nahrazován „koeficientem“, dostaneme právě výraz s opakováním. Důležité je vědět, že počet je správně, jenom se prvky neopakují – kauzálně se opakovat nemohou, musí být unikátní.

Poznámka : Proč se ujaly pojmy s opakováním je docela hádankou. Beze sporu jsou dnes binární množiny nejfrekventovanějším pojmem kombinatoriky vůbec a označit je za nekauzální se určitě nebude líbit zejména v rámci informatiky. Stačí se podívat na Pascalův trojúhelník a zjistíme, že 2ⁿ reprezentuje součet kombinací všech tříd stejného základu n. Množiny s opakováním mají svou kauzální podstatu v kombinacích, což si ukážeme na výpočtech za pomoci rozšířeného hypergeometrického rozdělení jevu pravděpodobnosti.

Ke kauzalitě binárních množin se můžeme dopracovat mimo jiné tak, že označíme takové množiny za množiny binárních prvků (nikoliv tedy za binární množiny). Jedná se o tabulkovou reprezentaci pozičního zápisu, kde lze znázornit souvislost s Pascalovým Trojúhelníkem (PT).

Když jsem pátral po důvodech proč teorie lpí na takto chybně definovaném základu dopracoval jsem se k tomu, že se pojem s opakováním uplatňuje v popisech polynomů. Uvedeme si notoricky známý binomický rozklad (a ± b)². Zápis se doporučuje zapisovat například pro (a+b)² takto : aa+ab+ab+bb, kde jsou členy aa, bb, uváděny jako variace s opakováním. Nevím zda kvůli takové potřebě vznikla nutnost definovat pojmy s opakováním, nebo se dodatečně našlo zdůvodnění pro jejich existenci. To je chyba. Kombinatorická uspořádání nepojednávají o velikosti značek (čísel oboru N).

Tady se dostáváme k teoretickému problému zavedení pravidla součtu a součinu do základní kombinatoriky. V tomto smyslu si musíme udělat správnou představu. Součty jsou dány sice vzorci, ale sčítají se jen logické prvky, které současně můžeme vyhodnocovat součinem. Základem pro kombinatoriku je jednoduchá aritmetika. Toto se opírá o názor plynoucí z grafické reprezentace. Uvedeme si příklad na kombinacích 3. třídy z celku 4, tedy C(3,4) :

Přestože uspořádání popisujeme vzorci, které vydávají typické počty, nelze opačně ze vzorců odvozovat uspořádání kombinatorických množin protože : Například při statistickém vyšetřování může mít nález pouze 4 různé trojice, což by znamenalo že C(k,n) = C(3,4), ale může to být pouze část různých trojic mnohem většího n. Nedostatečným příznakem je i skutečnost, že počet různých prvků = 4. Může jít o množinu variací V(3,4), která má 3! krát více trojic. K chybné interpretaci při tom může vést definice, že u kombinací na uspořádání nezáleží (zatímco u variací záleží).

Pokud použijeme čísla oboru N jako popis prvků, tato mají pouze existenční rozměr 1 celá a velikost podle součtu vyjadřuje k, nebo n. To se týká jednoho řádku. Počet řádků je součtem součinů z řádků. Počet řádků je dán podle druhu množiny. U kombinací je to kombinační číslo C(k,n), u variací V(k,n), nebo také k!C(k,n). Počet permutací P(n) je dán dle mne jinak, nežli jen jako V(n,n), nebo n! – popíšeme dále.

Uspořádání prvků do k-tic a n-tic

Označení n, k je dáno a stejně tak k ≤ n. Přestože je k podmnožinou n (a takto ji také přebírá algebra), je potřebné ještě odlišit podmnožiny další a to jak v rámci n, tak v rámci k. Oba pojmy mohou být v rámci rozkladů dále fragmentovány stejně jako by se jednalo o dvě různé množiny.

Příklad ze statistiky : Zjišťujeme pravděpodobnost rozložení 5 prvků do dvou částí celku 100.

Části ze 100 prvků možných n nejsou nutně stejné – volíme n₁ = 40 , n₂ = 60, což jsou 2 n-tice.
Výběr k = 5 se může celý vyskytnout jak v jedné části, tak v druhé části. Mimo toho ještě všechny možnosti mezi 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, konkrétně :

n₁(40), k₁(0) n₂(60), k₂(5)

n₁(40), k₃(1) n₂(60), k₄(4)

n₁(40), k₅(2) n₂(60), k₆(3)

n₁(40), k₆(3) n₂(60), k₅(2)

n₁(40), k₄(4) n₂(60), k₃(1)

n₁(40), k₂(5) n₂(60), k₁(0)

Poznámka : Konkrétní výpočet ukážeme v kapitole věnované aplikacím statistiky a pravděpodobnosti..

Na příkladu můžeme pozorovat, že máme pouze 2 n-tice, ale hned 6 k-tic. Právě kvůli podobným potřebám, musíme zavádět pojmy, které se navzájem dost pletou. Je nutno pochopit, že k-tice nejsou n-tice a nemohou se navzájem zaměňovat. Každý rozklad k-tic se v rámci schematu sice vyskytuje 2x, ale vždy v jiné n-tici. Bez kontextu bychom mohli považovat opakovaný výskyt k-tic za variace s opakováním jak je uváděno v rámci polynomů. Tak to ale není. Pokud bychom zvolili v předchozím schematu stejné poloviny, odpadne i „opakování“, což si ukážeme na výpočtech v rámci vzorových výpočtů.

Vazby mezi prvky a pořadí prvků

Mezi základní vlastnosti kombinatorických množin patří vazby prvků v množinách a také podmnožinách. O jaké vazby se jedná? V rámci n-tic i k-tic jde o jednice, dvojice, trojice apod. Opět použijeme schema, nyní n = 5 a rozdělení do dvou n-tic :

n-tice 0+5 = 5+0 :

počet 0 neobsahuje žádné vnitřní vazby a byla přidána symbolicky aby existovaly 2 díly.

počet 5 obsahuje 5 jednic, 10 dvojic, 10 trojic, 5 čtveřic a jednu pětici.

Součet n-tic z obou dílů = 0¹ + 5¹ + 10¹ + 10¹ + 5¹ + 1¹ = 32

n-tice 1+4= 4+1 :

počet 1 obsahuje pouze jedinou jednici.

počet 4 obsahuje 4 jednice, 6 dvojic, 4 trojice, 1 čtveřici.

Součet n-tic z obou dílů = 5 jednic, 6 dvojic, 4 trojice a 1 čtveřici = 5¹ + 6¹ + 4¹ + 1¹ = 16

n-tice 2+3= 3+2 :

počet 2 obsahuje pouze 2 jednice a 1 dvojici

počet 3 obsahuje 3 jednice, 3 dvojice, 1 trojici.

Součet n-tic z obou dílů = 5 jednic, 4 dvojice, 1 trojici = 5¹ + 4¹ + 1¹ = 10

Poznámka : Zatímco první rozklad má „plný počet“ n-tic (2⁵ = 32), druhý případ má už pouze 16 n-tic (2⁴ = 16) a zatím to vypadá, že by i třetí poslední případ měl mít 8 n-tic, tedy (2³ = 8) ale má jich 10. Příčina je v počtu dvojic, respektive v počtu druhů n-tic. Prvé dva rozklady obsahují sudý počet n-tic (6 a 4) zatímco třetí a poslední případ má lichý počet n-tic (3).

Rozklad podle schematu výše se neřídí podle kombinací ale množinou, která se nazývá „Partition“, respektive původním názvem „Partition Numerorum“ (PN). Česky se jedná o „oddíly“, nebo lépe „číselné oddíly“ stejného základu n. Více naleznete pod odkazem Partition. Pro 5 prvků platí následující schema rozkladu :

Použili jsme rozklad do dvou dílů n, tedy n-tic a použili všechna možná a různá uspořádání od první po druhou třídu PN(5). Třídou PN(n) je myšlen počet n-tic(dílů) z celku n. První třída každého PN je rovna n, a v rámci PN jde o jedinou podmnožinu. Proto jsem přidal ještě nulu, aby vznikl dojem dvou dílů.

První a druhá třída PN(n,1), PN(n,2) je obrazem souměrnosti na Pascalově trojúhelníku. Často se vyskytuje v souvislosti s k-ticemi výrok, který uvádí, že souměrnost je dána „doplňkem“, nebo „zbytkem“ k výběrům k, například C(k,n) = C(n-k,n). Správně by to mělo být popsáno jako pojem z algebry, konkrétně sigma-aditivní zbytek, nebo doplněk. Jen pro lepší představu řádek Pascalova trojúhelníku pro n = 5 vyjádříme vzorci takto : C(0,5)=C(5,5), C(1,5)=C(4,5), C(2,5)=C(3,5).

Vidíme 1. dvojici, která obsahuje také nulu, tedy k = 0 konkrétně ve vzorci C(0,5). To je důvod, který mne vedl k přidání nuly do rozkladu PN, protože PN vůbec nulu neobsahuje a neobsahuje ani opakování n-tic. Například 2+3 je stejné jako 3+2. Teorie doposud nespojovala rozklady n, k přímo s PN(n), ačkoliv vždy spojovala PN(n) v nějaké formě s kombinatorikou.

Vlastní uspořádání kombinatorických množin. Pojem uspořádání patří do oblasti „teorie uspořádaných množin“. Z této teorie by se dal pro kombinatoriku použít pouze pojem „poset“. Musíme si připomenout, že kombinatorické množiny obsahují prvky bez označení, a pořadí takových prvků není vůbec relevantní. Můžeme si ale zvolit označení podle potřeby. Mohou to být různé geometrické útvary, barvy, nebo také čísla. Čísla jsou tradičně z oboru celých kladných čísel a značení prvků nemá žádnou vlastní velikost, má jen logickou hodnotu – prvek existuje. Pro označení platí jenom jedno pravidlo, prvky musí být značeny unikátně, tak aby byl každý prvek jednoznačně identifikovatelný. Označení prvků je nutné zejména pro demonstraci variací.

To, co si musíme ještě vysvětlit je skutečnost, že PN(n) a Faktoriál(n) jsou unární množiny a každý řádek tabulkové reprezentace sestává ze všech různých prvků n, což není podmínka unarity jako takové, ale v rámci kombinatoriky je důležitá unárnost jednotlivých prvků. Kombinace, variace a permutace mají binární prvky a v tom se od PN(n) a F(n) odlišují. Z tohoto důvodu automaticky zahrnujeme také nulu, která je nejlépe vidět právě v Pascalově Trojúhelníku (PT). Této vlastnosti využijeme s výhodou právě u binárních prvků v podobě exponentu a využíváme rovnosti mezi výrazy 0⁰ = 0¹ = 1⁰ = 1¹. Binární prvky potom značíme jako p^0,1 přičemž využíváme pouze exponent (kardinální řád), proto například 7⁰ = 7¹ = 1. U některých zápisů použijeme s výhodnou ordinérní řád. Znovu opakuji, že číslo je jenom značka a nemůžeme ho zaměnit s vlastní velikostí značky. Značky mají pouze logickou hodnotu 1 z kauzální existence.

Nyní použijeme schema pozičního zápisu pro kombinace a poté i na variace. Jedná se nám o pojem uspořádání k-tic z celku n.

Poziční zápis respektuje záznam všech prvků n na řádku. V běžné praxi se tento nepoužívá. Zajímá nás pouze určitá k-tice. Do tabulkové reprezentace zapisujeme pouze preferovaný druh k-tice, ale nesmíme zapomenout že ten zbytek je kauzálně podmíněn svou existencí. Oba způsoby jsou správné, ale zápis pouze požadované k-tice je praktičtější. Rozlišujeme buď n-zápis, nebo k-zápis.

Variace jsou typické pořadím prvků v k-tici, respektive v n-tici. Známé je schema pro k-zápis, ale poradíme si také v n-zápisu. Toto obsahuje motivující problém, který se v rámci k-zápisu nevyskytuje. Proto musíme seřadit správně také ignorované prvky p⁰. Jako ukázku zvolíme první řádek n-zápisu ze schematu uvedeného výše (trojice 1,2,3). Každá variace trojice má 3! podob, tedy 6. Zápis podle n znamená čtveřice, těch je ale 4! = 24. Proto se příklad zaměří pouze na 6 řádků z celku 24 který zobrazuje jen první trojici.

Poziční n-zápis i zkrácený k-zápis podléhají faktoriálu. Samozřejmě víme, že u kombinací existuje rovnost například pro model loterie 6 losovaných z celku 49 C(6,49) = C(43,49). Je ale v rámci hazardu správné losovat variace V(6,49) a tvrdit při tom že to jsou kombinace, nebo naopak ignorovat sigma-aditivní zbytek? Příklad jenom ilustruje problém. Ten existuje u jiných loterií, které skutečně pořadí prvků vyhodnocují. Více v kapitole Permutace.

K pozičním zápisům ještě dodáme jinou vhodnou variantu. Index u prvků PN(n), ani faktoriálu F(n) vybavovat nemusíme, protože to jsou unární prvky. U binárních prvků to také není úplně nutné. Prvky výběru jsou pod indexem 1 a prvky zbytku pod indexem nula, ale pokud použijeme konvenci, nemusíme používat kardinální řád. Jednoduše místo ignorovaných prvků použijeme nulu a prvky výběru zapíšeme jen značkou. To by bylo použití ordinérního řádu. Například pro V(3,4) by vypadaly takto : 1230, 1203, 1320, 1302, 1023, 1032, 2130, 2103, 2310, 2301, 2013, 2031, 3120, 3102, 3210, 3201, 3012, 3021, 0123, 0132, 0213, 0231, 0312, 0321. Opět připomínám, že čísla jsou pouze značky a každé různé číslo včetně nuly má pouze logickou hodnotu 1.

Poznámka : Nemůžeme například čtveřici 1230 číst jako tisí-dvě-stě-třicet. Není to číselný výraz, ale alfabetický a mezi členy neexistuje jakákoliv souvislost na základě vlastní velikosti prvků. Nesmyslnost pochopíme jakmile si uvědomíme, že n může být více, nežli jednociferné číslo. Správně bychom měli například dvojciferné n vyjadřovat řádem například : 010203 abychom zachovali logiku čísel se dvěma číslicemi. Například trojici 1,2,11 musíme zapsat jako 010211, pokud bychom zapsali pouze 1211, získáme dojem, že jde o variace s opakováním (větší třídy a menšího n) a problém se stoupajícím řádem (n>99) eskaluje. Tato skutečnost ztěžuje třídění sloupců k-tic a n-tic, a řešíme ji pomocí UV, tedy unikátní hodnoty, což je také nový pojem v rámci kombinatoriky.

Pořadí prvků v n-ticích a k-ticích se řídí faktoriálem. Faktoriál je poměrně známou záležitostí, kterou se budeme zabývat ve specializované kapitole. Zde upozorníme pouze na skutečnost, kterou je nutné si zapamatovat. Zatímco z Pascalova Trojúhelníku vyplývá symetrie podle osy souměrnosti, neplatí to pro variace stejných tříd n. Chyba vznikne při chybě záměny variací za kombinace, což se podbízí právě při vyjádření sigma-aditivního zůstatku.

Téměř ve všech případech platí pro kombinace C(k,n) = C(n-k,n). Jedinou výjimkou jsou případy, sudých n, která mají lichý počet tříd v řádku PT. Prostřední třída a současně maximum řádků nemá párovou hodnotu a je jakoby podvojná sama v sobě.

Poznámka : Můžeme expresivně vyjádřit, že se do určité míry vyrovnávají obecné pojmy sudá a lichá. Lichý počet n má sudý počet členů na řádku PT, a sudý počet n naopak lichý počet členů. To je také důvod proč lze každý řádek PT vyjádřit jako 2ⁿ.

V případě variací platí nerovnost členů V(k,n) ≠ V(n-k,n), nebo také k!C(k,n) ≠ (n-k)!C(n-k,n) což je logické, pokud si uvědomíme, že ve většině případů faktoriály k! ≠ (n – k)!. Symetrie v rámci PT podle osy souměrnosti se týká pouze kombinací.

Kombinační, variační a permutační princip

Jednotlivé principy výběru (jako postupy realizace k) se navzájem odlišují. Kombinatorické principy determinují pojmy kombinací, variací a permutací. Současné definice jsou veskrze chybné a také značně zavádějící „U variací na pořadí záleží, u kombinací nikoliv a permutace = V(n,n)“.

Kombinační princip :

U kombinací se jedná o výběr prvků k naráz. Z počtu n naráz vybereme k prvků. Představa výběru kombinačním principem a stejně tak všechny další principy demonstrujeme na množinách prvků bez označení. Princip zapisujeme takto :

k = n – k

Výpočet kombinačním vzorcem, respektive C(k,n).

Variační princip :

U variací se jedná o postupný výběr k po jednom prvku. Princip zapisujeme například takto :

1 → (n – 1) schema (1¹) + (1⁰+1⁰+1⁰+1⁰+1⁰+1⁰+ … n-1)

2 → (n – 1) – 1 schema (1¹+1¹) + (1⁰+1⁰+1⁰+1⁰+1⁰+ … n-2)

3 → (n – 2) – 1 schema (1¹+1¹+1¹) + (1⁰+1⁰+1⁰+1⁰+ … n-3)

………… ……………………

k → (n – k) schema (1¹+1¹+1¹+1¹+1¹+1¹) + (1⁰+… n-k)

Výpočet vzorcem pro variace V(k,n), respektive k!C(k,n).

Permutační princip :

Permutační princip vybírá kombinovaně podle kombinací a variací, řídí se podle PN(k). Představíme si množinu neoznačených prvků, potom odpovídají kombinace 1. třídě PN(k) a variace poslední třídě PN(k). Kombinace a variace jsou krajní hodnoty (extrémy) PN(k). Ukázka PN(5) :

Výpočet je dán pro každý řádek samostatně. Ukázky ve vzorových výpočtech.

Tento princip odpovídá podmnožinám k prvků bez označení, kde není možnost variace jednotlivých prvků, ale je možná variace podmnožin v řádku. Střední třídy jsou částečně kombinacemi a částečně variacemi.

Připomeneme si, že PN(n) je obrazem, který neobsahuje nulu, ani variaci. Kombinatorické principy vysvětlujeme na množinách neoznačených prvků, což znamená, že využíváme pouze rozklad podle PN(k). Vliv variace, jinak také faktoriálu se s principem PN prolíná tak, že jednotlivé podmnožiny rozdělené podle PN(n) jsou značky, které už mohou mít variaci v pozici k-tice (řádku) a to i bez označení prvků. Permutace jako permutační princip s obrazem v PN(n) obsahují nulu i variace, přestože vlastní prvky označeny nejsou.

Závěr kombinatorických principů :

Kombinatorické principy jsou v této podobě novou součástí teorie, která by měla nahradit stávající pojmy (definice) vyjadřující co jsou kombinace, variace a permutace. Původní pojmy kombinací, variací, permutací a faktoriálu rozšiřujeme o Partitio Numerorum PN(n).

Výpočet vzorcem P(n) = n!PN(n). Více ve vzorových výpočtech.

Kombinace

Jsou primárním pojmem kombinatoriky z vícero důvodů. Po kombinacích je tradičně pojmenována celá tato oblast matematiky. Odvozujeme z nich Variace a Permutace. V mnoha aplikacích jsou kombinace páteřní kostrou vyjádření například ve formě kombinačních čísel, koeficientů, binomů atd. Symbolicky nejlépe reprezentuje kombinace Pascalův trojúhelník.

Definice kombinací :

Kombinace jsou dobře uspořádané, stejně mohutné a různé k-tice z výběru celku n možných.
Zdůvodnění souvisí se vztahem kombinací k variacím.

Demonstrace kombinací :

Pro nativní demonstraci kombinačního principu použijeme nejlépe dvě stejné misky. V jedné misce máme n různých ale neoznačených kuliček (například ocelové kuličky z ložiska). Z této misky vybereme určitý počet k kuliček a naráz vložíme do druhé misky. V jedné misce máme k prvků a v té druhé n – k. To je princip podle typu výběru, ale nemůžeme kauzálně doložit, kolik různých výběrů existuje, protože prvky nemají označení.

Hypoteticky, nebo i reálně (opticky) provedeme totéž, ale nyní už s označenými prvky – nejlépe alfabetickými znaky. Tak zjistíme, že existuje podle označení až C(k,n) různých výběrů se stejnou mohutností, což můžeme kauzálně dokázat například systematickým (nebo také náhodným) výběrem, kde se zapíší pouze různé k-tice. Jednotlivé k-tice jsou různé pokud se odlišují alespoň jedním znakem prvku.

Poznámka :
Při takovém dokazování, kdy k vybíráme naráz skutečně nezáleží na pořadí prvků ve výběru. Tuto skutečnost nelze vyjádřit jako definici kombinací (nezáleží na pořadí prvků ve výběru). Problém definice kombinací souvisí těsně s pojmem variací. Kombinace jsou základním schematem variací, ze kterého pomocí rozvoje faktoriálem získáme variace. Problém označení prvků je sekundární záležitostí a pojem řazení jako „uspořádání“ je až třetí v pořadí. Řazení prvků podle číselné značky je pro kombinatorické množiny velice relativní a spíš irelevantní.

Označení prvků může být různé, nemusí to být ani čísla, ani písmena. Prvky můžeme označit samostatně barvami, nebo geometrickými a jinými symboly. Tyto typově různé značky mohou být libovolně kombinované v jediné množině n prvků – nemusí odpovídat stejnému charakteru.

Potřebujeme sice pořadí, ale to musíme primárně určit. Například značku čtverce označíme pořadím číslo 1, červenou barvu vybavíme pořadím číslo 2, smajlíka vybavíme pořadím číslo 3, ….. Jednoznačně explicitní přiřazení pořadového čísla má až faktoriál(n) možností volby. Proto je relativní. Z tohoto důvodu je také relativní hovořit o jakémkoliv „uspořádání“ podle pozice prvků.

Množiny kombinací (a podobně všechny ostatní) mohou mít primárně pouze grafickou reprezentaci v podobě prvků uspořádaných do čtverců, nebo obdélníků. To i v případě, že mají určené pořadí, potom jde vždy o obdélníky (tabulky) pokud je n > 2. Grafickou reprezentací rozumíme také čtvercové tabulky znázorňující vazby mezi prvky (průsečíkové grafy). Čtvercem reprezentujeme logické vazby na rozdíl od obdélníků, které jsou taxativním výpisem různých k-tic, nebo n-tic.

Vždy se jedná nejméně o sekundární, tedy relativní záležitosti, které můžeme vyjádřit algebraicky. Vlastní kombinatorika vychází z jednoduché aritmetiky. Algebra čerpá z kombinatoriky, a může ji zpětně popsat, ale v podstatě jen na základě konvence – relativních značek a jejich relativního pořadí.

Principem jde o konvenci pořadí prvků, kterou přebíráme axiomaticky. Zpětně také důvěřujeme algebraickému popisu kombinatorických množin, ale zpětně nemůžeme na základě algebry definovat například kombinace, variace a permutace s opakováním. Jedná se pouze o formu aparátu výpočtu, který funguje sice nesporně, ale nemůže z toho vznikat nelogická a nekauzální definice tak jako například u variací s opakováním.

Spojitost mazi kombinacemi a binárními množinami :

Celkem známou skutečností je součet všech tříd kombinací stejného základu. Ne každý si toto správně představí. Nejlepší představu vytvoří tabulka, která porovná binární zápis a zápis kombinací. Použijeme grafickou reprezentaci nekauzální množiny 2³ kterou současně vyjádříme jako kombinace (což pokládáme za nepřímou kauzalitu binárních množin). Vytvoříme tabulku, která obsahuje 8 řádků. Hodnoty ve sloupci označíme velkými písmeny A,B,C. Tato písmena jsou substitučně poplatná dvěma různým posloupnostem. A(buď 2⁰, nebo 1), B(buď 2¹, nebo 2), C(buď 2², nebo 3) a nula :

Poznámka : Zápis tak jak je vyveden umožňuje n-zápis včetně variací. K dokazování spojitostí postačují dva poslední sloupce. V případě binárního zápisu už další variace nemají význam.

Zde si musíme připomenout pojem řazení. Řádky jsou řazeny vzestupně podle tříd kombinací, zatímco bychom mohli použít obvyklé řazení podle binárního zápisu. Problém je v tom, že konvence zápisu binárního vyjádření je jiná, nežli u kombinací. Binární zápisy se provádí zprava doleva, kombinace opačně. Na tom příliš nezáleží. Také si připomeneme, že používáme ordinérní řád pro popis a za důležitou pokládáme skutečnost, že každý řádek stejného schematu má unikátní výraz pro každý různý typ množiny. Z toho plyne, že jsme schopni stejný symbolický zápis číst dvěma různými způsoby.

Poznámka : To má celkem blízko ke kryptografii. Nejen že můžeme stejné schema (binární) číst jako kombinace, ale můžeme za určitého předpokladu substitučně číst například interval prvočísel zejména pro asymetrické šifry. Může to být matice 64², která se upravuje maticově a z pohledu steganografie se skryje mezi běžné textové řetězce Unicode, nebo Base64.

Důležitá je skutečnost, že binární množina má již uvedenu „aritmetickou velikost“ za řádek, ale kombinace mají pouze algebraický znak, který má logickou hodnotu, ale nikoliv vlastní velikost.

Přes to využíváme u znaků kombinací (čísel) jejich vlastní aritmetickou velikost, kterou bez ostychu používáme k řazení. To funguje, ale musíme vědět, že to je jenom domluvená pomůcka (konvence).

Na základě takové konvence můžeme aritmetickou velikost znaků kombinací uspořádat podle teorie uspořádaných množin a potom se dopracujeme k tomu, že „dobře uspořádané“ kombinace rozvíjí variace stejné třídy a základu za pomoci faktoriálu (více v kapitole Variace).

Variace

Jsou zřejmě nejfrekventovanějším pojmem mezi kauzálními pojmy. Princip spočívá v uspořádání unikátních prvků na různých pozicích k-tic a n-tic. To je vliv faktoriálu k!, nebo n!.

Definice variací :

Variace jsou stejně mohutné a různé k-tice z výběrů celku n možných, které se navzájem odlišují jak obsahem různých prvků, tak pořadím prvků v k-tici. Variace vznikají z kombinací podle rozvoje faktoriálem(k) a považujeme je za uspořádané na rozdíl od dobře uspořádaných kombinací. Kombinace jsou podmnožinou variací.

Demonstrace variací :

Opět použijeme dvě misky. Jedna miska obsahuje n kuliček. Vždy odebereme 1 kuličku z 1. misky a vložíme do druhé. Takto pokračujeme až do okamžiku, kdy druhá miska obsahuje k kuliček.

Důrazně doporučuji vztah mezi kombinacemi a variacemi odvozovat od výrazu V(k,n) = k!C(k,n), aby se neztrácela vazba mezi kombinacemi a variacemi stejné třídy – konkrétně :

Důvodem je snaha definovat pomocí uspořádání kombinace jinak, nežli variace. Je to celkem zásadní chyba, protože počet variací obsahuje kombinace. Proto je nepřijatelné tvrdit, že u variací na pořadí záleží, zatímco u kombinací nikoliv. Kombinace jsou v podstatě nejen uspořádané, ale nutně také „dobře uspořádané“, protože vzestupné (dobré) seřazení na kombinace mezi ostatními variacemi prostě zbývá – nemohou být uspořádané jinak.

Rozvoj variací z kombinací pomocí k! je velice dobře znám a zřejmě většina skript takovou tabulku rozvoje obsahuje, ačkoliv současně obsahuje stejnou chybnou definici.

Poznámka : Pojem dobře uspořádané kombinace a uspořádané variace vyvolává dojem nekompatibility, protože část podmnožin je uspořádána dobře a zbytek už je pouze uspořádán. Názor se opírá o skutečnost, že kombinace jsou seřazeny v řádku (nepodmíněně) ve sloupci pouze vzestupně, tedy „dobře“, ale když seřadíme množinu variací včetně kombinací zanikne dobré uspořádání kombinací. Pro představu C(2,4) a V(2,4) :

C(2,4) = 12 < 13 < 14 < 23 < 24 < 34. Uvnitř dvojic jsou číslice dobře (vzestupně) uspořádané.
V(2,4) = 12 < 13 < 14 < 21 < 23 < 24 < 31 < 32 < 34 < 41 < 42 < 43. Uvnitř některých dvojic není dobré (vzestupné) uspořádání (2>1, 3>1, 3>2, 4>1, 4>2, 4>3).
Připomínáme relativitu řazení podle axiomatické konvence vlastní velikosti čísel jako značek prvků.

Příklad tabulky pro V(3,4) :

Tabulka výše má kombinace jako předpis v prvém řádku. Tabulka se může vyskytovat také v transponované podobě, kdy jsou kombinace jako předpis ve sloupci. Tabulka jednoznačně ukazuje kombinace jako součást variací s rozvojem podle faktoriálu (3!) = počet řádků v tabulce s jedním sloupcem 24 trojic včetně kombinací.

Poznámka : Je to sice dobrý důkaz, ale jak jsme si už uvedli, jde jen o relativní značky prvků a logiku uspořádání, respektive řazení podle velikosti čísel – to přebíráme axiomaticky z konvence.

Výraz „swap“ je znám z informatiky, kterým se označuje prohození dvou značek (čísel) v pozicích. Konkrétně tedy nejde o výraz matematický, ale princip je dobře znám. Lze se s ním setkat například u popisů řadících algoritmů, zejména BubbleSortu a podobně. Záměna značek v podobě swapu je typická pro faktoriál a variace – více v kapitole faktoriál.

Permutace

Permutace je výraz používaný v rámci současné teorie pro speciální případ variací, které mají k = n. Konkrétně V(n,n) = n!. Podle stávající teorie permutace P(n) = V(n,n) = n!. To je trojnásobný výraz pro stejnou skutečnost.

Definice permutací :

Permutacemi jsou všechna různá uspořádání prvků podle PN(n). Kombinace a variace jsou extrémy.

Demonstrace permutací :

Opět použijeme misku obsahující n kuliček a druhou prázdnou misku. Nyní libovolně volíme výběr počtu kuliček < k. Například nejprve dvě kuličky a vložíme do prázdné misky, následně vybereme jednu kuličku a přidáme ji k dříve vybraným dvěma, potom vybereme naráz tři a přidáme do misky, která reprezentuje výběr. Pokračujeme takto dál dokud v misce výběru není k kuliček. Počet různých výběrů z celku k je dán jako PN(k).

Poznámka : Něco podobného jako trojnásobný výraz známe z křesťanské teologie jako Boží Trojice či trojjediný Bůh. Tato trojjedinost může sloužit dobře asi jen ke zmatení žáků. Úplně stačí, že faktoriálu jsou rovny variace stejné třídy a základu. K problému permutací, respektive k „trojjedinosti“, můžeme přistoupit dvěma základními náhledy. Buď zcela zamítnout permutace jako pojem bez důvodu, nebo najít důvod, který zapadá do koncepce základů, respektive kauzality. Takový důvod existuje a je celkem ve shodě s původní definicí, jen ji rozšiřuje.

Permutace jsou vnímány jako nadmnožina množin s binárními prvky. Faktoriál ale není množina binárních prvků. Existuje například dvojitý faktoriál, multifaktoriál, a jsou i další, které se dají použít i v rámci kombinací nebo variací. Tyto pojmy a jiné „super-množiny“ značně překračují rámec kombinatorických základů. Pro představu : n! * (n-1)! * (n-2)! * (n-3)! … až * (n=1)!, nebo podobně 2ⁿ * 2^(n-1) * 2^(n-2) * 2^(n-3) * 2^(n-4) … až * 2⁽ⁿ⁼¹⁾.

Nově vyjádříme permutace P(n) jako všechna uspořádání prvků podle PN(n) a faktoriálu(n). Počet potenciálních permutací je dán jako n!PN(n). Kombinace a variace jsou krajní a také extrémní případy z celkového počtu PN(n) řádků. Znázorníme si tabulku pro permutační princip :

Poznámka : V tabulce číslo 9 jsou uváděny variace n-tic, zatímco vzorec ukazuje kombinace. Toto je důsledek skutečnosti, která říká, že kombinace jsou součástí variací C(k,n) ⊂ V(k,n).

Další celkem nejasnou záležitostí se může jevit pojem vnějších n-tic. Existují ještě vnitřní n-tice, které by se měly značit jako k-tice, což ale také není úplně správné. Podstata je popsána v kapitole 3 tabulce číslo 2, kde je to vyjádřeno na množině, kde k < n. V našem případě jde o množinu která má stejný výběr k = n. Přes to vysvětlíme pojem vnitřních a vnějších k-tic, n-tic infantilně.

Vnitřní n-tice jsou pro představu dány jako prvky n, které mají vzájemný dotyk (ať už přímý, nebo nepřímý, tedy zprostředkovaný). Z pohledu geometrie mohou mít nejvýše 4 stejné kuličky vzájemný dotyk (reprezentace pyramidou kuliček). Pátá stejně velká kulička už nemůže mít přímý dotyk se všemi původními (čtyřmi) kuličkami. V rámci kombinatoriky tento aspekt zanedbáváme.

Vnějšími n-ticemi chápeme vztah mezi různými n-ticemi, tedy díly n. V rámci množin k = n je představa poněkud zkreslena a další podobně matoucí záležitostí jsou množiny neoznačených prvků. Podstatu je možné lépe pochopit na množinách s označenými prvky a při k < n. Pro představu si vypomůžeme terminologií z oblasti pravděpodobnosti – „n-tice“ z celku n jsou jako jevy pravděpodobnosti navzájem vyloučeny (mezi n-ticemi není dotyk).

Z popisu už poznáváme, že kombinace (C) ⊂ variace (V) ⊂ permutace (P). Jinak můžeme vyjádřit také nerovnost C < V < P, protože P(n) = PN(n)*V(n), V(n) = n!*C(n). To se dá vyjádřit takto :
P(k,n) = PN(k)*k!C(k,n) a pro C(n,n) takto : P(n) = n!*PN(n)
Na nerovnosti se podílejí obě unární množiny, tedy PN a faktoriál. Proto nově definujeme permutace jako množinu PN(n) krát větší, nežli faktoriál(n). Tím jsme odstranili také trojjedinost permutací, respektive faktoriálu.

Faktoriál

Definice faktoriálu :

Faktoriál n je unární množina prvků, odlišujících se pořadím prvků v n-tici alespoň na dvou pozicích každé n-tice mezi všemi různými n-ticemi.

Faktoriál je vnímán více jako funkce, tedy vzorec, který vyjadřuje počet, nikoliv jako množina. Tato množina má n! řádků a n členů v každém řádku klasicky vyjádřených formou velikostí čísla, například 5! = 5*4*3*2*1, což odvádí pozornost od podstaty. Jedná se o pořadí prvků, což můžeme dokázat různými značkami, například písmeny, nebo jakýmikoliv jinými značkami. Například pro 5! značkami bez vlastní velikosti, jen s existenční hodnotou 1 a vedle pomocné číselné pořadí :

Otázka řazení vzestupně, nebo sestupně je obecný problém všech množin a souvisí zejména s realizačním algoritmem, který tabulku generuje. Existuje také výraz pro funkci, která počet řádků vypočítá. Hovoří se někdy o iterativní, nebo rekurzivní funkci faktoriálu. Iterativní algoritmus je takový, který členy součinu inkrementuje o jedničku, tedy 1*(1+1)*(2+1)* …*n, zatímco opačný rekurzivní dekrementuje. Tedy n*(n-1)*(n-2)*(n-3)* …*1. Pro vyjádření počtu řádků je to přímo nepodstatné, ale u generujícího algoritmu množiny, který vytváří tabulkovou podobu je to zásadní.

Generujících algoritmů může být více druhů, ale vždy se jeden považuje za typický, nebo reprezentativní a ten se vyznačuje tím, že generuje množinu jako pokud možno „dobře seřazenou“. To znamená v řádku buď vzestupně (Ascending „A“) a ve sloupci také tak, nebo opačně, tedy v řádku i sloupci sestupně (Descending „D“). U většiny množin kombinatorického typu existuje plná kombinace 2² možností AA (vzestupně řádek i sloupec), AD (vzestupně řádek, sestupně sloupec), DA (sestupně řádek, vzestupně sloupec), nebo DD (sestupně řádek i sloupec).

Vlastní podoba tabulkově vyjádřené množiny potom souvisí s vlastní velikostí značek, ale musíme vědět, že ty mají „vlastní velikost“ jen díky axiomatické konvenci. U faktoriálu se navíc nabízí názor, že funkce vyjadřující počet řádků (n!) souvisí s tělesovým uspořádáním prvků v řádcích a sloupci. To není pravda.

Například pro faktoriál můžeme zvolit „grafický algoritmus“, který sice generuje v určitém pořadí, ale neodpovídá přímo žádné ze 4 možností (AA, AD, DA, DD). Princip „grafického algoritmu“ (swap) pro faktoriál v tabulce číslo 11.:

Demonstrace swapování faktoriálu :

Poznámka : Samozřejmě i tento algoritmus lze realizovat opačně. Konkrétně přidávat další prvek vždy na prvou pozici – tedy více méně sestupným způsobem, zatímco výše znázorněný přidává nejprve nakonec a postupně do středních pozic až nakonec na první pozici.

V tabulce 11 je znázorněn algoritmus, který ač grafický, odpovídá stylu popisu funkce n!, tedy začínáme jedním prvkem „a“, a přidáme k němu „b“. Následně prohodíme pozice prvků (swap). Tím dostáváme dvojici kterou rozšíříme třetím prvkem „c“, a následně čtvrtým prvkem „d“. Trojice obsahuje 3 pozice v n-tici. Původně čtvercovou matici ab|ba (se dvěma pozicemi) povýšíme na tři pozice kam třetí prvek postupně vložíme. To znamená trojnásobné opakování původní čtvercové matice. Odpovídá to funkci n!, tedy například pro faktoriál(5) = ((((1*2)*3)*4)*5).

Poznámka : Přes to takto vytvořená množina není vhodná k reprezentaci. To se dá upravit „seřazením“ celé množiny, ale … Technicky lze číselně řadit pouze velice omezeně. V některém případě sice množinu seřadíme, ale pro n! < 17 neumíme dekadicky vyjádřit správný počet řádků, protože stroj za 17. řádem zaokrouhluje a v případě 170! už neumí ani zaokrouhlit – vyhazuje chybu. Tento problém se dá řešit pomocí „variací s opakováním“ formou vyšší číselné soustavy zapisované textovým řetězcem. Problematika tohoto typu je shrnuta do kapitoly UV.

Naopak uvedená množina je vhodná k demonstraci swapování. Dobře je to vidět u čtveřic, kde se nejprve přidá značka D nakonec. Postupně se pořadí swapuje se sloupcem vlevo až se dopracujeme k D na první pozici. Napříkad : abcD, +swap cD = abDc, +swap bD = aDbc, +swap aD = Dabc.

Podle tabulky číslo 12 odvozujeme členy součinu 5!. Součtu prvků odvozujeme na intervalu od 1 do n = 5. Jedná se o posloupnost, která obsahuje (5² – 5)/2 + 5 jednic = 15, což je stejné jako výraz 5² – C(2,5), tedy 25 – 10, nebo také C(2,5) + 5, tedy C(2,n) + n. Nezáleží vůbec na skutečnosti zda n je sudé, nebo liché.

Faktoriál nemá žádné třídy a to ani přeneseně. Za třídy faktoriálu by se daly považovat variace, ale variace považujeme za kombinace rozvinuté faktoriálem. Za třídy faktoriálu nelze považovat ani „super-množiny“ typu „dvojitý faktoriál“, nebo multi-faktoriál a podobně.

Partition

Odkaz na pojem Partition.

Definice Partition :

Partition vyjadřuje počet všech možných součtů čísel z celku n.

Partition je schematem entropie a ve fyzikální asociaci také schematem „velkého třesku“.

Partition je stejně jako faktoriál unární množinou, zatímco ostatní kombinatorické množiny jsou množiny binárních, nebo větších prvků.

Partition je zkratkou původního názvu Partition Numerorum, česky „oddíly čísel“ a značíme ho v rámci kombinatoriky značkou PN(n), protože jako „P“ jsou již značeny permutace.

Partition je dnes velice frekventovaný pojem zejména pro oblast informatiky, kdy pod pojmem partition rozumíme přímo diskové oddíly, nebo oddíly nerotačních pamětí.Obecně je tento pojem zahrnut pod teorii čísel a aplikací je až neuvěřitelně mnoho na to, jak jednoduchá je podstata.

V rámci teorie čísel jsou jednotlivé řádky PN(n) nazývány „orbity“, ale domnívám se, že vhodnější je nazývat jednotlivé řádky „stavem množiny“ (prvků n) a stejně tak pro faktoriál. Jedná se především o obecnější pojem „uspořádání“, kterým se odlišují jak různé kombinatorické množiny, tak také jednotlivé řádky stejné množiny.

V rámci kombinatoriky rozeznáváme u PN(n) třídy, což je počet podmnožin n.

5 1. třída 1 podmnožina n₁ = 5

4+1 2. třída 2 podmnožiny n₁ = 4, n₂ = 1

3+2 2. třída 2 podmnožiny n₁ = 3, n₂ = 2

3+1+1 3. třída 3 podmnožiny n₁ = 3, n₂ = 1, n₃ = 1

2+2+1 3. třída 3 podmnožiny n₁ = 2, n₂ = 2, n₃ = 1

2+1+1+1 4. třída 4 podmnožiny n₁ = 2, n₂ = 1, n₃ = 1, n₄ = 1

1+1+1+1+1 5. třída 5 podmnožin n₁ = 1, n₂ = 1, n₃ = 1, n₄ = 1, n₅= 1

Každé PN(n) má počet tříd = n. Krajní třídy (orbity) 1. a n-tá sestávají z jediného stavu. Mimo těchto má stejnou vlastnost ještě třída (n – 1), tedy předposlední třída.

Díky takto určeným třídám má PN(n) 8 různých možností seřazení, zatímco ostatní kombinatorické množiny mají maximálně 4 možnosti. Není snadné určit, jaké seřazení je nejdůležitější, nebo nejreprezentativnější. Žádné neodpovídá „dobrému seřazení“. Proto preferujeme podobu, kterou bylo PN(n) původně uvedeno a tradičně definováno, tedy od největší n-tice k nejmenší viz Partition. Mimo toho, že se jedná o původní uspořádání, reprezentuje toto také obraz entropie, což je velmi důležité a celkem unikátní napříč matematikou i aplikacemi.

Doporučuji podívat se sem Orderings – OEISWiki. Na otevřené stánce je náhled tabulky, která ukazuje různé možnosti uspořádání. Osobně prferuji uspořádání podle 3. sloupce zleva s nadpisem Rev Lex*. Což znamená „Reverse Lexicographic order“, česky „obrácené lexikální uspořádání“, nebo lepe uspořádání sestupné v řádku i sloupci. Více v kapitole Partiton Numerorum.

Pro kombinatoriku má PN(n) význam zejména jako obraz všech možných rozdělení n. Důležitost PN(n) zjistíme zejména při výpočtech z oblasti pravděpodobnosti, konkrétně při výpočtech hypergeometrického rozdělení jevu pravděpodobnosti.

Enumerační vzorce a výpočty

Mezi základy kombinatoriky pro edukační účely základních škol doporučuji zahrnout vzorce enumerací pro kombinace C(k,n), variace k!C(k,n) a faktoriál. Permutace P(n) jsou vzhledem k PN(n) složitější na vysvětlení, proto postačuje vyjádření, že tento pojem je množinou nad ostatními. Konkrétně to vyjádříme vztahem C(k,n) < V(k,n) < P(k,n).

V rámci středoškolského učiva už by mělo být zdůvodněno více. Nejen P(n), ale také kauzalita pojmů s opakováním a výpočty z oblasti teorie pravděpodobnosti.

Dostáváme se k výpočtům, které jsou známé pouze z určité části, proto musíme jejich platnost dokázat výpočtem. Budeme vycházet z hypergeometrického rozdělení jevu pravděpodobnosti. Základ je dobře znám, ale platí také ve formě rozšířené verze, o které se musíme přesvědčit důkazem ve formě vzorových výpočtů. V kapitole „Uspořádání prvků do k-tican-tic“ jsme použili schema dvou n-tic a šesti k-tic, které nyní provedeme formou výpočtu hypergeometrického rozdělení jevu pravděpodobnosti n = 100, A=40, k = 5, x (0, 1, …, 5) pro každý řádek samostatně :

Hypergeometrické rozdělení jevu pravděpodobnosti vyjadřuje relativní četnost jako pravděpodobnost určitého uspořádání. Tato relativní četnost se opírá o přesný diskrétní výpočet, který nás zajímá více jako důkaz správného postupu.

Pokud postup platí pro 2 n-tice, musí platit i pro více n-tic z celku n. Znamená to schopnost použít výpočetní mechanizmus na každý stav PN(n), což už tak snadné není. Přes to řešit každý rozklad PN(n) lze stejně přesně jako pro 2 n-tice a sice za předpokladu, že všechny výsledky z diskrétních výpočtů na řádcích dávají součet kombinací C(k,n).

Základ rozšířeného schematu si ukážeme na množině kombinací C(5,25). Jedná se o případ n = k². Takový typ diskrétní množiny kde n = k², a podobně k = sqrt(n) u spojité množiny nazveme přirozenou množinou.

Příklad demonstruje enumeraci nad PN(5) v pravidelně rozděleném n = 5². Z pohledu výpočtu je zde problémem sloupec „variace“. Již dříve jsme si vysvětlovali, že kombinace jsou součástí variací, proto by nás to nemělo překvapovat. Sloupec variací chápeme jako statistickou váhu základního výpočtu, která značně zjednodušuje výpočtové schema. Sedmý řádek ukazuje jak zapadá systém variací s opakováním do kauzality kombinací.

Ne vždy budeme řešit takto ideální rozvržení n-tic a k-tic. Nastávají při tom 3 různé problémy, které jsou celkem velice nepříjemné. Vzorové postupy výpočtu jsou uvedeny zde (kopie původního webu) :
Příklad 1 Příklad 2 Příklad 3 Příklad 4. Příklady se zabývají z větší části statistikou, a proto doporučuji prohlédnout nejdříve příklady bez popisu speciálních rozborů :

1. Třída n-tic < třída k-tic. Všechny třídy k-tice > n-tice automaticky v rámci výpočtu vynecháváme. Máme li například PN(k=2, n=100), můžeme pro schema výpočtu použít pouze k-tice 1. a 2. třídy. To je zřejmé z dříve uvedené ukázky. PN(k) obsahuje 5 tříd, ale příklad má pouze 2 n-tice. Proto k-tic může být nejvýše stejně jako n-tic.
2. Každá k-tice může být veliká (mohutná) nejvýše jako n-tice. Všechny případy kdy nastane případ k-tice > n-tice stejně jako v prvém případě vynecháváme.
3. V případech, kdy se na řádku výpočtu objeví stejné k-tice ve stejných n-ticích, podléhá tento případ výpočtu kombinací. V jiném případě výpočtu variací.

Výpočty se řídí vztahem podle počtu tříd n-tic takto :

Unikátní hodnoty (UV) k-tic a n-tic.

Pojem UV vychází z potřeby pracovat s označením prvků, řádků a sloupců kombinatorických množin. V praxi se neobejdeme bez přiřazení pořadí v nějaké podobě čísel. Celkem samozřejmé je použít číselné pořadí místo značek. Například pro množiny n do velikosti 10 (jednomístné) vystačíme s čísly 0 až 9. Potom můžeme zápis n-tic a k-tic vyhodnocovat přímo jako čísla. Ale obecně potřebujeme systém, který lze porovnávat i pro veliká k a n, kde už dekadický řád nepostačuje a nepostačuje ani číslování pomocí šestnáctkové soustavy (hexadecimální).

Unikátní hodnoty mají primárně určovat velikost jednotlivých stavů podle „vzájemně porovnatelné velikosti“. Převedeme – li značky jednotlivých stavů na hodnoty můžeme celou množinu seřadit podle velikosti. Neznamená to ale, že se jedná o pořadí od „1“ do „n“ tak jak to známe například v podobě unikátního klíče v případě databází.

Můžeme například zaměnit infimum UV = 1, přiřadit postupně další čísla až získáme supremum UV = n. Tak získáme pořadí bez závislosti na vlastní hodnotě a stejně tak můžeme systém vlastních hodnot stavů zkrátit ve smyslu zápisu vyšší n-prvkovou a k-bitovou soustavou (hodnota stavu je tak zachována a z výrazu lze systém značek zpětně přímo odvodit).

UV není tedy pořadovou hodnotou od jedničky, hashem ani GUID (Globally Unique Identifier) přestože tyto případy (Unikátní index, hash a GUID) plní podobnou úlohu. Toho můžeme využít výhodně v kryptografii. Například konkrétní tvar značek vyjádříme formou pořadového kroku generátoru kde je klíčem vlastní generátor. Konkrétně není známo jakou množinu generuje a v jakém systému seřazení. Generátor lze snadno oddělit od běžného kódu protože běží v CACHE (mezipaměť), nebo na extra procesoru a vydá výstup jinam, nežli do zdroje odkud přišlo číslo. Veskrze se jedná o možnost ukrýt generátor a jeho výstup v běžném kódu (steganografie).

Řešení zápisu pro veliká k, n existuje například v podobě variací s opakováním n-prvkové a k-bitové soustavy. Výhodně tak můžeme použít například Base64, tedy 64 čísel v alfanumerické podobě. (Musíme vědět, že ze 64 značek musíme jednu vyhradit nule, takže ze 64 čísel dosáhneme pouze na číslo 63.)

Base64 může být seřazena až 64! krát jinak. Když dostaneme číslo pořadí musíme ještě vědět, že se jedná o Base64 a nikoliv o kombinace C(k,1024), nebo PN(256) a podobně.

Můžeme používat číselné pořadí shodné s krokem generátoru (například kombinací) a rychle měnit klíče například přidáním počtu kroků generátoru. Počet kroků mezi jednotlivými „klíči“ může být dán nelineární funkcí, která je sama a sobě klíčem. Při takto vzniklém pořadí může být číslo použito jako modulo pro úplně jiný systém, nežli má generátor pořadí – například pro Unicode apod.

Teoreticky lze jakýkoliv text zašifrovat na číslo pořadí, které neříká nic o tom jakého je původu, tedy jaký generátor byl použit a na jakou množinu se vztahuje. Klíče se mohou měnit s každým znakem.

Poznámka : Výše uvedený popis směřuje k problému, který je znám pod pojmem „kryptokalipsa“, který se zabývá šifrováním odolným i proti kvantovým počítačům. Viz Kryptokalipsa.

Grafické reprezentace a tabulky

Grafickými reprezentacemi rozumíme zejména záznam logických vazeb v kvadratickém grafu. Tabulkové reprezentace potom vyjadřují vlastní zápis množin značek. Tyto již v převážné většině nejsou ve čtvercových grafech, ale v obdélníkových.

Logické reprezentace zápisů

Tyto reprezentace se zabývají zejména logickými vazbami mezi prvky stavů, nebo celé množiny což vychází z logické podstaty prvků kombinatorických množin. Základem je průsečíkový graf ploch. V takových grafech můžeme zobrazovat nejen logické vazby, ale také vlastní velikosti.

1. Příklad logického záznamu vazeb

Máme sestrojit tabulku trojic, které obsahují všechny dvojice celku n = 7 {a, b, c, d, e, f, g}.
Analýza : všech dvojic z celku 7 = C(2,7) = 21. Těchto 21 dvojic se vejde do 21/3 = 7 trojic, tedy do tabulky 7×3 prvky. Tabulku provedeme na základě odečtu z průsečíkového grafu.

2. Příklad logický záznam binomu

Ve druhém příkladu vidíme možnost vyjádřit binomy a polynomy pomocí logických schemat. Musíme si uvědomit, že nyní máme v přeponě kvadrantu čtverce, což neplatí pro první příklad. Ale operace nad a popřípadě pod přeponou jsou schematicky stejné.

Tabulkové reprezentace zápisů

Tabulkové reprezentace pro kombinatoriku se neliší od jiných tabulek, přes to rozlišujeme určité druhy tabulek zejména podle obsahu.

Výpisy

Za výpisy označujeme tabulky obsahující všechny k-tice, nebo n-tice určitého typu množin. Výpisy nemusí být specificky seřazené, ale musí obsahovat unikátně všechny k-tice, nebo n-tice. Například neúplné tabulky nemusí být nutně výpisem, ani rozpisem. Takové bychom očekávali v případě statistických nálezů. Podobně nahlížíme na tabulky kde se nějaký stav opakuje. Pojmem výpis označujeme také specificky „random“ seřazený obsah k-tic, n-tic (výpis všech rozpisů určitého typu). Příkladem je následující tabulka :

Výpis sestává z 84 trojic celku n = 9 které jsou uspořádány do 28 čtvercových matic s obsahem všech jednic. Tyto matice jsou potom uspořádány po čtyřech do sloupců, které obsahují všechny dvojice z celku 9. Existuje 15360 podobných uspořádání.

Rozpisy

Rozpisy lze označit jako části výpisů, které mají specifický obsah, nebo vlastnost. Výraz „rozpis“ není standardně definovaný a různí autoři si přizpůsobují věcný obsah. Rozpisy jsou v praxi velice rozšířené v různých oblastech a pod různými názvy. Mezi rozpisy zahrnujeme zejména různé typy řádů. Například jízdní řády, pracovní řády, funkční schemata a podobně. Setkáváme se s názvy jako například „grafikony“, „pravidla“ a další například časové plánování v rámci logistiky. Veskrze se jedná o ustanovení nejvýhodnějších (popřípadě i záložních řešení) vazeb mezi prvky.

Význam rozpisů je v tom, že umožňují v rámci aplikací dosahovat opakovaně nejefektivnějšího řešení úkolu (popřípadě řešení očekávaného problému). Pod tímto pojmem si musíme představit sice statický model, který je ale možné dynamicky obměňovat tak aby výsledkem byl vždy úspěch.

Etalony

Etalony jsou striktně uspořádané výpisy. Většinou pod tímto pojmem rozumíme množinu „dobře uspořádanou“, tedy množinu uspořádanou vzestupně jak v řádku, tak ve sloupci. Ale etalon nemusí být jen ve vzestupném seřazení. Měli bychom pochopit, že se jedná o „tradiční“, nebo „typické“ popřípadě „reprezentativní“ uspořádání. Například faktoriál bývá nejčastěji řazen vzestupně jak v řádku, tak ve sloupci, ale PN je tradičně řazen sestupně (od největší k-tice k nejmenším), a existuje 8 různých možností seřazení. Sestupné schema je dáno původním zveřejněním problému.

Etalon si představíme nejlépe jako databázovou tabulku, nebo generátor s nejlépe iterativním algoritmem podle kterého se prohledává, respektive poměřuje a spojujeme ho s logikou postupného odvození z unikátní existence v (kauzálním) minulém, nebo budoucím (predikovaném) čase.

Pascalův trojúhelník

Pascalův trojúhelník symbolizuje prakticky celou kombinatoriku, je znám už hodně dlouho, ale stále nevydal všechna svá tajemství. Proto je předmětem zkoumámí i v dnešní době.

Na tomto vyjádření je fascinující co se z něho dá vyčíst a odvodit. Obsahuje posloupnosti jako je například součet čísel z řádku Pascalova trojúhelníku, který je roven mocnině čísla 2, nebo Fibanacciho posloupnost, a nebo fraktální útvary a další.

Lze na něm odvodit součet nekonečné řady z řádku „e“, tady k základu přirozeného logaritmu ve formě součtu nekonečné řady, nebo také uváděné jako limita následující posloupnosti. Nevím zda je možné uvádět tuto skutečnost jako nově objevenou, nebo jen nově vyjádřenou. V každém případě jsem našel souvislost která je mírně odlišná od dříve uvedeného součtu :

Výše uvedené vyjádření dokazuje souvislost mezi Pascalovým trojúhelníkem (PT) a základem přirozených logaritmů. Tímto je také nepřímo prostřednictvím Eulerovy rovnosti (identity) prokázaný vztah mezi konstantou π a PT.

Závěr

Pascalovým trojúhelníkem dle mne končí základy kombinatoriky.

V rámci výuky základů postačuje podle této práce definovat kombinace, variace a pojmy s opakováním. U permutací postačí konstatování, že jsou nadmnožinou předchozích pojmů (podle PN). Mezi základní pojmy řadíme ještě Faktoriál a Partitio Numerorum, které jsou množinami unárních prvků, zatímco ostatní (n, k, kombinace, variace, permutace) jsou množinami binárních prvků.

U pojmů s opakováním stačí uvést skutečnost, že tyto jsou nekauzální respektive, že mají nepřímou kauzalitu z kombinací bez opakování. Název s „opakováním“ je historicky tradován, ale prvky se ve skutečnosti neopakují, jen jejich podmnožiny (mince mají dvě strany, kostky 6). U podmnožin platí pouze 1 strana z možných a zbytek je pro jednotlivý náhodný pokus vyloučen.

Z Pascalova trojúhelníku lze odvodit vazby na další matematické disciplíny. Jedná se tedy o řady 2ⁿ, Fibonacciho posloupnost, Eulerovo číslo e, konstantu π, binomickou větu, fraktály (Sierpińského trojúhelník) a další.

Tato práce se zabývá více elementárním dokazováním, které by mělo vést k uvedeným definicím z nichž je asi nejdůležitější „Kombinatorika je matematická disciplína zabývající se uspořádáním množin logických prvků.“. Základní dokazování je na množinách neoznačených prvků. Označení prvků je konvence vztahující se nejlépe k číslům oboru čísel N (počínaje 1 .. n) v podobě pořadí (Euklidova číselná osa). V rámci kombinatoriky o vlastní velikosti čísel nehovoříme. To používá až algebra, která vyjádří například vzorcem kolik je kombinací určité třídy a základu …

Petr Neudek