Specii (matematică)

În matematică, speciile sunt o noțiune care poate fi poziționată între logică și aritmetică.

• Aspect aritmetic : specia extinde, la același nivel de înțelegere, noțiunile fundamentale de număr ordinal/cardinal, către alte tipuri de numere, cum ar fi numere ciclice, numere poligonale, numere partiționale, numere arborescente etc. Astfel de noțiuni se învață pe de rost în clasele primare.
• Aspect logic : definițiile și identitățile combinatorice pot fi privite ca propoziții a căror valoare de adevăr nu este 0 sau 1 (fals sau adevărat, nici-unul sau unul-sau-mai-multe) dar a căror valoare arată exact numărul de realizări ( via coeficienții funcției generatoare exponențiale ) ale obiectului (structurii) descrise în propoziție.
• Aspect combinatoric : În combinatorică, specia descrie o clasă de structuri combinatorice, care pot fi puse în corespondență biunivocă printr-o bijecție având o proprietate de functorialitate, adică copiază nu numai cardinalitatea unei mulțimi, dar și structura combinatorică asociată.
• Aspect informatic : În informatică, speciile se manifestă ca suporturi (containere) pentru diferite tipuri abstracte de date, cum ar fi liste, arbori etc.
• Aspect geometric : Noțiuni elementare cum ar fi linia și transformările ei, planul și transformările lui, dreapta proiectivă etc. au (cel puțin în geometriile finite) descrieri în termeni de specii și operații cu specii.
• Aspect algebric : Noțiuni fundamentale cum ar fi grupul sau corpul au descrieri în termeni de specii și operații cu specii. Specia poate fi privită ca o structură ce nu a fost coordonatizată încă; totuși anumite operații elementare rămân posibile și în absența reperelor și a coordonatelor.

Datorită adâncimii conceptului, este nevoie de un metalimbaj pentru a putea defini speciile și operațiile cu specii. De aceea expunerile despre specii conțin termeni din teoria categoriilor, diagrame, pasaje de text special marcate sau texte scrise în diverse limbaje de programare.

Istoric

Se spune că primul exemplu de calcul cu specii a fost dat la concursul de matematică nord-american Putnam, la o problemă legată de numărul de partiții.

„Une partition est un ensemble d'ensembles non-vides.” ( O partiție este o mulțime de mulțimi nevide. )

În termeni de teoria speciilor, aceasta se scrie :

Part = Ens ( Ens₊ )

Funcția generatoare exponențială asociată este :

part (x) = exp (exp (x) - 1)

Coeficienții funcției generatoare exponențiale part (x) sunt

1, 1, 2, 5, 15, 52, 203, 877, 4140,... Șirul A000110 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

adică numărul de partiționări ale unei mulțimi de n elemente distincte.

Exemple

Exemple de specii concentrate pe cardinalitatea cinci

Sunt 5.4.3.1 moduri de a eticheta unul din grafurile descrise ; chiar dacă cele două grafuri sunt diferite, etichetarea lor este în esență aceeași

OOOOO este descrisă ca X.Ens₂ (X.X)

X.X.X.X.X reprezintă un „șir” de cinci sloturi cu poziții bine determinate (numărul ordinal cinci), în care pot fi puse obiecte distincte,

iar Ens₅ reprezintă un sac în care pot fi puse cinci obiecte distincte, (numărul cardinal cinci) fără ca acestea să poată avea poziții precizate.

Exemplu de număr ciclic cinci

五行 sau Wu Xing : cele cinci transformări,

火 (foc) → 土 (pământ) → 金 (metal) → 水 (apă) → 木 (lemn) → 火 ( și din nou, foc)

Exemple de specii concentrate pe optsprezece, douăzeci și cinci și respectiv, cinci

Trei zaruri = Ens₃ ( X.Ens₅ )

Cub' = X. [ Cyc₂ ( Lin₁₂ ) + Cyc₃ ( Lin₈ ) + Cyc₄ ( Lin₆ ) ]

