Ejemplos de funciones generadoras

Los siguientes ejemplos de funciones generatrices se presentan siguiendo el espíritu de George Pólya, que abogaba por el aprendizaje de la matemática haciendo y repasando tantos ejemplos y pruebas como fuese posible. 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.


Ejemplo resuelto A: básico editar

Se pueden crear nuevas funciones generadoras expandiendo otras funciones generadoras más simples. Por ejemplo, comenzando con:

 

y sustituyendo   por  , obtenemos:

 

Ejemplo resuelto B: números de Fibonacci editar

Consideremos el problema de hallar una fórmula cerrada para los números de Fibonacci Fn definidos por F0 = 0, F1 = 1, y Fn = Fn−1 + Fn−2 para n ≥ 2. Formamos la función generatriz ordinaria

 

para esta sucesión. La función generatriz para la sucesión (Fn−1) es xf y la de (Fn−2) es x2f. 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.) Resolviendo esta ecuación para f, obtenemos

 

El denominador puede factorizarse utilizando la proporción áurea φ1 = (1 + √5)/2 y φ2 = (1 − √5)/2, y la técnica de descomposición en fracciones parciales nos da:

 

Estas dos series formales de potencias se conocen expresamente porque son series geométricas; comparando coeficientes, hallamos la fórmula explícita

 

Ejemplo resuelto C: aristas en un grafo no orientado editar

El foco de este ejemplo es el uso de las funciones generatriz en muchas variables para alcanzar la meta de clasificar los elementos   de un conjunto   de acuerdo con muchos parámetros   a través de la correspondencia  . Aquí las variables de la función generadora son   y la función generadora   es

 

de modo que el número   de elementos de   que corresponden a la tupla de parámetros   es dado por

 

donde hemos usado el operador de extracción de coeficientes para la serie formal de potencias.

El ejemplo que estudiaremos concierne a un grafo no dirigido   cuyos vértices   corresponden a palabras de longitud   a partir de un alfabeto   que contiene exactamente   letras, es decir:

 

En lo que sigue, utilizaremos los números de   a   en lugar de las letras, para mantener una notación sencilla.

Además, nos dan un conjunto de funciones   que determinan cuál de los vértices posibles   aparecen en el grafo, y cuáles son las aristas. De modo más preciso,   especifica un conjunto de posibles sustitutos para  , si se presenta en una posición  . En ese caso,   puede cambiarse por cualquier letra que se presente en  , dando una palabra adyacente, esto es, un vértice. Las aristas existen entre las palabras adyacentes, pero solo si difieren exactamente en una posición. Hablando intuitivamente, los   ofrecen los vecinos de una letra particular que se presenta en una posición  , y los vecinos de una palabra son las palabras que pueden obtenerse seleccionando una posición y reemplazando la letra   en esa posición por uno de sus vecinos, es decir, un elemento de  . Queda garantizado que los   son tales que la adyacencia siempre funciona en ambos sentidos, esto es, si  , entonces  . Las palabras que contienen letras en posiciones en las que no tienen vecinos, es decir, en las que  , se omiten en el conjunto de vértices. La cuestión que tratamos de responder es: ¿cuántas aristas contiene este grafo?

El conjunto cuyos elementos tratamos de enumerar y clasificar aquí es el conjunto de vértices  , y tenemos que clasificar los vértices   de acuerdo con el número de letras que tienen   vecinos, de modo que

 

siendo   el número de letras que tienen un vecino en su posición,   el número de letras que tienen dos vecinos en su posición, etc., porque entonces el número de aristas que se originan en   es dado por

 

Esto se debe a que   indica la presencia de  letras que tienen   vecinos en  , que aportan   aristas, pero

 

Este proceso contará las aristas dos veces (una vez en cada extremo), dando finalmente la fórmula para el número   de aristas

 

Falta por hallar  . Con esto en mente, introducimos las cantidades  , el número de letras de una posición   que tienen   vecinos, esto es,

 

También nos hará falta  , el número de letras que de hecho se presentan en la posición  , es decir,

 

(Recuérdese que todas las letras que no tienen vecinos no contribuyen al conjunto de vértices posibles.)

Entonces, la función generatriz   es dada por

 

