El objetivo de este artículo es presentar trucos comunes del oficio en su contexto, de manera que el lector pueda incorporarlos a sus conocimientos.
A partir de la relación de recurrencia, vemos, por lo tanto, que la serie de potencias xf + x2f concuerda con f excepto en los dos primeros coeficientes: Teniendo en cuenta éstos, hallamos que (Este es el paso crucial; las relaciones recurrentes casi siempre pueden traducirse a ecuaciones para las funciones generatrices.)
El ejemplo que estudiaremos concierne a un grafo no dirigido
Las aristas existen entre las palabras adyacentes, pero solo si difieren exactamente en una posición.
ofrecen los vecinos de una letra particular que se presenta en una posición
son tales que la adyacencia siempre funciona en ambos sentidos, esto es, si
La cuestión que tratamos de responder es: ¿cuántas aristas contiene este grafo?
se puede calcular explícitamente, dando una fórmula sencilla y útil.
, y consideremos las palabras (vértices) que consisten en dos letras, es decir,
es dado por La función generadora se convierte en Extrayendo la diferenciación, hallamos la siguiente expresión para
De hecho, estas aristas son El resultado encaja con lo que obtenemos sustituyendo en la fórmula.
La fórmula simplificada se convierte en Supóngase, por ejemplo, que todas las letras son adyacentes a las que difieren en una unidad de su valor numérico, independiente de su posición.
Las funciones generatrices ordinarias no se limitan a representar sucesiones que dependen únicamente de un solo parámetro.
Aquí se muestra un ejemplo de cómo trabajar con funciones generadoras en dos variables.
Sea n un número natural y consideremos los enteros desde
Emplearemos funciones generadoras en dos variables para responder la siguiente cuestión: ¿cuál es la suma de los enteros en
Ciertamente es imposible calcular esta suma por enumeración directa para grandes
es dado por Ahora introducimos las dos siguientes funciones generatrices en dos variables: (Se requiere que
También se requieren dos funciones auxiliares para mantener la notación sencilla: Ahora, por la definición de
, faltará en la suma de la izquierda, así que lo calculamos y lo añadimos.
Tenemos Añadiendo todo, hallamos que de donde o bien lo cual es una simple función generatriz racional.
Recordemos nuestra fórmula inicial, que podemos reescribir como Ahora podemos calcular el
, que sin embargo no es tan receptiva al cálculo simbólico como la forma previa, se puede obtener extendiendo la serie geométrica en la descomposición en fracciones parciales de
Por supuesto, es enteramente posible preañadir r a esos contribuyentes, lo que resulta en la recurrencia alternativa Sumando como antes, hallamos Resolver esto para
Tenemos De ahí Este también es el valor correcto, ya que Material adicional en relación con este ejemplo, así como una instantánea de cómo se desarrolló, puede encontrarse en los «Enlaces externos«.
Específicamente tenermos las letras I, V y X con los valores 1, 5 y 10, cualquier sucesión de los cuales se considera un número cuyo valor es la suma de las cifras individuales.
En otras palabras, tenemos un alfabeto y consideramos los elementos de
Empleamos la siguiente función generatriz ordinaria para responder la pregunta: donde el monomio
Por definición, tenemos Sumando la recurrencia con n hallamos lo que da la siguiente ecuación para
Razonando con más cuidado, vemos que una palabra de peso n contiene como promedio