Especies combinatorias

En matemáticas combinatorias , la teoría de especies combinatorias es un método abstracto y sistemático para derivar las funciones generadoras de estructuras discretas, lo que permite no simplemente contar estas estructuras sino dar pruebas biyectivas que las involucren. Ejemplos de especies combinatorias son grafos (finitos) , permutaciones , árboles , etc.; cada uno de estos tiene asociada una función generadora que cuenta cuántas estructuras hay de un determinado tamaño. Uno de los objetivos de la teoría de las especies es poder analizar estructuras complicadas describiéndolas en términos de transformaciones y combinaciones de estructuras más simples. Estas operaciones corresponden a manipulaciones equivalentes de funciones generadoras, por lo que producir dichas funciones para estructuras complicadas es mucho más fácil que con otros métodos. La teoría fue introducida, cuidadosamente elaborada y aplicada por investigadores canadienses en torno a André Joyal .

El poder de la teoría proviene de su nivel de abstracción. El "formato de descripción" de una estructura (como lista de adyacencia versus matriz de adyacencia para gráficos) es irrelevante, porque las especies son puramente algebraicas. La teoría de categorías proporciona un lenguaje útil para los conceptos que surgen aquí, pero no es necesario comprender las categorías antes de poder trabajar con especies.

La categoría de especies equivale a la categoría de secuencias simétricas en conjuntos finitos. ^[1]

Definición de especie

Ilustración esquemática de una estructura combinatoria de especies en cinco elementos mediante el uso de un diagrama de Labelle

Cualquier especie consta de estructuras combinatorias individuales construidas sobre los elementos de un conjunto finito: por ejemplo, un gráfico combinatorio es una estructura de aristas entre un conjunto dado de vértices, y un tipo de gráfico incluye todos los gráficos de todos los conjuntos finitos. Además, un miembro de una especie puede tener su conjunto subyacente reetiquetado por los elementos de cualquier otro conjunto equinumero; por ejemplo, reetiquetar los vértices de un gráfico da "la misma estructura de gráfico" en los nuevos vértices, es decir, un gráfico isomórfico .

Esto lleva a la definición formal de especie combinatoria . Sea la categoría de conjuntos finitos , siendo los morfismos de la categoría las biyecciones entre estos conjuntos. Una especie es un functor ^[2] ${\displaystyle {\mathcal {B}}}$

${\displaystyle F\colon {\mathcal {B}}\to {\mathcal {B}}.}$

Para cada conjunto finito A en , el conjunto finito F [ A ] ^{[nota 1]} se llama conjunto de F -estructuras en A , o conjunto de estructuras de especies F en A . Además, según la definición de funtor, si φ es una biyección entre los conjuntos A y B , entonces F [φ] es una biyección entre los conjuntos de F -estructuras F [ A ] y F [ B ], llamada transporte de F- estructuras a lo largo de φ . ^[3] ${\displaystyle {\mathcal {B}}}$

Por ejemplo, la "especie de permutaciones" ^[4] asigna cada conjunto finito A al conjunto S [ A ] de todas las permutaciones de A (todas las formas de ordenar A en una lista), y cada biyección f de A a otro conjunto B naturalmente induce una biyección (un reetiquetado) llevando cada permutación de A a una permutación correspondiente de B , es decir, una biyección . De manera similar, la "especie de particiones" se puede definir asignando a cada conjunto finito el conjunto de todas sus particiones , y la "especie de conjunto potencia" asigna a cada conjunto finito su conjunto potencia . El diagrama adyacente muestra una estructura (representada por un punto rojo) construida sobre un conjunto de cinco elementos distintos (representados por puntos azules); se podría construir una estructura correspondiente a partir de cinco elementos cualesquiera. ${\displaystyle S[f]:S[A]\to S[B]}$

Dos conjuntos finitos están en biyección siempre que tengan la misma cardinalidad (número de elementos); así, por definición , los conjuntos de especies correspondientes también están en biyección, y la cardinalidad (finita) de depende sólo de la cardinalidad de A. ^{[nota 2]} En particular, la serie generadora exponencial F ( x ) de una especie F se puede definir: ^[5] ${\displaystyle F[A]}$

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

¿Dónde está la cardinalidad de para cualquier conjunto A que tenga n elementos? p.ej, . ${\displaystyle \operatorname {Card} F[n]}$ ${\displaystyle F[A]}$ ${\displaystyle A=\{1,2,\dots ,n\}}$

Algunos ejemplos: escribir , ${\displaystyle f_{n}=\operatorname {Card} F[n]}$

