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)\rightarrow 1}$. En este caso escribimos ${\displaystyle n\rightarrow \infty }$.