Planul lui Fano" = X.Grupul lui Klein

Exemplu de primitivă

Primitiva unui număr ciclic, în cazul în care există, este un corp finit

Field_r' = Cyc_r-1

unde r este o putere a unui număr prim.

Specii moleculare

„Arbore (etichetat) cu două, trei sau 4 noduri” este o specie care nu este moleculară. Există 1 + 3 + 12 + 4 = 20 de moduri de a eticheta un arbore cu două, trei sau patru noduri

O specie moleculară este o specie care nu poate fi scrisă ca sumă de alte specii. O componentă moleculară a unei specii este în întregime descrisă de acțiunea lui S_A restrânsă la o singură orbită, care este asociată în mod unic unui subgrup de permutări (subgrupul stabilizator al unei realizări). Însă din puzderia de grupuri de permutări numai o parte infimă deține o exprimare în termeni simpli de teoria speciilor și o interpretare combinatorică inteligibilă.

Numărul de realizări ale unei specii moleculare este n!/m, unde n este gradul grupului de permutări asociat, iar m este ordinul acestui grup. Astfel, spectrul speciilor moleculare este cuprins între Ens și Lin având un număr de realizări cuprins între 1 și n!.

Exemple și contra-exemple

• Ens₃ - cu trei elemente poate fi formată o singură mulțime ( această mulțime poate fi scrisă în șase moduri distincte : { a, b, c } = { b, a, c } =...= { c, a, b} ). Specia „mulțime” sau „număr cardinal” are o singură realizare, și nu este o sumă de alte specii.
• Cyc₃ - cu trei elemente pot fi formate două cicluri de lungime trei, ( a b c ) și ( a c b ). Fiecare din cicluri are câte trei scrieri echivalente ; spre exemplu, ( a b c ) = ( b c a ) = ( c b a ). Să notăm aceste cicluri C₁(a, b, c) și C₂(a, b, c). Se poate scrie :

C₁( a, b, c ) = C₂( b, a, c )

adică prin transpunerea a două simboluri, unul din cicluri se transformă în celălalt. Dacă realizările unei specii sunt transformabile din una în alta prin astfel de operații, specia este moleculară.

• Sunt două tipuri de arbori cu 4 noduri. Un lanț O-O-O-O are 12 realizări (există 12 moduri distincte de a eticheta/colora un lanț cu patru culori), în timp ce o stea are numai 4 realizări (dată de alegerea unei culori din patru pentru centru). Prin permutarea a două culori, o realizare de tip lanț este transportată tot într-un lanț, iar o stea merge tot într-o stea. În acest caz, specia arbore cu 4 noduri nu este moleculară, ci este suma a două specii moleculare.

Specii atomice

O specie care nu poate fi scrisă ca produs de alte două specii este numită atomică.

Exemple și contraexemple

• Cilindrii, de forma Cyc(Lin), sunt specii atomice.
• Grupurile combinatorice, sau specia grup, sunt date de către grupurile (finite) exact tranzitive.
• Corpurile combinatorice sunt date de către grupurile (finite) exact dublu tranzitive.
• Dreptele proiective sunt date de către grupurile (finite) exact triplu tranzitive.
• Cele cinci fețe ale unei prisme triunghiulare drepte împreună cu cele șase rotații sunt o specie atomică.

A	B	C	d	e
A	C	B	e	d
B	A	C	e	d
B	C	A	d	e
C	A	B	d	e
C	B	A	e	d

Cele șase linii ale tabelului de deasupra arată reetichetări echivalente ale prismei. Atunci numărul de reectichetări esențial distincte va fi de 5! / 6 = 20. Una dintre reetichetările esențial distincte ar putea fi, de pildă, A d B C e.

• Speciile partiționale (produse de mulțimi) sunt moleculare dar nu și atomice.

Cele patru operații de bază

