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 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 sus coeficientes. Las secuencias de conteo de las 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, equivalentemente, 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; dicha prueba puede interpretarse como una demostración de que los objetos en las dos clases isomorfas son criptomórficos entre sí.
Por ejemplo, las triangulaciones de polígonos regulares (con un tamaño dado por el número de lados del polígono y una elección fija del polígono a triangular para cada tamaño) y el conjunto de árboles binarios planos sin raíz (hasta el isomorfismo de grafos , con un orden fijo de las hojas y con un tamaño dado por el número de hojas) se cuentan ambos por los números de Catalan , por lo que forman clases combinatorias isomorfas. Un isomorfismo biyectivo en este caso está dado por la dualidad de grafos planares : una triangulación se puede transformar biyectivamente en un árbol con una hoja por cada arista del polígono, un nodo interno por cada triángulo y una arista por cada dos (¿aristas de polígonos?) o triángulos que son adyacentes entre sí. [4]
La teoría de especies combinatorias y su extensión a la combinatoria analítica proporcionan un lenguaje para describir muchas clases combinatorias importantes, construir nuevas clases a partir de combinaciones de las 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 dos clases y la función de tamaño es la suma de los tamaños de cada objeto en el par. Estas operaciones forman respectivamente las operaciones de adición y multiplicación de un semiring en la familia de (clases de equivalencia de isomorfismo de) clases combinatorias, en la 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 patrones de permutación , una clase combinatoria de clases de permutación , enumeradas por longitud de 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.