Calcular la respuesta editar

Es así que   se puede calcular explícitamente, dando una fórmula sencilla y útil. Este cálculo se basa en la observación de que

 

equivale a

 

que se simplifica como

 

y resulta

 

Un ejemplo sencillo editar

Tomemos  , de modo que  , y consideremos las palabras (vértices) que consisten en dos letras, es decir,  . El conjunto de funciones vecinas   es dado por

 

La función generadora se convierte en

 

Extrayendo la diferenciación, hallamos la siguiente expresión para  :

 

o bien

 

así que podemos esperar siete aristas.

De hecho, estas aristas son

 

El resultado encaja con lo que obtenemos sustituyendo en la fórmula. Tenemos   y  , y   y   lo que da

 

Caso especial editar

Hay un caso especial importante que ofrece una fórmula más sencilla para  . Este es el caso de cuando no hay letras «inertes», es decir, cuando todas las letras tienen vecinos o bien   en todas las posiciones, lo que implica que   para todo  . 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. De ahí que haya dos letras que tienen un vecino (a saber,   y  ), y las demás letras tienen dos vecinos. De la sustitución resulta entonces

 

Este ejemplo se ha tomado de Les-Mathematiques.net. Algunas variaciones de este problema, incluyendo una considerable cantidad de material adicional, pueden encontrarse en los «Enlaces externos».

Ejemplo resuelto D: funciones generatriz en dos variables y sumas de los dígitos editar

Las funciones generatrices ordinarias no se limitan a representar sucesiones que dependen únicamente de un solo parámetro. Son posibles más parámetros, dos o más, como se ha visto en el ejemplo previo. También es posible mezclar tipos de funciones generadoras, por ejemplo funciones generatrices de probabilidad en dos variables, donde una función generadora ordinaria genera una exponencial. A menudo se denomina a estos tipos de funciones generadoras «superfunciones generadoras». 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   a  , donde esos enteros que tienen menos de   dígitos se completan con ceros a la izquierda, de forma que de todos ellos pueda considerarse que tienen   dígitos. Por ejemplo, para   el abanico va desde   hasta  . Emplearemos funciones generadoras en dos variables para responder la siguiente cuestión: ¿cuál es la suma de los enteros en   cuyos primeros n dígitos suman el mismo valor que los últimos n dígitos, esto es, la suma de los dígitos de la primera mitad de los cuales es igual a la suma de los dígitos de la segunda mitad? A estos enteros los llamamos equilibrados. Por ejemplo, el entero 124511 sería parte de la suma con  , ya que 1+2+4=7=5+1+1. El valor que aportaría es sencillamente 124511. Ciertamente es imposible calcular esta suma por enumeración directa para grandes   (tómese  , por ejemplo).

Sea   la denotación de la suma deseada, e introdúzcase  , que da el número de enteros n cifras de largo (completándolos con ceros como antes, para obtener   valores) cuyas cifras suman k, y  , que es la suma de los enteros n cifras de largo cuyas cifras suman k. La observación clave aquí es darse cuenta de que

 

Para ver esto, establézcase k, la suma de los dígitos, y considérese el conjunto de enteros equilibrados de longitud  , la suma de los dígitos de la primera y la segunda mitad de los cuales es k. Este conjunto de enteros se crea emparejando cualquier entero de longitud n y suma de los dígitos k con cualquier otro, de modo que se presenta cualquier valor particular   veces en la primera mitad (multiplicado por  ), y   veces en la segunda mitad. Añadiendo todos estos enteros, resulta   El número de sumandos que contribuyen a   es dado por

 

Ahora introducimos las dos siguientes funciones generatrices en dos variables:

 

(Se requiere que   y   para  , porque   es la suma de los dígitos máxima posible.) También se requieren dos funciones auxiliares para mantener la notación sencilla:

 

Ahora, por la definición de  , se sigue inmediatamente que

 

Esto se debe a que los términos de   representan el proceso de escoger un dígito decimal para la primera posición de la izquierda, uno para la segunda, y así sucesivamente. Los exponentes se añaden de forma que el término   se presente cada vez que los dígitos suman k.

La siguiente observación clave es que para  ,

 