Notațiile pentru cele patru operații de bază au fost alese asfel ca forma ecuațiilor să permită extragerea directă a funcției generatoare exponențiale (f.g.e.). Cele patru operații combinatorice extind calculele cu funcții generatoare în sensul că mai multe specii distincte pot avea aceeași f.g.e.. Dacă singurele specii considerate ar fi de tip Ens_n, (numere cardinale) informația despre oricare specie construită din acestea ar fi conținută exhaustiv în f.g.e..

Adunarea

O specie poate fi înțeleasă ca o multimulțime de specii moleculare.

Spre exemplu, multimulțimea {{ 2, 2, 2, 3, 5 }} capătă în teoria speciilor aspectul :

F = Ens₂ + Ens₂ + Ens₂ + Ens₃ + Ens₅

În exemplul de mai jos, permutarea a două etichete A și B lasă pe loc două copii ale mulțimii formate din A și B, și comută între ele cele două realizări AB și BA - perechi formate din A și B.

permutările de etichete A B

A B B A

acționează asupra

{ A, B } { A, B }

{ {A}, {B} } { {A}, {B} }

AB BA BA AB

În total, specia Ens₂ + Ens₂ + Lin₂ are 1+1+2 = 4 realizări.

Produsul

Produsul a două specii F × G este produsul a două multimulțimi, adică multimulțimea produselor de specii moleculare {{ F.G }} unde F este în F și G în G.

La rândul lui, produsul a două specii moleculare poate fi definit cu ajutorul grupurilor stabilizatoare asociate.

Spre exemplu, produsul Ens₃.Ens₂ va avea următorul grup de permutări asociat:

A B C A C B B A C B C A C A B C B A

×

D E E D

=

A B C D E A B C E D A C B D E A C B E D B A C D E B A C E D B C A D E B C A E D C A B D E C A B E D C B A D E C B A E D

Exemplul de mai sus se referă la partiționarea unei mulțimi cu 5 elemente în două clase a câte 3, respectiv 2 elemente. Funcțiile generatoare exponențiale ale speciilor Ens₃ .și Ens₂ sunt

$1.{x^{3} \over 3!}$ și respectiv $1.{x^{2} \over 2!}$

Produsul funcțiilor generatoare exponențiale este

$1.1.{x^{3} \over 3!}.{x^{2} \over 2!}={5! \over 2!.3!}.{x^{5} \over 5!}=10.{x^{5} \over 5!}$

așadar există 10 moduri de a partiționa cinci obiecte în două clase a câte 3, respectiv 2 obiecte.

Produsul a două specii moleculare poate fi privit în mod natural ca o specie multisort, ceea ce este o reflectare a principiului multiplicativ :

F[ X ] . G[ X ] = F[ X ] . G[ Y ]    / X = Y

Derivarea

Prin „derivarea” unei specii se obține o altă specie.

Exemplu

Prismă triunghiulară ===== derivare ====> X.Cyc₃ + Cyc₂(X.X)

Să presupunem că cele cinci fețe ale unei prisme triunghiulare drepte trebuie etichetate cu cinci etichete diferite. După aplicarea unei prime etichete, pe un triunghi sau pe un pătrat, ceea ce rămâne de etichetat este specia derivată.

Astfel, în cazul în care prima etichetă a fost aplicată pe un triunghi, al doilea triunghi este unic determinat, în timp ce pentru cele trei pătrate rămase, libertatea de reetichetare (nedeterminarea) este descrisă de un ciclu de lungime 3, ceea ce se formulează ca X.Cyc₃ .

În cazul în care prima etichetă a fost aplicată pe un pătrat, libertatea de reetichetare este descrisă de un cilindru plin Cyc₂(X.X).

Funcția generatoare exponențială pentru specia derivată este :

$x\cdot 2.{x^{3} \over 3!}+1.{x^{2} \over 2!}\circ (x\cdot x)={x^{4} \over 3}+{x^{4} \over 2}=20.{x^{4} \over 4!}$

Prin integrare se obține funcția generatoare a prismei de la care s-a pornit :

