Espècies combinatòries

Espècies combinatòries

En combinatòria, la teoria de espècies combinatòries és un método abstracte i sistemàtic per a analisar estructures discretes en térmens de funcions generadores. Són eixemples d'estructures discretes els grafos (finitos), les permutació, els arbres i atres similars; cada una d'elles té una funció generadora associada que conta quàntes d'estes estructures són d'un tamany donat. Un objectiu de la teoria d'espècies combinatòries és poder analisar estructures complexes en térmens de transformacions i combinacions d'estructures més senzilles. Estes transformacions corresponen a manipulacions equivalents de funcions generadores, de manera que la teoria facilita calcular les funcions associades a estructures complexes. La teoria d'espècies combinatòries va ser introduïda per André Joyal.

El poder d'esta teoria prové el seu alt nivell d'abstracció. La forma específica en la que es descriu una estructura (llestes de adyacencia front a matrius de adyacencia) és irrellevant perque les espècies són purament algebraiques. La teoria de categories proporciona un llenguage útil per a tractar els conceptes de la teoria, pero no és necessari d'entendre categories per a treballar en espècies.

Definició

Siga $ℬ$ la categoria dels conjunts finitos en les biyecciones entre ells com morfismos. Una espècie combinatòria és un funtor

$F:ℬ\to ℬ;$

que donat un conjunt A, torna el conjunt F[A] de F-estructures en A. El funtor opera ademés sobre els morfismos, que són les biyecciones en este cas. Si φ és una biyección entre els conjunts A i B, es té que F[φ] és una biyección entre els conjunts de F-estructures F[A] i F[B], i es diu que és la funció que transporta de F-estructures sobre φ.

Software

SageMath implementa operacions en espècies. El llenguage de programació Haskell oferix llibreries específiques.

Referències

• André Joyal, Unix théorie combinatoire dones séries formelles, Advances in Mathematics 42:1–82 (1981).
• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie dones espèces et combinatoire dones structures arborescentes, LaCIM, Montréal (1994). English version: Combinatorial Species and Tree-like Structures [1] archivat en Wayback Machine., Cambridge University Press (1998).
• François Bergeron, Species and Variations on the Theme of Species, invited talk at Category Theory and Computer Science '04, Copenhague (2004). Slides (pdf).
• Marcelo Aguiar, Swapneel Mahajan, Monoidal functors, species and Hopf algebras, CRM Monograph Séries Volume 29. A co-publication of the AMS and Centre de Recherches Mathématiques. Expected publication dona't is November 19, 2010. pdf
• Federico G. Lastaria, An invitation to Combinatorial Species [2] archivat en Wayback Machine..
• Yves Chiricota, "Classification dones espèces moléculaires de degré 6 et 7", Ann. Sci. Math. Québec 17 (1993), no. 1, 1 l–37.