Esto quiere decir sencillamente que los enteros que contribuyen a   se pueden obtener a partir de los que contribuyen a  , donde r es un dígito decimal, moviendo los últimos una posición a la izquierda (multiplicación por diez) y añadiendo r (recuérdese que hay   enteros que contribuyen a  )

Ahora nos disponemos a reconstituir   sumando la recurrencia de arriba con  . El término para  , esto es,  , faltará en la suma de la izquierda, así que lo calculamos y lo añadimos. (En lo que sigue utilizaremos el operador de extracción de coeficientes para la serie de potencias formales.) 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  , ya que tenemos formas cerradas para   y   Esto nos da la siguiente tabla para   y  :

    1 495
    2 3349665
    3 27625972374
    4 240801497591985
    5 2162288199783771180
    . ...
   17 1185633898500558643116053969483499881436610149944135688394603051650
   18 11525195623906119101843912373578899988474804376093880898156087626421100
   19 112203312767859412537217211281711779998877966872321405874627827887182882200
   20 1093844474149520613133628019194480743399890615552585047938686637198080551925660.

Fórmula explícita alternativa editar

Una fórmula explícita para  , 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   y empleando la simetría de   para observar que

 

lo cual nos da

 

Pero

 

de modo que

 

Recurrencia alternativa editar

El lector sagaz habrá observado que obtuvimos la recurrencia para   añadiendo el dígito r a uno de los contribuyentes 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   produce, como esperábamos, la misma solución que antes:

 

Verificación editar

Cuando se trabaja con funciones generatrices, es importante verificar que producen valores razonables. Al poner variables de funciones generatrices ordinarias multivariables en una sola, obtenemos funciones generadoras de superclases de estructuras o cantidades combinatorias, ya que uno o más de los parámetros desaparecen. Por ejemplo,   es la función generadora de la cuenta total de enteros no negativos de n dígitos, en la cual se usa el completado con ceros a la izquierda. De hecho, tenemos

 

lo cual es correcto. De modo similar.   es la función generadora de la suma de todos los enteros no negativos de n dígitos, de nuevo completando por la izquierda con ceros. 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«.

Ejemplo resuelto E: pseudonúmeros romanos editar

Considérese un sistema numérico creado empleando un subconjunto de las reglas y las letras de los números romanos. 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  

Cada letra tiene un peso que corresponde al número de barras que hacen falta para dibujar esa letra. Consideramos que I tiene peso uno y que X y V tienen ambas peso dos, al consistir en dos barras cruzadas la primera y en dos barras adyacentes con un punto base común la segunda. El peso de una palabra, es decir, número, es la suma de los pesos de los dígitos que la constituyen. Por ejemplo, el valor de XXVI es 26 y su peso es 2 + 2 + 2 + 1 = 7. Ahora formulamos la siguiente pregunta: ¿qué valor se puede esperar del valor de un número que tiene peson?

Empleamos la siguiente función generatriz ordinaria para responder la pregunta:

 

donde el monomio   representa una palabra de n barras (peso n) que tiene un valor k. Sea   Por definición, tenemos

 

Sumando la recurrencia con n hallamos

 

lo que da la siguiente ecuación para  :

 

Resolviendo para G, obtenemos

 

El valor esperado E(n) de una palabra de peso no es dado por la fórmula

 

donde el numerador es la suma de los valores de todas las palabras que tienen peso n, y el denominador es el número de esas palabras.

Comencemos con el denominador. Tenemos

 ,

así que el número de palabras es

 

De modo similar,

 

así que la suma de sus valores es

 

La conclusión es que el valor esperado es

 

El valor esperado es una palabra/número es lineal en el número de barras/peso del número.

La linearidad es evidente en el hecho de que la contribución de un dígito es un valor constante e independiente de su posición. Razonando con más cuidado, vemos que una palabra de peso n contiene como promedio   dígitos/letras, cuyo valor promedio es  , dando un valor esperado aproximado de  , lo cual no es lo bastante exacto, porque los dígitos no son equiprobables.

Material adicional en relación con este ejemplo, así como una instantánea de cómo se desarrolló, puede encontrarse en los «Enlaces externos«.

Enlaces externos editar