Combinatoria enumerativa

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 problema son el conteo de combinaciones y el conteo de 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. El método de doce partes proporciona un marco unificado para contar permutaciones , combinaciones y particiones .

Las funciones más simples de este tipo son 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 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 función generadora y utilizarla para llegar a la fórmula 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 $g(n)$ es una aproximación asintótica a $f(n)$ si $f(n)/g(n)\rightarrow 1$ como $n\rightarrow \infty$ En este caso, escribimos. $f(n)\sim g(n).\,$

Funciones generadoras

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

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

dónde $f_{n}$ 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 $x^{n}$ A continuación se desarrollarán algunas operaciones comunes sobre familias de objetos combinatorios y su efecto en la función generadora. También se utiliza a veces la función generadora exponencial . En este caso tendría la forma

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

Una vez determinada, la función generadora proporciona la información obtenida mediante los métodos 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, ${\mathcal {F}}$ y ${\mathcal {G}}$ con funciones generadoras F ( x ) y G ( x ) respectivamente, la unión disjunta de las dos familias ( ${\mathcal {F}}\cup {\mathcal {G}}$ ) tiene función generadora F ( x ) + G ( x ).

Pares

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

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:

{\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 expresar lo anterior con palabras: Una secuencia vacía, una secuencia de un elemento, una secuencia de dos elementos, una secuencia de tres elementos, etc. La función generadora sería:

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

Estructuras combinatorias

Las operaciones anteriores ahora se pueden usar para enumerar objetos combinatorios comunes, incluyendo árboles ( binarios y planos), caminos de Dyck y ciclos. 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 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 planos son ejemplos de una estructura combinatoria sin etiquetar. Los árboles constan de nodos unidos por aristas de tal manera que no existen ciclos . Generalmente hay un nodo llamado raíz, que no tiene 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. ${\mathcal {P}}$ Denotemos por la familia de todos los árboles planos. Entonces, esta familia se puede definir recursivamente de la siguiente manera:

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

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

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

Después de resolver para P ( x ):

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

Ahora se puede determinar una fórmula explícita para el número de árboles planos de tamaño n extrayendo el coeficiente de x ⁿ :

{\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) ^-ésimonúmero de Catalan . Por lo tanto, p _n = c _n₋₁ .

Véase también

Referencias

↑ (secuencia A003763 en el OEIS )
↑ (secuencia A209077 en el OEIS )

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 Septentrional), Á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). Una 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). Generatingfunctionology (2.ª ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001 .

[1] (secuencia A003763 en el OEIS )

[2] (secuencia A209077 en el OEIS )

[ 1 ]

[ 2 ]