Kombinatorické druhy - Combinatorial species

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v kombinační matematika, teorie kombinatorické druhy je abstraktní, systematická metoda pro analýzu diskrétních struktur z hlediska generující funkce. Příklady diskrétních struktur jsou (konečný ) grafy, obměny, stromy, a tak dále; každý z nich má přidruženou generující funkci, která počítá, kolik struktur má určitou velikost. Jedním z cílů teorie druhů je schopnost analyzovat složité struktury jejich popisem z hlediska transformací a kombinací jednodušších struktur. Tyto operace odpovídají ekvivalentním manipulacím generujících funkcí, takže vytváření takových funkcí pro komplikované struktury je mnohem jednodušší než u jiných metod. Teorie byla představena, pečlivě rozpracována a aplikována kanadskou skupinou lidí kolem André Joyal.

Síla teorie vychází z její úrovně abstrakce. "Formát popisu" struktury (například seznam sousedství proti matice sousedství pro grafy) je irelevantní, protože druhy jsou čistě algebraické. Teorie kategorií poskytuje užitečný jazyk pro koncepty, které zde vznikají, ale není nutné rozumět kategoriím, než budete moci pracovat s druhy.

Kategorie druhů odpovídá kategorii symetrické sekvence v konečných sadách.^[1]

Definice druhu

Schematické znázornění kombinatorické druhové struktury na pěti prvcích pomocí Labellova diagramu

S některými je spojena jakákoli struktura - instance konkrétního druhu soubor, a pro stejnou sadu je často mnoho možných struktur. Například je možné sestrojit několik různých grafů, jejichž popisky uzlů jsou nakresleny ze stejné dané sady. Současně bylo možné k sestavení struktur použít jakoukoli sadu. Rozdíl mezi jedním druhem a druhým je v tom, že ze stejné základní sady staví odlišnou sadu struktur.

To vede k formální definici a kombinatorické druhy. Nechat ${ displaystyle { mathcal {B}}}$ být kategorie z konečné množiny, s morfismy kategorie je bijekce mezi těmito sadami. A druh je funktor^[2]

${ displaystyle F colon { mathcal {B}} až { mathcal {B}}.}$

Pro každou konečnou množinu A v ${ displaystyle { mathcal {B}}}$konečná množina F[A]^{[poznámka 1]} se nazývá množina F-struktury na Anebo soubor struktur druhů F na A. Dále podle definice funktoru, je-li φ bijekce mezi množinami A a B, pak F[φ] je bijekce mezi množinami F-struktury F[A] a F[B], volala transport F-struktur podél φ.^[3]

Například „druh permutací“^[4] mapuje každou konečnou množinu A na soubor všech permutací Aa každou námitku z A do jiné sady B přirozeně vyvolává bijekci ze sady všech permutací A na soubor všech permutací B. Podobně lze „druh přepážek“ definovat tak, že ke každé konečné sadě přiřadíme celou sadu oddíly a „druh množiny výkonů“ přiřadí každé konečné množině své napájecí sada. Sousední diagram ukazuje strukturu na sadě pěti prvků: oblouky spojují strukturu (červená) s prvky (modrá), ze kterých je postavena.

Protože mezi dvěma konečnými množinami existuje bijekce právě tehdy, když mají dvě sady stejné mohutnost (počet prvků) pro každou konečnou množinu A, mohutnost ${ displaystyle F [A]}$, což je konečné, závisí pouze na mohutnosti A. (Vyplývá to z formální definice funktoru.^{[poznámka 2]}) Zejména exponenciální generující řady F(X) druhu F lze definovat:^[5]

${ displaystyle F (x) = součet _ {n geq 0} operatorname {Card} F [n] { frac {x ^ {n}} {n!}}}$

kde ${ displaystyle operatorname {Card} F [n]}$ je mohutnost ${ displaystyle F [A]}$ pro jakoukoli sadu A mít n elementy; např., ${ displaystyle A = {1,2, tečky, n }}$.

Několik příkladů: psaní ${ displaystyle f_ {n} = operatorname {Card} F [n]}$,

