Ejemplos de funciones generadoras

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Los siguientes ejemplos de funciones generadoras se presentan siguiendo el espíritu de George Pólya, que abogaba por el aprendizaje de las matemáticas 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 generadora ordinaria

para esta sucesión. La función generadora 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 generadoras.) 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 generadoras 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 sólo 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 generadora 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 generadoras en dos variables y sumas de los dígitos[editar]

Las funciones generadoras 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 generadoras de probabilidad en dos variables, donde una función generadora ordinaria genera una exponencial. A menudo se denomina a estos tipos de funciones generadoras «super funciones 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 generadoras 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 izquiera, 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 generadora 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 generadoras, es importante verificar que producen valores razonables. Al poner variables de funciones generadoras 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: pseudo nú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 generadora 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]