Especies combinatorias
En combinatoria, la teoría de especies combinatorias es un método abstracto y sistemático para analizar estructuras discretas en términos de funciones generadoras. Son ejemplos de estructuras discretas los grafos (finitos), las permutaciones, los árboles y otras similares; cada una de ellas tiene una función generadora asociada que cuenta cuántas de estas estructuras son de un tamaño dado. Un objetivo de la teoría de especies combinatorias es poder analizar estructuras complejas en términos de transformaciones y combinaciones de estructuras más sencillas. Estas transformaciones corresponden a manipulaciones equivalentes de funciones generadoras, de forma que la teoría facilita calcular las funciones asociadas a estructuras complejas. La teoría de especies combinatorias fue introducida por André Joyal.
El poder de esta teoría proviene su alto nivel de abstracción. La forma específica en la que se describe una estructura (listas de adyacencia frente a matrices de adyacencia) es irrelevante porque las especies son puramente algebraicas. La teoría de categorías proporciona un lenguaje útil para tratar los conceptos de la teoría, pero no es necesario de entender categorías para trabajar con especies.
Definición
Sea la categoría de los conjuntos finitos con las biyecciones entre ellos como morfismos. Una especie combinatoria es un funtor
que dado un conjunto A, devuelve el conjunto F[A] de F-estructuras en A. El funtor opera además sobre los morfismos, que son las biyecciones en este caso. Si φ es una biyección entre los conjuntos A y B, se tiene que F[φ] es una biyección entre los conjuntos de F-estructuras F[A] y F[B], y se dice que es la función que transporta de F-estructuras sobre φ.
Software
SageMath[1] implementa operaciones con especies. El lenguaje de programación Haskell ofrece librerías específicas.[2][3]
Notas
- Sage documentation on combinatorial species.
- Haskell package species.
- Brent A., Yorgey (2010). Species and functors and types, oh my!. ACM. pp. 147-158. ISBN 978-1-4503-0252-4. doi:10.1145/1863523.1863542.
Referencias
- 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, Cambridge University Press (1998).
- François Bergeron, Species and Variations on the Theme of Species, invited talk at , Copenhague (2004). .
- Marcelo Aguiar, Swapneel Mahajan, Monoidal functors, species and Hopf algebras, CRM Monograph Series Volume 29. A co-publication of the AMS and Centre de Recherches Mathématiques. Expected publication date is November 19, 2010.
- Federico G. Lastaria, An invitation to Combinatorial Species.
- Yves Chiricota, "Classification des espèces moléculaires de degré 6 et 7", Ann. Sci. Math. Québec 17 (1993), no. 1, 1 l–37.