Combinatoria enumerativa

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 las combinaciones de conteo y las permutaciones de conteo . Más generalmente, 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 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 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 de if as . En este caso, escribimos ${\ estilo de visualización g (n)}$ ${\ estilo de visualización f (n)}$ ${\ estilo de visualización f (n) / g (n) \ flecha derecha 1}$ ${\ estilo de visualización n \ flecha derecha \ infinito}$ ${\ estilo de visualización f (n) \ sim g (n). \,}$

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

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 usa a veces. En este caso tendría la forma ${\ Displaystyle f_ {n}}$ ${\ estilo de visualización x^{n}}$

Una vez determinada, la función generadora arroja la información proporcionada por los enfoques anteriores. Además, las diversas operaciones naturales sobre funciones generatrices 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.