• Druhy sad (tradičně nazývané Ez francouzštiny "soubor", což znamená" set ") je funktor, který mapuje A do {A}. Pak ${ displaystyle f_ {n} = 1}$, tak ${ displaystyle E (x) = e ^ {x}}$.
• Druh S z obměny, popsáno výše, má ${ displaystyle f_ {n} = n!}$. ${ displaystyle S (x) = 1 / (1-x)}$.
• Druh T₂ párů (2-n-tice ) je funktor, který bere množinu A na A². Pak ${ displaystyle f_ {n} = n ^ {2}}$ a ${ displaystyle T_ {2} (x) = x (x + 1) e ^ {x}}$.

Počet druhů

Aritmetika generujících funkcí odpovídá určitým „přirozeným“ operacím na druhu. Základní operace jsou sčítání, násobení, složení a diferenciace; je také nutné definovat rovnost druhů. Teorie kategorií již má způsob, jak popsat, kdy jsou dva funktory ekvivalentní: a přirozený izomorfismus. V této souvislosti to znamená jen pro každého A mezi nimi je bijekce F-struktury na A a G-struktury na A, který je při interakci s transportem „vychovaný“. Druhy se stejnou generující funkcí nemusí být izomorfní, ale izomorfní druhy mají vždy stejnou generující funkci.

Přidání

Přidání druhů je definována disjunktní unie množin a odpovídá volbě mezi strukturami.^[6] Pro druhy F a G, definovat (F + G)[A] být disjunktní unie (také psaný "+") z F[A] a G[A]. Z toho vyplývá, že (F + G)(X) = F(X) + G(X). Jako ukázku si vezměte E⁺ být druhem neprázdných množin, jejichž generující funkcí je E⁺(X) = E^X - 1 a 1 druh prázdná sada, jehož generující funkce je 1(X) = 1. Z toho vyplývá, že E = 1 + E⁺: slovy, „sada je prázdná nebo neprázdná“. Rovnice, jako je tato, lze číst tak, že odkazují na jedinou strukturu i na celou kolekci struktur.

Původní definice druhu inspirovala tři směry vyšetřování.^{[Citace je zapotřebí ]}

- Po kategorické stránce je potřeba většího rámce, aby obsahoval produkt i produkt koprodukt. Cena je ztráta indexu cyklu.

- Jiný přístup přináší Burnsideovy kroužky nebo soupravy. Burnsideův součet reprezentací je formální notace používaná při zpracování teorie tabulek značek.

- Konečně obvyklá definice nebere v úvahu funkčnost a skutečnost, že druh, i když je považován za pravidlo, je jedinečný. Pro pravidlo F neexistuje druhé pravidlo F, které by vytvořilo disjunktní součet F + F. V tomto přístupu je definice sčítání ve skutečnosti definicí příkladu. Výhodou je přirozené vložení indexu cyklu jako elektrického nářadí.

Násobení

Násobení druh je o něco složitější. Je možné brát jako definici pouze kartézský součin množin, ale kombinatorická interpretace toho není zcela správná. (Použití tohoto druhu produktu viz níže.) Operátor násobení místo toho, aby dal dohromady dvě nesouvisející struktury na stejné sadě, používá myšlenku rozdělení sady na dvě složky a vytvoření F-struktura na jedné a a G-struktura na druhé straně.^[7]

${ displaystyle (F cdot G) [A] = součet _ {A = B + C} F [B] krát G [C].}$

Toto je disjunktní spojení se všemi možnými binárními oddílyA. Je jednoduché ukázat, že násobení je asociativní a komutativní (až do izomorfismus ), a distribuční nad sčítáním. Pokud jde o generující sérii, (F · G)(X) = F(X)G(X).

Níže uvedený diagram ukazuje jednu z možných (F · G) -struktura na sadě s pěti prvky. The F-struktura (červená) sbírá tři prvky základní sady a G-struktura (světle modrá) vezme zbytek. Ostatní struktury budou mít F a G rozdělení sady jiným způsobem. Sada (F · G)[A], kde A je základní sada, je disjunktní sjednocení všech takových struktur.

Sčítání a množení druhů jsou nejkomplexnějším vyjádřením pravidel součtu a součinu počítání.

Složení

Složení, nazývané také substituce, je opět komplikovanější. Základní myšlenkou je nahradit komponenty F s G-struktury, formování (F∘G).^[8] Stejně jako u násobení se to dělí rozdělením vstupní sady A; disjunktní podmnožiny jsou dány G dělat G-struktury a sada podmnožin je dána F, aby se F-struktura spojující G-struktury. Je to nutné pro G namapovat na sebe prázdnou sadu, aby složení fungovalo. Formální definice je:

