Especies combinatorias
From Wikipedia, the free encyclopedia
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.
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 φ.
