Combinatoria enumerativa

Área de la combinatoria que se ocupa del número de formas en que se pueden formar ciertos patrones.

La combinatoria enumerativa es un área de la combinatoria que se ocupa del número de formas en que se pueden formar ciertos patrones. Dos ejemplos de este tipo de problemas 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 cuente el número de objetos en S _n para cada n . Aunque contar el número de elementos en 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 doce veces proporciona un marco unificado para contar permutaciones , combinaciones y particiones .

Las funciones más simples son las 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, la cantidad de posibles ordenaciones diferentes 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 una 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 ${\displaystyle g(n)}$ ${\displaystyle f(n)}$ ${\displaystyle f(n)/g(n)\rightarrow 1}$ ${\displaystyle n\rightarrow \infty }$ ${\displaystyle f(n)\sim g(n).\,}$

Funciones generadoras

Las funciones generadoras se utilizan para describir familias de objetos combinatorios. Sea F ( x ) la familia de objetos y su función generadora. ${\displaystyle {\mathcal {F}}}$

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}}$

donde denota el número de objetos combinatorios de tamaño n . Por lo tanto, el número de objetos combinatorios de tamaño n viene dado por el coeficiente de . A continuación se desarrollarán algunas operaciones comunes sobre familias de objetos combinatorios y su efecto sobre la función generadora. La función generadora exponencial también se utiliza a veces. En este caso, tendría la forma ${\displaystyle f_{n}}$ ${\displaystyle x^{n}}$

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}}$

Una vez determinada, la función generadora proporciona la información proporcionada por los enfoques anteriores. Además, las diversas operaciones naturales sobre funciones generadoras, como la adición, 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 función generadora F ( x ) + G ( x ). ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {F}}\cup {\mathcal {G}}}$

Pares

Para dos familias combinatorias como las anteriores, el producto cartesiano (par) de las dos familias ( ) tiene función generadora F ( x ) G ( x ). ${\displaystyle {\mathcal {F}}\times {\mathcal {G}}}$

Secuencias

Una secuencia (finita) generaliza la idea del par tal como se definió anteriormente. Las secuencias son productos cartesianos arbitrarios de un objeto combinatorio consigo mismo. Formalmente:

${\displaystyle {\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \ {\mathcal {F}}\!\times \!{\mathcal {F}}\!\times \!{\mathcal {F}}\ \cup \cdots }$

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:

${\displaystyle 1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}.}$

Estructuras combinatorias

Las operaciones anteriores se pueden utilizar ahora para enumerar objetos combinatorios comunes, incluidos árboles ( binarios y planos), caminos de Dyck y ciclos. Una estructura combinatoria está compuesta de á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 planos

Los árboles binarios y los árboles planos son ejemplos de una estructura combinatoria sin etiquetar. Los árboles están formados por nodos unidos por aristas de tal manera que no hay ciclos . Generalmente hay un nodo llamado raíz, que no tiene un nodo padre. En los árboles planos, cada nodo puede tener un número arbitrario de hijos. En los árboles binarios, un caso especial de árboles planos, cada nodo puede tener dos hijos o ninguno. Sea la familia de todos los árboles planos. Entonces, esta familia se puede definir recursivamente de la siguiente manera: ${\displaystyle {\mathcal {P}}}$

${\displaystyle {\mathcal {P}}=\{\bullet \}\times \,{\mbox{Seq}}({\mathcal {P}})}$

En este caso representa la familia de objetos que consta de un nodo. Este tiene una función generadora x . Sea P ( x ) la función generadora . Expresando la descripción anterior en palabras: Un árbol plano consta de un nodo al que se adjunta un número arbitrario de subárboles, cada uno de los cuales es también un árbol plano. Utilizando la operación sobre familias de estructuras combinatorias desarrollada anteriormente, esto se traduce en una función generadora recursiva: ${\displaystyle \{\bullet \}}$ ${\displaystyle {\mathcal {P}}}$

${\displaystyle P(x)=x\,{\frac {1}{1-P(x)}}}$

Después de resolver para P ( x ):

${\displaystyle P(x)={\frac {1-{\sqrt {1-4x}}}{2}}}$

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 ⁿ :

${\displaystyle {\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}}$

Nota: La notación [ x ⁿ ] f ( x ) se refiere al coeficiente de x ⁿ en f ( x ). La expansión en serie de la raíz cuadrada se basa en la generalización de Newton del teorema binomial . 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 de Catalan . Por lo tanto, p _n = c _{n −1} .

Véase también

• Combinatoria algebraica
• Combinatoria asintótica
• Lema de Burnside
• Explosión combinatoria
• Teoría de juegos combinatorios
• Principios combinatorios
• Especies combinatorias
• Principio de inclusión-exclusión
• Método de elemento distinguido
• Teorema de enumeración de Pólya
• Teoría del tamiz

Referencias

• Zeilberger, Doron , Combinatoria enumerativa y algebraica
• Björner, Anders y Stanley, Richard P. , Una miscelánea combinatoria
• Graham, Ronald L. , Grötschel M. y Lovász, László , eds. (1996). Manual de combinatoria , volúmenes 1 y 2. Elsevier (Holanda del Norte), Ámsterdam 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. CRC Press. ISBN 143984884X , ISBN 978-1439848845 .  
• Stanley, Richard P. (1997, 1999). Combinatoria enumerativa, volúmenes 1 y 2. Cambridge University Press . ISBN 0-521-55309-1 , ISBN 0-521-56069-1 .  
• Goulden, Ian P. y Jackson, David M. (2004). Enumeración combinatoria. Dover Publications . ISBN 0486435970 . 
• Riordan, John (1958). 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). Función generadora (2.ª ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4.Zbl 0831.05001  .