${ displaystyle (F circ G) [A] = součet _ { pi v P [A]} (F [ pi] krát prod _ {B v pi} G [B]). }$

Tady, P je druh přepážek, takže P[A] je sada všech oddílů A. Tato definice říká, že prvek (F ∘ G)[A] je tvořen F-struktura na nějakém oddílu Aa G-struktura na každé komponentě oddílu. Generující řada je ${ displaystyle (F Circ G) (x) = F (G (x))}$.

Jedna taková struktura je uvedena níže. Tři G-struktury (světle modré) dělí mezi nimi pětičlennou základnu; pak an F-struktura (červená) je vytvořena pro připojení G-struktury.

Tyto poslední dvě operace lze ilustrovat na příkladu stromů. Nejprve definujte X být druh "singleton", jehož generující řada je X(X) = X. Pak druh Ar zakořeněných stromů (z francouzštiny „stromovost") je definován rekurzivně pomocí Ar = X · E(Ar). Tato rovnice říká, že strom se skládá z jednoho kořene a sady (pod) stromů. Rekurze ano ne potřebují explicitní základní případ: generuje pouze stromy v souvislosti s aplikací na nějakou konečnou množinu. Jedním ze způsobů, jak o tom přemýšlet, je, že Ar funktor je opakovaně aplikován na „přísun“ prvků z množiny - pokaždé, když je jeden prvek převzat Xa další distribuovány uživatelem E mezi Ar podstromů, dokud nejsou další prvky, které je třeba dát E. To ukazuje, že algebraické popisy druhů se zcela liší od specifikací typů v programovacích jazycích Haskell.

Stejně tak druh P lze charakterizovat jako P = E(E⁺): "oddíl je párová disjunktní sada neprázdných sad (využívajících všechny prvky vstupní sady)". Exponenciální generující řada pro P je ${ displaystyle P (x) = e ^ {(e ^ {x} -1)}}$, což je série pro Čísla zvonků.

Diferenciace

Diferenciace druhů intuitivně odpovídá budování „struktur s dírou“, jak je znázorněno na obrázku níže.

Formálně,^[9]

${ displaystyle (F ') [A] = F [A uplus { star }],}$

kde ${ displaystyle star}$ je nějaký odlišený nový prvek, který není v ${ displaystyle A}$.

Abychom rozlišili související exponenciální řady, je třeba posunout posloupnost koeficientů o jedno místo „doleva“ (ztráta prvního členu). To naznačuje definici druhů: F' [A] = F[A + {*}], kde {*} je singletonová sada a „+“ je disjunktní sjednocení. Pokročilejší části teorie druhů používají diferenciaci značně ke konstrukci a řešení diferenciální rovnice o druzích a sériích. Myšlenka přidání (nebo odebrání) jedné části struktury je silná: lze ji použít k navázání vztahů mezi zdánlivě nespojenými druhy.

Zvažte například strukturu druhu L lineárních objednávek - seznamy prvků základní sady. Odstranění prvku ze seznamu ho rozdělí na dvě části (případně prázdné); v symbolech to je L ' = L·L. Funkce exponenciálního generování L je L(X) = 1/(1 − X), a vskutku:

${ displaystyle { frac {d} {dx}} {(1-x)} ^ {- 1} = {(1-x)} ^ {- 2}.}$

Druh C cyklických permutací trvá sadu A do sady všech zapnutých cyklů A. Odebrání jednoho prvku z cyklu jej sníží na seznam: C' = L. Můžeme integrovat generující funkce L vyrábět to proC.

${ displaystyle C (x) = int _ {0} ^ {x} { frac {dt} {1-t}} = log { frac {1} {1-x}}.}$

Pěkným příkladem integrace druhu je dokončení linie (koordinované polem) s nekonečným bodem a získání projektivní linie.

Další operace

Existuje celá řada dalších manipulací, které lze s druhy provádět. Ty jsou nezbytné k vyjádření složitějších struktur, jako jsou řízené grafy nebo bigrafy.

Polohovací^{[Citace je zapotřebí ]} vybere jeden prvek ve struktuře. Vzhledem k druhu F, odpovídající špičatý druh F^• je definováno F^•[A] = A × F[A]. Tedy každý F^•-struktura je F-struktura s rozlišením jednoho prvku. Ukazování souvisí s diferenciace vztahem F^• = X·F' , tak F^•(X) = X F' (X). Druhy špičaté sady, E^•, je zvláště důležitý jako stavební kámen pro mnoho složitějších staveb.

The kartézský součin dvou druhů^{[Citace je zapotřebí ]} je druh, který může stavět dvě struktury na stejné sadě současně. Liší se od běžného operátoru násobení v tom, že všechny prvky základní sady jsou sdíleny mezi těmito dvěma strukturami. An (F × G) -strukturu lze považovat za superpozici F-struktura a G-struktura. Bigrafy lze popsat jako superpozici grafu a sady stromů: každý uzel bigrafu je součástí grafu a zároveň součástí nějakého stromu, který popisuje, jak jsou uzly vnořeny. Generující funkce (F × G)(X) je Hadamardův nebo koeficientový produkt F(X) a G(X).

Druh E^• × E^• lze vidět, že provádí dva nezávislé výběry ze základní sady. Tyto dva body se mohou shodovat, na rozdíl od v X·X·E, kde jsou nuceni se lišit.

Jako funktory, druhy F a G lze kombinovat pomocí funkční složení:^{[Citace je zapotřebí ]} ${ displaystyle (F , Box , G) [A] = F [G [A]]}$ (používá se symbol rámečku, protože kruh se již používá jako náhrada). Tím se vytvoří F-struktura na množině všech G-struktury na scéně A. Například pokud F je funktor, který vezme množinu do své výkonové množiny, struktura složeného druhu je nějaká podmnožina G-struktury na A. Pokud nyní vezmeme G být E^• × E^• shora získáme druh řízených grafů s povolenými smyčkami. (Směrovaný graf je sada hran a hrany jsou páry uzlů: graf je tedy podmnožinou sady dvojic prvků sady uzlů. A.) Tímto způsobem lze definovat další rodiny grafů a mnoho dalších struktur.

Software

Operace s druhy jsou podporovány SageMath^[10] a pomocí speciálního balíčku také pomocí Haskell.^[11][12]

Varianty

• Druh v druzích k je funktor ${ displaystyle { mathcal {B}} ^ {k} rightarrow { mathcal {B}}}$. Zde mohou vytvořené struktury obsahovat prvky čerpané z odlišných zdrojů.^{[Citace je zapotřebí ]}
• Funktor do ${ displaystyle { mathcal {B}} _ {R}}$kategorie Rvážené sady pro R A prsten výkonové řady, je a vážené druhy.^{[Citace je zapotřebí ]}

Pokud se „konečné množiny s bijekce“ nahradí „konečnými vektorovými prostory s lineárními transformacemi“, získá se pojem polynomiální funktor (po uložení nějaké podmínky konečnosti).^{[Citace je zapotřebí ]}

Viz také

• Kontejner (teorie typů)

Poznámky

Reference

• André Joyal, Une théorie combineatoire des séries formelles„Advances in Mathematics 42: 1–82 (1981).
• Labelle, Jacques. Quelques espèces sur les ensembles de petite cardinalité., Ann. Sc. Matematika. Québec 9.1 (1985): 31-58.
• J. Labelle a Y.N. Jo, Vztah mezi Burnsideovými kroužky a kombinatorickými druhy, Journal of Combinatorial Theory Series A 50, (1989) 269–284
• Yves Chiricota, Classification des espèces moléculaires de degré 6 et 7, Ann. Sci. Matematika. Québec 17 (1993), č. 1. 1, 1 l – 37.
• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combineatoire des structures arborescentes, LaCIM, Montréal (1994). Anglická verze: Kombinatorické druhy a struktury podobné stromům, Cambridge University Press (1998).
• Kerber, Adalbert (1999), Applied finite group actions, Algorithms and Combinatorics, 19 (2nd ed.), Berlin, New York: Springer-Verlag, ISBN  978-3-540-65941-9, MR 1716962, OCLC 247593131

externí odkazy

• Weisstein, Eric W. "Druh". MathWorld.
• https://ncatlab.org/nlab/show/species