Combinatoria enumerativa

La combinatoria enumerativa es un área de la combinatoria que trata de la cantidad de maneras 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 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 Sn 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.

Las funciones más simples son las fórmulas cerradas, que se pueden expresar  como una composición de funciones elementales como factoriales, potencia, etc. Por ejemplo, como se muestra a continuación, el número de diferentes ordenamientos posibles de un mazo 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 usar esto 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, una aproximación asintótica simple puede ser preferible. Una función g(n) es una aproximación asintótica a ${displaystyle f(n)}$  si ${displaystyle f(n)/g(n) ightarrow 1}$. En este caso escribimos ${displaystyle n ightarrow infty }$.

Las funciones generadoras se usan para describir familias de objetos combinatorias. F denota la familia de objetos y F(x) es su función generadora. Entonces:

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

dónde ${displaystyle f_{n}}$ denota la cantidad de objetos combinatorios de tamaño n. Por lo tanto, el número de objetos combinatorios de tamaño n está dado por el coeficiente de ${displaystyle x^{n}}$. Se desarrollará ahora una operación común 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

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

Una vez determinado, la función generadora proporciona la información dada por los enfoques anteriores. Además, las diversas operaciones naturales en las funciones de generación tales como la suma, la multiplicación, la diferenciación, etc., tienen una importancia combinatoria, esto permite extender los resultados de un problema combinatorio para resolver otros.

Dadas dos familias combinatorias,${displaystyle {mathcal {F}}}$ y ${displaystyle {mathcal {G}}}$ con funciones generadoras F(x) y G(x) respectivamente, la unión disjunta de las dos familias,

(${displaystyle {mathcal {F}}cup {mathcal {G}}}$) tiene la función generadora F(x) + G(x).

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

Una secuencia generaliza la idea del par 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}} imes {mathcal {F}} cup {mathcal {F}} imes {mathcal {F}} imes {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)}}}$

Las operaciones anteriores ahora se pueden usar para enumerar objetos combinatorios comunes, incluidos árboles (binarios y planos), caminos Dyck y ciclos. Una estructura combinatoria está compuesta de átomos. Por ejemplo, con árboles, los átomos serías 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 marcados son distintos. Por lo tanto, para un objeto combinatorio que consiste en átomos etiquetados, se puede formar un nuevo objeto simplemente intercambiando dos o más átomos.

Los árboles son ejemplos de una estructura combinatoria no etiquetada. Los árboles consisten en nodos unidos por aristas de tal manera que no hay ciclos. En general, hay un nodo llamado raíz, que no tiene nodo primario. En los árboles,cada nodo puede tener un número arbitrario de hijos. En los árboles binarios, un caso especial es que cada nodo puede tener dos o ningún hijo.${displaystyle {mathcal {P}}}$ denota la familia de todos los árboles. Entonces esta familia se puede definir recursivamente de la siguiente manera:

${displaystyle {mathcal {P}}={ullet } imes {mbox{Seq}}({mathcal {P}})}$

En este caso ${displaystyle {ullet }}$ representa la familia de objetos que consiste en un nodo. Esto tiene la función generadora x. P(x) denota la función generadora ${displaystyle {mathcal {P}}}$ . Poniendo la descripción anterior en palabras: Un árbol consiste en un nodo al cual está unido un número arbitrario de subárboles, cada uno de los cuales es también un árbol. Al utilizar la operación en familias de estructuras combinatorias desarrolladas anteriormente, esto se traduce en una función de generación recursiva:

${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 la cantidad de árboles planos de tamaño n extrayendo el coeficiente de ${displaystyle x^{n}}$.

${displaystyle {egin{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 [${displaystyle x^{n}}$] f(x) se refiere al coeficiente de ${displaystyle 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 binomial. Para llegar desde la cuarta a quinta línea, se necesitan manipulaciones que utilicen el coeficiente binomial generalizado.

La expresión en la última línea es igual al (n-1) Números de Catalan. Por lo tanto, pn = cn - 1.