• La especie de conjuntos (tradicionalmente llamada E , del francés " conjunto ", que significa "conjunto") es el funtor que asigna A a { A }. Entonces . _ ${\displaystyle f_{n}=1}$ ${\displaystyle E(x)=e^{x}}$
• La especie S de permutaciones , descrita anteriormente, tiene . . ${\displaystyle f_{n}=n!}$ ${\displaystyle S(x)=1/(1-x)}$
• La especie T ₂ de pares ordenados (2- tuplas ) es el functor que lleva un conjunto A a A ² . Entonces y . ${\displaystyle f_{n}=n^{2}}$ ${\displaystyle T_{2}(x)=x(x+1)e^{x}}$

Cálculo de especies

La aritmética de funciones generadoras corresponde a determinadas operaciones "naturales" sobre especies. Las operaciones básicas son suma, multiplicación, composición y diferenciación; También es necesario definir la igualdad entre especies. La teoría de categorías ya tiene una forma de describir cuándo dos functores son equivalentes: un isomorfismo natural . En este contexto, simplemente significa que para cada A hay una biyección entre F -estructuras en A y G -estructuras en A , que se "comporta bien" en su interacción con el transporte. Las especies con la misma función generadora pueden no ser isomórficas, pero las especies isomórficas siempre tienen la misma función generadora.

Suma

La suma de especies se define por la unión disjunta de conjuntos y corresponde a una elección entre estructuras. ^[6] Para las especies F y G , defina ( F + G )[ A ] como la unión disjunta (también escrita "+") de F [ A ] y G [ A ]. Se deduce que ( F  +  G )( x ) =  F ( x ) +  G ( x ). A modo de demostración, tome E ⁺ como la especie de conjuntos no vacíos, cuya función generadora es E ⁺ ( x )=  ex ⁻  1, y 1 la especie del conjunto vacío , cuya función generadora es 1 ( x )= 1. Se deduce que E  =  1  +  E ⁺ : en palabras, "un conjunto está vacío o no está vacío". Se puede leer que ecuaciones como esta se refieren a una sola estructura, así como a toda la colección de estructuras.

Multiplicación

Multiplicar especies es un poco más complicado. Es posible tomar simplemente el producto cartesiano de conjuntos como definición, pero la interpretación combinatoria de esto no es del todo correcta. (Consulte a continuación el uso de este tipo de producto). En lugar de juntar dos estructuras no relacionadas en el mismo conjunto, el operador de multiplicación usa la idea de dividir el conjunto en dos componentes, construyendo una estructura F en uno y una estructura G en uno . estructura por el otro. ^[7]

${\displaystyle (F\cdot G)[A]=\sum _{A=B+C}F[B]\times G[C].}$

Esta es una unión disjunta sobre todas las particiones binarias posibles  de A. Es sencillo demostrar que la multiplicación es asociativa y conmutativa ( hasta el isomorfismo ) y distributiva sobre la suma. En cuanto a la serie generadora, ( F  ·  G )( x ) =  F ( x ) G ( x ).

El siguiente diagrama muestra una posible estructura ( F  ·  G ) en un conjunto con cinco elementos. La estructura F (roja) recoge tres elementos del conjunto básico y la estructura G (azul claro) se lleva el resto. En otras estructuras, F y G dividirán el conjunto de forma diferente. El conjunto ( F  ·  G )[ A ], donde A es el conjunto base, es la unión disjunta de todas esas estructuras.

La suma y multiplicación de especies son la expresión más completa de las reglas de conteo de suma y producto.

Composición

La composición , también llamada sustitución, vuelve a ser más complicada. La idea básica es reemplazar componentes de F con estructuras G , formando ( F ∘ G ). ^[8] Al igual que con la multiplicación, esto se hace dividiendo el conjunto de entrada A ; los subconjuntos disjuntos se le dan a G para hacer G -estructuras, y el conjunto de subconjuntos se le da a F , para hacer la F -estructura que une las G -estructuras. Es necesario que G asigne el conjunto vacío a sí mismo para que la composición funcione. La definición formal es:

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

Aquí, P es la especie de particiones, por lo que P [ A ] es el conjunto de todas las particiones de A. Esta definición dice que un elemento de ( F  ∘  G )[ A ] está formado por una estructura F en alguna partición de A y una estructura G en cada componente de la partición. La serie generadora es . ${\displaystyle (F\circ G)(x)=F(G(x))}$

Una de esas estructuras se muestra a continuación. Tres estructuras G (azul claro) dividen la base de cinco elementos entre ellas; luego, se construye una estructura F (roja) para conectar las estructuras G.

