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.
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
Las funciones generadoras se usan para describir familias de objetos combinatorias.
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.
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.
Una secuencia generaliza la idea del par como se definió anteriormente.
Las secuencias son productos cartesianos arbitrarios de un objeto combinatorio consigo mismo.
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 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 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.
denota la familia de todos los árboles.
Entonces esta familia se puede definir recursivamente de la siguiente manera:
representa la familia de objetos que consiste en un nodo.
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:
Después de resolver para P(x):
] f(x) se refiere al coeficiente de
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)-ésimo número de Catalan.