Combinatoria enumerativa

Área de combinatoria que se ocupa de la cantidad de formas en que se pueden formar ciertos patrones.

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 problemas son contar combinaciones y contar permutaciones . De manera más general, dada una colección infinita de conjuntos finitos Si 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 doce proporciona un marco unificado para contar permutaciones , combinaciones y particiones .

Las funciones más simples son las fórmulas cerradas , que pueden expresarse como una composición de funciones elementales como factoriales , potencias , etc. Por ejemplo, como se muestra a continuación, el número de diferentes ordenamientos 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 crece 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 if as . 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. Denotemos la familia de objetos y sea F ( x ) su función generadora. Entonces ${\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 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. A veces también se utiliza la función generadora exponencial . 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 produce la información proporcionada por los enfoques anteriores. Además, las diversas operaciones naturales sobre funciones generadoras como suma, multiplicación, diferenciación , etc., tienen un significado combinatorio; esto permite ampliar 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 la función generadora F ( x ) G ( x ). ${\displaystyle {\mathcal {F}}\times {\mathcal {G}}}$

Secuencias

Una secuencia (finita) generaliza la idea del par como se define 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 ahora se pueden utilizar para enumerar objetos combinatorios comunes, incluidos árboles ( binario y plano), trayectorias y ciclos de Dyck. Una estructura combinatoria está compuesta de átomos. Por ejemplo, en los árboles los átomos serían los nodos. Los átomos que componen el objeto pueden estar etiquetados o no. 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 constan de 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 plátanos, 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 ningún hijo. Denotemos la familia de todos los plátanos. 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. Esto tiene función generadora x . Sea P ( x ) la función generadora . Poniendo la descripción anterior en palabras: un árbol plano consta de un nodo al que está unido un número arbitrario de subárboles, cada uno de los cuales también es un árbol plano. Usando 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 ). El desarrollo en serie de la raíz cuadrada se basa en la generalización del teorema del binomio de Newton . 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) ^primer número catalán . Por lo tanto, p _n = c _{n −1} .

Ver también

• combinatoria algebraica
• Combinatoria asintótica
• Lema de Burnside
• Explosión combinatoria
• Teoría de juegos combinatoria
• 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 .
• José, 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, Nicolás A. (2011). Combinatoria biyectiva. Prensa CRC. 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. Publicaciones de Dover . ISBN 0486435970 . 
• Riordan, John (1958). Introducción al análisis combinatorio , Wiley & Sons, Nueva York (reeditado).
• Riordan, John (1968). Identidades combinatorias , Wiley & Sons, Nueva York (reeditado).
• Wilf, Herbert S. (1994). Funcionalidad generadora (2ª ed.). Boston, MA: Prensa académica. ISBN 0-12-751956-4. Zbl  0831.05001.