$20.{x^{5} \over 5!}$

În concluzie, există 20 de moduri de a colora cele cinci fețe ale unei prisme cu cinci culori diferite.

Calculul „clasic” presupune să se partiționeze 5 culori în 2 + 3 (sunt 10 variante) ; după aplicarea a două culori pe fețele triunghiulare, prisma capătă o orientare, ceea ce dă două moduri de a aplica cele trei culori rămase pe fețele pătrate : 10 × 2 = 20.

Cazul (F+G)'

Prin derivarea unei sume de specii moleculare se obține suma derivatelor.

(F+G)' = F'+G'

Derivarea unei specii moleculare

În cazul în care stabilizatorul are o singură orbită, stabilizatorul speciei derivate este Fix(a), stabilizatorul unei singur simbol.

În cazul mai multor orbite, prin derivarea unei specii moleculare se obține o sumă de specii moleculare, fiecare componentă corespunzând unei orbite a stabilizatorului. Deoarece o specie moleculară cu mai multe orbite este în mod natural o specie multi-sort, spre exemplu Cub(F,M,V), componentele derivatei corespund sorturilor de etichete (trei, pentru un cub).

Prisma triunghiulară din exemplul de mai sus, având două triunghiuri T și trei pătrate P se derivează ca specie multi-sort astfel :

Prismă triunghiulară (T,P) ===== derivare ====> T.Cyc₃(P) + Cyc₂(T.P)

Astfel, derivata este suma derivatelor parțiale în raport cu fiecare sort.

Compunerea

Speciile pot fi exprimate ca sume (multimulțimi) de specii moleculare, așadar pentru exemplificarea compunerii trebuie considerate trei cazuri. F ,F₁ , F₂ , G , G₁ și G₂ sunt, în cele ce urmează, specii moleculare.

Cazul F(G)

În teoria grupurilor, operația corespunzătoare se numește produs în coroană (en: wreath product).

Compunerea a două specii moleculare poate fi definită în felul următor. Spre exemplu (fără a pierde din generalitate) grupul de permutări asociat speciei Cyc₃(Ens₂) este :

1 2 3 2 3 1 3 1 2

°

a b b a

=

a1 b1 a2 b2 a3 b3 b1 a1 b2 a2 b3 a3 a2 b2 a3 b3 a1 b1 b2 a2 b3 a3 b1 a1 a3 b3 a1 b1 a2 b2 b3 a3 b1 a1 b2 a2

Ca și în cazul produsului a două specii moleculare, specia obținută prin compunere este tot moleculară, însă cardinalitatea pentru care este definită ( gradul grupului de permutări asociat) nu mai este grad₁ + grad₂ ci grad₁ × grad₂.

Cazul (F₁+F₂)(G)

În acest caz, specia compusă este multimulțimea a două specii moleculare, F₁(G) + F₂(G)

Cazul F(G₁+G₂)

Exemplu : Specia Cyc₃(Ens₂ + Lin₂), un ciclu ale cărui elemente pot fi mulțimi cu două elemente sau perechi de două elemente. Această specie are patru componente moleculare.

tip matematic	tip de specie	ordin GP	# realizări
( { x, y } { z, t } { u, v } )	Cyc3(Ens2)	24	30
( { x, y } { z, t } uv )	Ens2.Ens2.Lin2	4	180
( { x, y } zt uv )	Ens2.Lin2.Lin2	2	360
( xy zt uv )	Cyc3(Lin2)	3	240
	Cyc3(Ens2 + Lin2)		810

Scoțând din context o linie a tabelului, spre exemplu linia a doua (cea cu 180 de realizări), numărarea se poate face așa : sunt 6 variante pentru alegerea lui u, 5 variante pentru alegerea lui v, 3 variante pentru alegerea perechii lui x și încă două variante pentru stabilirea ordinii celor două mulțimi ; în total 6×5×3×2 = 180.