Estas dos últimas operaciones pueden ilustrarse con el ejemplo de los árboles. Primero, defina X como la especie "singleton" cuya serie generadora es X ( x ) =  x . Entonces la especie Ar de árboles enraizados (del francés " arborescencia ") se define recursivamente por Ar  =  X  ·  E ( Ar ). Esta ecuación dice que un árbol consta de una sola raíz y un conjunto de (sub)árboles. La recursividad no necesita un caso base explícito: solo genera árboles en el contexto de su aplicación a algún conjunto finito. Una forma de pensar en esto es que el funtor Ar se aplica repetidamente a un "suministro" de elementos del conjunto; cada vez, X toma un elemento y E distribuye los demás entre los subárboles de Ar , hasta que haya no más elementos para darle a E . Esto muestra que las descripciones algebraicas de especies son bastante diferentes de las especificaciones de tipos en lenguajes de programación como Haskell .

Asimismo, la especie P se puede caracterizar como P  =  E ( E ⁺ ): "una partición es un conjunto disjunto por pares de conjuntos no vacíos (que utilizan todos los elementos del conjunto de entrada)". La serie generadora exponencial de P es , que es la serie de los números de Bell . ${\displaystyle P(x)=e^{(e^{x}-1)}}$

Diferenciación

La diferenciación de especies corresponde intuitivamente a construir "estructuras con un agujero", como se muestra en la siguiente ilustración.

Formalmente, ^[9]

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

¿ Dónde hay algún elemento nuevo distinguido que no está presente en ? ${\displaystyle \star }$ ${\displaystyle A}$

Para diferenciar la serie exponencial asociada, la secuencia de coeficientes debe desplazarse un lugar hacia la "izquierda" (perdiendo el primer término). Esto sugiere una definición de especie: F' [ A ] =  F [ A  + {*}], donde {*} es un conjunto singleton y "+" es una unión disjunta. Las partes más avanzadas de la teoría de especies utilizan ampliamente la diferenciación para construir y resolver ecuaciones diferenciales sobre especies y series. La idea de añadir (o eliminar) una sola parte de una estructura es poderosa: puede utilizarse para establecer relaciones entre especies aparentemente desconectadas.

Por ejemplo, consideremos una estructura de la especie L de órdenes lineales: listas de elementos del conjunto básico. Eliminar un elemento de una lista lo divide en dos partes (posiblemente vacías); en símbolos, esto es L'  =  L · L . La función generadora exponencial de L es L ( x ) = 1/(1 −  x ), y de hecho:

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

Las fórmulas de diferenciación generalizada se encuentran en una investigación previa de NG de Bruijn, publicada en 1964.

La especie C de permutaciones cíclicas lleva un conjunto A al conjunto de todos los ciclos en A . Eliminar un solo elemento de un ciclo lo reduce a una lista: C'  =  L . Podemos integrar la función generadora de L para producir eso para  C .

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

Un bonito ejemplo de integración de una especie es completar una recta (coordinada por un campo) con el punto infinito y obtener una recta proyectiva.

Otras operaciones

Hay una variedad de otras manipulaciones que se pueden realizar en especies. Estos son necesarios para expresar estructuras más complicadas, como grafos dirigidos o bigrafos .

Señalar selecciona un solo elemento en una estructura. ^[10] Dada una especie F , la correspondiente especie puntiaguda F ^• se define por F ^• [ A ] = A × F [ A ]. Así, cada estructura F ^• es una estructura F con un elemento distinguido. El señalar está relacionado con la diferenciación por la relación F ^• = X · F' , entonces F ^• ( x ) = x F' ( x ). La especie de conjuntos puntiagudos , E ^• , es particularmente importante como bloque de construcción para muchas de las construcciones más complejas.

El producto cartesiano de dos especies ^{[ cita necesaria ]} es una especie que puede construir dos estructuras en el mismo conjunto al mismo tiempo. Se diferencia del operador de multiplicación ordinario en que todos los elementos del conjunto base se comparten entre las dos estructuras. Una estructura ( F × G ) puede verse como una superposición de una estructura F y una estructura G. Los bigrafos podrían describirse como la superposición de un gráfico y un conjunto de árboles: cada nodo del bigrafo es parte de un gráfico y, al mismo tiempo, parte de algún árbol que describe cómo se anidan los nodos. La función generadora ( F × G )( x ) es el producto de Hadamard o coeficiente de F ( x ) y G ( x ).

Se puede considerar que la especie E ^• × E ^• realiza dos selecciones independientes del conjunto base. Los dos puntos pueden coincidir, a diferencia de X · X · E , donde se ven obligados a ser diferentes.

