La combinatoria enumerativa es un área de la combinatoria que se ocupa de la cantidad de formas en que se pueden formar ciertos patrones. Dos ejemplos de este tipo de problema son contar combinaciones y contar permutaciones . De manera más general, dada una colección infinita de conjuntos finitos S i indexados por los números naturales , la combinatoria enumerativa busca describir una función de conteo que cuenta el número de objetos en S n para cada n . Aunque contar el número de elementos de un conjunto es un problema matemático bastante amplio, muchos de los problemas que surgen en las aplicaciones tienen una descripción combinatoria relativamente simple . La forma de doce proporciona un marco unificado para contar permutaciones , combinaciones y particiones .
Las funciones más simples son fórmulas cerradas , que se pueden expresar como una composición de funciones elementales como factoriales , potencias, etc. Por ejemplo, como se muestra a continuación, el número de diferentes ordenaciones posibles de una baraja de n cartas es f ( n ) = n !. El problema de encontrar una fórmula cerrada se conoce como enumeración algebraica , y con frecuencia implica derivar una relación de recurrencia o función generadora y usarla para llegar a la forma cerrada deseada.
A menudo, una fórmula cerrada complicada proporciona poca información sobre el comportamiento de la función de conteo a medida que aumenta el número de objetos contados. En estos casos, puede ser preferible una aproximación asintótica simple . Una función es una aproximación asintótica a Si como . En este caso, escribimos
Funciones generadoras
Las funciones generadoras se utilizan para describir familias de objetos combinatorios. Dejardenotar la familia de objetos y sea F ( x ) su función generadora. Luego
dónde denota el número de objetos combinatorios de tamaño n . Por tanto, el número de objetos combinatorios de tamaño n viene dado por el coeficiente de. Ahora se desarrollarán algunas operaciones comunes en familias de objetos combinatorios y su efecto sobre la función generadora. La función de generación exponencial también se usa a veces. En este caso tendría la forma
Una vez determinada, la función generadora arroja la información dada por los enfoques anteriores. Además, las diversas operaciones naturales sobre funciones generadoras como la suma, la multiplicación, la diferenciación, etc., tienen un significado combinatorio; esto permite extender los resultados de un problema combinatorio para resolver otros.
Unión
Dadas dos familias combinatorias, y con funciones generadoras F ( x ) y G ( x ) respectivamente, la unión disjunta de las dos familias () tiene la función generadora F ( x ) + G ( x ).
Pares
Para dos familias combinatorias como arriba, el producto cartesiano (par) de las dos familias () tiene la función generadora F ( x ) G ( x ).
Secuencias
Una secuencia generaliza la idea del par como se definió anteriormente. Las secuencias son productos cartesianos arbitrarios de un objeto combinatorio consigo mismo. Formalmente:
Para poner lo anterior en palabras: Una secuencia vacía o una secuencia de un elemento o una secuencia de dos elementos o una secuencia de tres elementos, etc. La función generadora sería:
Estructuras combinatorias
Las operaciones anteriores ahora se pueden usar para enumerar objetos combinatorios comunes, incluidos árboles (binarios y planos), rutas y ciclos de Dyck . Una estructura combinatoria está compuesta por átomos. Por ejemplo, con árboles, los átomos serían los nodos. Los átomos que componen el objeto pueden estar etiquetados o no etiquetados. Los átomos no etiquetados son indistinguibles entre sí, mientras que los átomos etiquetados son distintos. Por lo tanto, para un objeto combinatorio que consta de átomos etiquetados, se puede formar un nuevo objeto simplemente intercambiando dos o más átomos.
Árboles binarios y plátanos
Los árboles binarios y plátanos son ejemplos de una estructura combinatoria sin etiquetar. Los árboles están formados por nodos unidos por bordes de tal manera que no hay ciclos. Generalmente hay un nodo llamado raíz, que no tiene un nodo padre. En Plane trees, cada nodo puede tener un número arbitrario de hijos. En los árboles binarios, un caso especial de los plátanos, cada nodo puede tener dos hijos o ninguno. Dejardenota la familia de todos los plátanos. Entonces esta familia se puede definir de forma recursiva de la siguiente manera:
En este caso representa la familia de objetos que consta de un nodo. Esto tiene función generadora x . Sea P ( x ) la función generadora. Poniendo la descripción anterior en palabras: un árbol plano consiste en un nodo al que se adjunta un número arbitrario de subárboles, cada uno de los cuales también es un árbol plano. Usando la operación en familias de estructuras combinatorias desarrollada anteriormente, esto se traduce en una función generadora recursiva:
Después de resolver para P ( x ):
Ahora se puede determinar una fórmula explícita para el número de plátanos de tamaño n extrayendo el coeficiente de x n .
Nota: La notación [ x n ] f ( x ) se refiere al coeficiente de x n en f ( x ). La expansión en serie de la raíz cuadrada se basa en la generalización de Newton del teorema del binomio . Para pasar de la cuarta a la quinta línea se necesitan manipulaciones utilizando el coeficiente binomial generalizado .
La expresión de la última línea es igual al ( n - 1) número catalán . Por lo tanto, p n = c n −1 .
Ver también
Referencias
- Zeilberger, Doron , combinatoria enumerativa y algebraica
- Björner, Anders y Stanley, Richard P. , A Combinatorial Miscellany
- Graham, Ronald L. , Grötschel M. y Lovász, László , eds. (1996). Manual de combinatoria , volúmenes 1 y 2. Elsevier (Holanda Septentrional), Amsterdam y MIT Press, Cambridge, Mass. ISBN 0-262-07169-X .
- Joseph, George Gheverghese (1994) [1991]. La cresta del pavo real: raíces no europeas de las matemáticas (2ª ed.). Londres: Penguin Books . ISBN 0-14-012529-9.
- Loehr, Nicholas A. (2011). Combinatoria biyectiva . Prensa CRC . ISBN 143984884X , ISBN 978-1439848845 .
- Stanley, Richard P. (1997, 1999). Combinatoria enumerativa , volúmenes 1 y 2 . Prensa de la Universidad de Cambridge . ISBN 0-521-55309-1 , ISBN 0-521-56069-1 .
- Goulden, Ian P. y Jackson, David M. (2004). Enumeración combinatoria . Publicaciones de Dover . ISBN 0486435970 .
- Análisis combinatorio - un artículo en Encyclopædia Britannica undécima edición
- Riordan, John (1958). Una introducción al análisis combinatorio , Wiley & Sons, Nueva York (republicado).
- Riordan, John (1968). Combinatorial Identities , Wiley & Sons, Nueva York (republicado).
- Wilf, Herbert S. (1994). Generatingfunctionology (2ª ed.). Boston, MA: Prensa académica. ISBN 0-12-751956-4. Zbl 0831.05001 .