• O altă specie, definită pentru aceleași cardinalități, poate avea însă o altă compoziție moleculară. Spre exemplu, specia Lin₃(Ens₂ + Lin₂) are opt componente moleculare.
• Definiția formală a unei specii poate fi urmărită astfel pentru exemplul considerat :

$(F\circ G)[A]=\sum _{\pi \in P[A]}(F[\pi ]\times \Pi _{B\in \pi }G[B]).$

Mulțimea suport A are șase etichete : a, b, c, d, e și f care pot fi partiționate corespunzător (2+2+2) în 15 moduri iar suma se face pentru 15 termeni. Pentru fiecare partiție există exact 2 cicluri care pot fi definite. Pentru fiecare parte B, există 3 realizări ale lui G, de pildă { a, b } , ab și ba. În total sunt deci 15×2×3×3×3 = 810 realizări. Una din realizări ar putea fi :

( { a, b } { c, d } { e, f } ). { { a, b }, { c, d }, ef }

Etichetele e și f nu pot fi permutate cu alte etichete, deci nici { e, f } cu alte părți. Singura libertate de reetichetare rămâne a ↔ b și c ↔ d, corespunzătoare permutărilor XIIII și IIXII, care generează un grup cu 4 elemente.

• Cele două semne $\times$ și $\Pi \,$ trebuiesc înțelese mai degrabă ca un unic semn $\times \Pi$ desemnând un „produs ghidat” de către specia $F\,$. Definiția formală a compunerii speciilor este posibilă datorită echivalenței între diferite scrieri ale unor obiecte matematice. Spre exemplu, se poate scrie :

( 1 2 3 )( 4 5 ) ≈ ( 1 2 3 )( 4 5 ) . { { 1, 2, 3 }, { 4, 5 } } ≈ ( 1 2 3 )( 4 5 ) . { 1, 2, 3 } . { 4, 5 }

deoarece, ca specie, cele trei mulțimi de mai sus sunt echivalente.

• Apelând la specii multisort, F(G₁+G₂) = F(X+Y) / X=G₁, Y=G₂.
• În general, F(X+Y)= F(X) + F'(X).Y + ... + X.F'(Y) + F(Y).

Specii Multisort

Ecuația combinatorică descrie ceea ce rămâne după etichetarea unui nod, adică a unui singur nod de tip X sau nod de tip Y.

Un exemplu de specie multisort poate fi un cub, care are 26 de elemente : 8 vârfuri, 12 muchii și 6 fețe. Sunt 24 de rotații care transportă vârfuri în vârfuri, muchii în muchii și fețe în fețe. Avem așadar trei sorturi de obiecte permutate de un același grup abstract. Văzut ca grup de permutări, avem un grup de grad 26 = 8+12+6 și ordin 24, care însă nu permută ”tranzitiv” obiectele : spre exemplu, un vârf nu va fi transportat într-o muchie (sau într-o față).

Cub'(V, M, F) = V. Cyc₃ ( V².M⁴.F² ) + M. Cyc₂ ( V⁴.M⁵.F³ ) + F. Cyc₄ ( V².M³.F )

Această ecuație poate fi citită astfel :

Formulă	Citire
Cub'(V, M, F) =	Fixând un element al unui cub, acesta poate fi un vîrf
V	caz în care vîrful opus este determinat
.	iar libertatea de mișcare rămasă este descrisă de
Cyc3 (	un cilindru format din
V2.M4.F2 )	componentele rămase
+	sau poate fi o muchie
M	caz în care muchia opusă este la rândul ei fixată
.	iar libertatea de mișcare rămasă este descrisă de
Cyc2 (	un cilindru format din
V4.M5.F3 )	componentele rămase
+	sau poate fi o față
F	caz în care fața opusă este la rândul ei fixată
.	iar libertatea de mișcare rămasă este descrisă de
Cyc4 (	un cilindru format din
V2.M3.F )	componentele rămase.

Factorizând prin V = M = F (folosind un singur sort de etichete, în loc de trei) se obține ecuația cubului cum a fost descrisă într-unul din exemplele de mai sus.