Como functores, las especies F y G pueden combinarse mediante composición functorial : ^{[ cita necesaria ]} (se usa el símbolo del cuadro porque el círculo ya está en uso para sustitución). Esto construye una estructura F en el conjunto de todas las estructuras G en el conjunto A. Por ejemplo, si F es el functor que lleva un conjunto a su conjunto potencia, una estructura de la especie compuesta es algún subconjunto de las G -estructuras en A. Si ahora tomamos que G es E ^• × E ^• desde arriba, obtenemos las especies de gráficos dirigidos, con bucles automáticos permitidos. (Un gráfico dirigido es un conjunto de aristas, y las aristas son pares de nodos: por lo tanto, un gráfico es un subconjunto del conjunto de pares de elementos del conjunto de nodos A ). Otras familias de gráficos, así como muchas otras estructuras, pueden definirse de esta manera. ${\displaystyle (F\,\Box \,G)[A]=F[G[A]]}$

Software

Las operaciones con especies están soportadas por SageMath ^[11] y, utilizando un paquete especial, también por Haskell . ^{[12] [13]}

Variantes

• Una especie en k tipos es un funtor . Aquí, las estructuras producidas pueden tener elementos extraídos de distintas fuentes. ^{[ cita necesaria ]} ${\displaystyle {\mathcal {B}}^{k}\rightarrow {\mathcal {B}}}$
• Un functor a , la categoría de conjuntos ponderados R para R un anillo de series de potencias , es una especie ponderada . ^{[ cita necesaria ]} ${\displaystyle {\mathcal {B}}_{R}}$

Si se reemplazan “conjuntos finitos con biyecciones” por “espacios vectoriales finitos con transformaciones lineales”, entonces se obtiene la noción de functor polinomial (después de imponer alguna condición de finitud). ^{[ cita necesaria ]}

Ver también

• Contenedor (teoría de tipos)

Notas

1. Joyal prefiere escribir para , el valor de F en A. ${\displaystyle F[A]}$ ${\displaystyle F(A)}$
2. Si es una biyección, entonces es una biyección y por tanto tiene la misma cardinalidad. ${\displaystyle u:A\to B}$ ${\displaystyle F[u]:F[A]\to F[B]}$ ${\displaystyle F[A],F[B]}$

1. Secuencia simétrica en el n Lab
2. Joyal 1981, § 1.1. Definición 1.
3. Federico G. Lastaria, Una invitación a las especies combinatorias. (2002)
4. Joyal 1981, § 1.1. Ejemplo 3.
5. Joyal 1981, § 1.1.1.
6. Joyal 1981, § 2.1.
7. Joyal 1981, § 2.1. Definición 5
8. Joyal 1981, § 2.2. Definición 7
9. Joyal 1981, § 2.3. Definición 8
10. Flajolet, Philippe ; Sedgewick, Robert (2009). Combinatoria analítica .
11. Documentación de Sage sobre especies combinatorias.
12. Especies del paquete Haskell.
13. Brent A., Yorgey (2010). "Especies, functores y tipos, ¡Dios mío!". Actas del tercer simposio de ACM Haskell sobre Haskell-Haskell '10 . ACM. págs. 147-158. CiteSeerX 10.1.1.165.6421 . doi :10.1145/1863523.1863542. ISBN  978-1-4503-0252-4. S2CID  511418.

Referencias

• Joyal, André (octubre de 1981). "Una teoría combinatoria de series formales". Avances en Matemáticas . 42 (1): 1–82. doi :10.1016/0001-8708(81)90052-9.
• Bruijn, de, NG (1964). La teoría del conteo de Pólya. En EF Beckenbach (Ed.), Matemáticas combinatorias aplicadas (págs. 144-184)
• Labelle, Jacques. Quelques espèces sur les ensembles de petite cardinalité. , Ana. Carolina del Sur. Matemáticas. Québec 9.1 (1985): 31-58.
• Etiqueta, J.; Sí, YN (1989). "La relación entre los anillos de Burnside y las especies combinatorias". Revista de teoría combinatoria . Serie A. 50 (2): 269–284. doi : 10.1016/0097-3165(89)90019-8 .
• Yves Chiricota, Clasificación de especies moleculares de grado 6 y 7 , Ann. Ciencia. Matemáticas. Québec 17 (1993), núm. 1, 11–37.
• François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire desstructures arborescentes , LaCIM, Montreal (1994). Versión en inglés: Combinatorial Species and Tree-like Structures Archivado el 2 de octubre de 2006 en Wayback Machine , Cambridge University Press (1998).
• Kerber, Adalbert (1999), Acciones aplicadas de grupos finitos, Algoritmos y combinatoria, 19 (2ª ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-65941-9 , MR 1716962, OCLC 247593131 

enlaces externos

• Weisstein, Eric W. "Especies". MundoMatemático .
• especies en el laboratorio n