En matemáticas , una clase combinatoria es un conjunto contable de objetos matemáticos, junto con una función de tamaño que asigna cada objeto a un número entero no negativo, de modo que hay un número finito de objetos de cada tamaño. [1] [2]
La secuencia de conteo de una clase combinatoria es la secuencia de los números de elementos de tamaño i para i = 0, 1, 2,...; también puede describirse como una función generadora que tiene estos números como coeficientes. Las secuencias de conteo de clases combinatorias son el principal tema de estudio de la combinatoria enumerativa . Se dice que dos clases combinatorias son isomorfas si tienen el mismo número de objetos de cada tamaño, o de manera equivalente, si sus secuencias de conteo son las mismas. [3] Con frecuencia, una vez que se sabe que dos clases combinatorias son isomorfas, se busca una prueba biyectiva de esta equivalencia; Se puede interpretar que tal prueba muestra que los objetos de las dos clases isomórficas son criptomórficos entre sí.
Por ejemplo, las triangulaciones de polígonos regulares (con tamaño dado por el número de lados del polígono, y una elección fija de polígono a triangular para cada tamaño) y el conjunto de árboles planos binarios sin raíces (hasta isomorfismo gráfico , con un orden de las hojas, y con tamaño dado por el número de hojas) se cuentan con los números catalanes , por lo que forman clases combinatorias isomórficas. Un isomorfismo biyectivo en este caso viene dado por la dualidad del gráfico plano : una triangulación se puede transformar biyectivamente en un árbol con una hoja para cada borde del polígono, un nodo interno para cada triángulo y un borde para cada dos (¿bordes del polígono?) o triángulos. que están adyacentes entre sí. [4]
La teoría de las especies combinatorias y su extensión a la combinatoria analítica proporciona un lenguaje para describir muchas clases combinatorias importantes, construir nuevas clases a partir de combinaciones de otras previamente definidas y derivar automáticamente sus secuencias de conteo. [3] Por ejemplo, dos clases combinatorias pueden combinarse mediante unión disjunta o mediante una construcción de producto cartesiano en la que los objetos son pares ordenados de un objeto de cada una de las dos clases, y la función de tamaño es la suma de los tamaños de cada una. objeto en el par. Estas operaciones forman respectivamente las operaciones de suma y multiplicación de un semiring en la familia de (clases de equivalencia de isomorfismo de) clases combinatorias, en las que el objeto cero es la clase combinatoria vacía y la unidad es la clase cuyo único objeto es el conjunto vacío . [5]
En el estudio de los patrones de permutación , una clase combinatoria de clases de permutación , enumeradas por la longitud de la permutación, se denomina clase Wilf . [6] El estudio de enumeraciones de clases de permutación específicas ha revelado equivalencias inesperadas en el conteo de secuencias de clases de permutación aparentemente no relacionadas.