Grupul stabilizator al unei specii multisort nu este tranzitiv ci are mai multe orbite - câte una pentru fiecare sort.

Particularizarea definiției functoriale

• Restrângerea definiției ”telescopice” functoriale la endo-specii. Prin aceasta, bijecțiile devin permutări iar functorialitatea exprimă o colecție (pentru orice mulțime A ) de acțiuni a grupului simetric S_A asupra mulțimii realizărilor F[A].
• Restrângerea la o anumită cardinalitate. În această etapă speciile sunt încă sume de specii moleculare, spre exemplu F[A] + F[A] + G[A] .
• Molecularizarea (restrângerea la o singură orbită a acțiunii) : o specie care nu se mai descompune în sumă de alte specii este unic asociată unei orbite a acțiunii grupului S_A pe mulțimea realizărilor F[A]. Având o singură orbită (a acțiunii), specia este descrisă în mod unic de grupul stabilizator (grup de permutări, subgrup în S_A). La acest nivel există, spre exemplu, poliedrele platonice sau specia Loto 6/49 = Ens₆.Ens₄₃.
• Restrângerea la specii atomice, care nu pot fi exprimate ca produse. Spre exemplu, Ens₂(X.X) , desenată ca O-O-O-O, este o specie atomică, are ca grup stabilizator grupul generat de permutarea (1 4)(2 3), și nu poate fi exprimată ca produs de alte specii. La acest nivel există încă specii multisort, spre exemplu Ens₂(X.X) poate fi văzută ca Ens₂(X.Y), desenată ca O-o-o-O.
• Restrângerea la specii nucleare, cum ar fi grupurile, corpurile, liniile proiective, spațiile vectoriale afine sau numerele (unul câte unul, nu toate deodată) poligonale / ciclice/ cardinale a căror stabilizator este un grup tranzitiv de permutări, având o singură orbită. Clasificarea grupurilor tranzitive de permutări este o consecință a clasificării grupurilor simple finite, rezultat acceptat actualmente, însemnând un secol de matematică în peste 200 de articole și 10.000 de pagini.

Vezi și

• Definiție combinatorică

Note

• Federico G. Lastaria, An invitation to Combinatorial Species Arhivat în 13 martie 2012, la Wayback Machine..
• Brent A. Yorgey, Species and Functors and Types, Oh My! Arhivat în 21 octombrie 2014, la Wayback Machine.
• Brent A. Yorgey, Species and Functors and Types, Oh My! video
• John C. Baez, Toby Bartels, Being an Octopus, 2004

Pentru tabele :

• Jaques Labelle, Quelques espèces sur les ensembles de petite cardinalité, Ann. Sci. Math. Québec 9 (1985), no. 1, 31-58.
• Yves Chiricota, Classification des espèces moléculaires de degré 6 et 7, Ann. Sci. Math. Québec 17 (1993), no. 1, 11-37.
• "On Transitive Permutation Groups" by J.H. Conway, A. Hulpke, and J. McKay, LMS J. Comput. Math. 1 (1998), 1-8.
• Notațiile Maple ale grupurilor tranzitive de grad ≤ 15

Seminarii și cursuri

• http://web.mac.com/xgviennot/Xavier_Viennot/cours_files/Ch3.pdf^{[nefuncțională]} 1988
• Newton Institute, 2008

Bibliografie

• Dumitriu, Anton (1977), History of logic, Tunbridge Wells, Eng.: Abacus Press 
• André Joyal, „Une théorie combinatoire des séries formelles”, Advances in Mathematics 42:1-82 (1981).
• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structures arborescentes, LaCIM, Montréal (1994). English version: Combinatorial Species and Tree-like Structures Arhivat în 2 octombrie 2006, la Wayback Machine., Cambridge University Press (1998).

Legături externe

• http://algo.inria.fr/flajolet/Publications/books.html
• Grupurile finite ca primitive ale speciei Lin Șirul A000001 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)