Clase combinatoria
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 una cantidad finita de objetos de cada tamaño.[1][2]
Conteo de secuencias e isomorfismo
[editar]La secuencia de conteo de una clase combinatoria es la secuencia del número 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 isomórficas 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 isomórficas, se busca una prueba biyectiva de esta equivalencia; una prueba de este tipo puede interpretarse en el sentido de que los objetos de 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 de polígono a triangular para cada tamaño) y el conjunto de árboles planos binarios sin raíz (hasta el isomorfismo del gráfico, con un el orden de las hojas, y con el 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 viene dado por la dualidad gráfica plana: una triangulación se puede transformar biyectivamente en un árbol con una hoja para cada borde de polígono, un nodo interno para cada triángulo y un borde para cada dos bordes de polígono o triángulos adyacentes. el uno al otro.[4]
Combinatoria analítica
[editar]La teoría de las 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 por unión disjunta, o por 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 suma y multiplicación de un semianillo 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]
Patrones de permutación
[editar]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 recuento de secuencias de clases de permutación aparentemente no relacionadas.
Referencias
[editar]- ↑ Martínez, Conrado; Molinero, Xavier (2001), «A generic approach for the unranking of labeled combinatorial classes», Random Structures & Algorithms 19 (3-4): 472-497, MR 1871563, doi:10.1002/rsa.10025..
- ↑ Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles (2004), «Boltzmann samplers for the random generation of combinatorial structures», Combinatorics, Probability and Computing 13 (4-5): 577-625, MR 2095975, doi:10.1017/S0963548304006315..
- ↑ a b Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, Definition I.3, p.19, ISBN 9781139477161..
- ↑ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics 25, Springer, Theorem 1.1.3, pp. 4–6, ISBN 9783642129711..
- ↑ Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579..
- ↑ Steingrímsson, Einar (2013), «Some open problems on permutation patterns», Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser. 409, Cambridge Univ. Press, Cambridge, pp. 239-263, MR 3156932.
Enlaces externos
[editar]Esta obra contiene una traducción derivada de «Combinatorial Class» de la Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.
| Control de autoridades |
|
|---|
Datos: Q5150823