Introducción
En matemáticas, una función generadora o función generatriz es una serie formal de potencias cuyos coeficientes codifican información sobre una sucesión an cuyo índice corre sobre los enteros no negativos.
Hay varios tipos de funciones generadoras: funciones generadoras ordinarias, funciones generadoras exponenciales, la serie de Lambert, la serie de Bell y la serie de Dirichlet.
Las funciones generadoras son expresiones cerradas en un argumento formal x. A veces, una función generadora se «evalúa» en un valor específico x=a pero hay que tener en cuenta que las funciones generadoras son series formales de potencias, por lo que no se considera ni se analiza el problema de la convergencia en todos los valores de x.
Por lo mismo es importante observar que las funciones generadoras no son realmente funciones en en el sentido usual de ser mapeos entre un dominio y un codominio; el nombre es únicamente el resultado del desarrollo histórico de su estudio.
Planteamiento del problema
Contar, constituye un verdadero reto. No es aplicar reglas o fórmulas, es un proceso mental en el que se deben considerar cuidadosamente las relaciones entre los diversos elementos participantes. Como ocurre en algunos juegos, digamos ajedrez, conocer o saber de memoria las reglas no implica saber jugar tal juego. Es necesario ponerse a jugar para adquirir algún dominio del mismo.
Cuando se abordan problemas de conteo como paso previo para la determinación de la probabilidad de un evento, el estudiante pregunta: ¿es de permutaciones o de combinaciones? Desea una herramienta que le conteste en forma casi automática su problema. No quiere plantear cuidadosamente como se relacionan los datos o información de su problema y descubrir por sí mismo que reglas debe aplicar para lograr su respuesta.
Creemos que la función generatriz obliga al aprendiz de la mima a ser más analítico en sus planteamientos de conteo.
Función generadora ordinaria
La función generadora ordinaria de una sucesión (an) = a0, a1, a2, a3 … se define como
Es común usar la expresión función generadora sin mayor calificativo, para referirse a este tipo de función.
Es posible definir funciones generadoras sobre varias variables. Por ejemplo, la función generadora ordinaria en 2 variables de (am,n) donde n y m son índices que recorren los enteros no negativos, es
Áreas de aplicación
Entre algunos temas o áreas de aplicación de la función generadora se pueden mencionar: Procesos de ramificación, Convergencia de una sucesión de funciones de masa, procesos regenerativos, caminatas aleatorias, ruina del jugador, Problemas de ocupación, cruce de una carretera, teoría de secuencias (carreras) de éxitos, procesos de difusión, cadenas de Markov.
Ejemplo de aplicación práctica
Si cn es el número de formas en que se puede pagar n pesos usando monedas de 1, 2 y 5 pesos, entonces la función generadora de la sucesión (cn) es
ya que el coeficiente de xn es igual al número de formas de escoger a, b, c tales que
y que corresponen a usar a monedas de 1 peso, b monedas de 2 pesos y c monedas de 5 pesos.
La aplicación de la fórmula de Taylor es demasiado compleja en este caso, por lo que aplicaremos el siguiente artificio debido a Ronald Graham.
Cada uno de los denominadores (1-x), (1-x2) y (1-x5) son divisores de (1-x10), por lo que podemos reescribir
para un A(x) en donde:
Finalmente, desarrollando la función generadora
obtenemos
De la expresión anterior se puede leer con detalle el valor exacto del coeficiente de xn, es decir, el número cn de formas de pagar n pesos con monedas de 1,2 y 5 pesos. Por ejemplo, el número de formas de pagar 77 pesos se obtiene calculando el término correspondiente a x77:
y se concluye que hay 328 formas de pagar 77 pesos con monedas de 1, 2 o 5 pesos.