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:
![{\displaystyle G(1;x)=\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1db5f814004fa641ef93112bc1dbd4b4e889e7a8)
y sustituyendo
por
, obtenemos:
![{\displaystyle G(1;2x)={\frac {1}{1-2x}}=1+(2x)+(2x)^{2}+\cdots +(2x)^{n}+\cdots =G(2^{n};x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2514b3e74742dd1822994f15c4c48c1e611f135)
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
![{\displaystyle f=\sum _{n\geq 0}F_{n}x^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d0ccd7adbe7f29c15a36e3afbc34e66d4faa892)
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:
![{\displaystyle {\begin{array}{rcrcrcrcrcrcr}f&=&F_{0}x^{0}&+&F_{1}x^{1}&+&F_{2}x^{2}&+&\cdots &+&F_{i}x^{i}&+&\cdots \\xf&=&&&F_{0}x^{1}&+&F_{1}x^{2}&+&\cdots &+&F_{i-1}x^{i}&+&\cdots \\x^{2}f&=&&&&&F_{0}x^{2}&+&\cdots &+&F_{i-2}x^{i}&+&\cdots \\(x+x^{2})f&=&&&F_{0}x^{1}&+&(F_{0}+F_{1})x^{2}&+&\cdots &+&(F_{i-1}+F_{i-2})x^{i}&+&\cdots \\&=&&&&&F_{2}x^{2}&+&\cdots &+&F_{i}x^{i}&+&\cdots \\\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea9fd7dc872e6338f16997e4ad19d770a9fca432)
Teniendo en cuenta éstos, hallamos que
![{\displaystyle f=xf+x^{2}f+x.\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d2d4549ad0a4da8a79648bc32335e1cc6167327)
(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
![{\displaystyle f={\frac {x}{1-x-x^{2}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c94d0681b629012277880c3f72e0a82f8de10cbe)
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:
![{\displaystyle f={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi _{1}x}}-{\frac {1}{1-\varphi _{2}x}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b4d2ae823f9b1dc2a5d07a1cd6c94c9b7afe554)
Estas dos series formales de potencias se conocen expresamente porque son series geométricas; comparando coeficientes, hallamos la fórmula explícita
![{\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(\varphi _{1}^{n}-\varphi _{2}^{n}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0321c7001ffc9a8c023c580692d89f36a0010a03)
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
![{\displaystyle f(w_{0},w_{1},\ldots )=\sum _{m\in E}w_{0}^{r_{0}(m)}w_{1}^{r_{1}(m)}\cdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/450a21471e4e0cbaac6140c3244b8ad95799fa48)
de modo que el número
de elementos de
que corresponden a la tupla de parámetros
es dado por
![{\displaystyle c=[w_{0}^{r_{0}}w_{1}^{r_{1}}\cdots ]f(w_{0},w_{1},\ldots ),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2ad1586607ca748033518f60790a0a4fabe0dc0)
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:
![{\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{l}\}\quad {\mbox{and}}\quad V\subseteq \Sigma ^{t}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a63cd38e8c7ff1332147753407ef9549a3135478)
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
![{\displaystyle m\leftrightarrow w_{1}^{r_{1}(m)}w_{2}^{r_{2}(m)}\cdots ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a427cb10cbb0ac32ef51284009511479afaf1a19)
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
![{\displaystyle \left(\sum _{j=1}^{l-1}j{\frac {d}{dw_{j}}}w_{1}^{r_{1}(m)}w_{2}^{r_{2}(m)}\cdots \right)_{w_{1}=\ldots =w_{l-1}=1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84f7495e4cb62390b3f083df097ba9fb97e482e8)
Esto se debe a que
indica la presencia de
letras que tienen
vecinos en
, que aportan
aristas, pero
![{\displaystyle q\,r_{q}=q\,\left({\frac {d}{dw_{q}}}w_{q}^{r_{q}}\right)_{w_{q}=1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f03353faeb4ed932c6c97f40c2e4f0ca2d0523c8)
Este proceso contará las aristas dos veces (una vez en cada extremo), dando finalmente la fórmula para el número
de aristas
![{\displaystyle T={\frac {1}{2}}\left(\sum _{j=1}^{l-1}j{\frac {d}{dw_{j}}}f(w_{1},\ldots ,w_{l-1})\right)_{w_{1}=\ldots =w_{l-1}=1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58e5c2874f16c6864d7863140fed26cacac41c3a)
Falta por hallar
. Con esto en mente, introducimos las cantidades
, el número de letras de una posición
que tienen
vecinos, esto es,
![{\displaystyle v_{k}(q)=[z^{q}]\sum _{\lambda \in \Sigma }z^{|p_{k}(\lambda )|}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/229eee772687842b2d154400aab4668016f2c58c)
También nos hará falta
, el número de letras que de hecho se presentan en la posición
, es decir,
![{\displaystyle L_{k}=l-v_{k}(0).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b73e216071d8c3b24bbeda7a8fd0c6bada0ed1c1)
(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
![{\displaystyle f(w_{1},\ldots ,w_{l-1})=\prod _{k=0}^{t-1}\sum _{q=1}^{l-1}v_{k}(q)w_{q}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae884d060a77c7287f1678ceeb0b8277e7e1f3b9)
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
![{\displaystyle \left({\frac {d}{dw_{j}}}f(w_{1},\ldots ,w_{l-1})\right)_{w_{1}=\ldots =w_{l-1}=1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22820a57997442f30514a967008c9262f3633d82)
equivale a
![{\displaystyle \left(f(w_{1},\ldots ,w_{l-1})\sum _{k=0}^{t-1}{\frac {v_{k}(j)}{\sum _{q=1}^{l-1}v_{k}(q)w_{q}}}\right)_{w_{1}=\ldots =w_{l-1}=1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcc504adea8a95a22bfc202d6fbe5c2d4e7ea5fd)
que se simplifica como
![{\displaystyle \prod _{k=0}^{t-1}L_{k}\sum _{k=0}^{t-1}{\frac {v_{k}(j)}{L_{k}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebc5e7714e941e306294e3034b32b3803623d65f)
y resulta
![{\displaystyle T={\frac {1}{2}}\left(\sum _{j=1}^{l-1}j\sum _{k=0}^{t-1}{\frac {v_{k}(j)}{L_{k}}}\right)\,\prod _{k=0}^{t-1}L_{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5cc003187bc9f9cac80bdf72201cc94618feb8e)
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
![{\displaystyle p_{0}(0)=\{1\},\,p_{0}(1)=\{0,2\},\,p_{0}(2)=\{1\}\quad {\mbox{and}}\quad p_{1}(0)=\{1\},\,p_{1}(1)=\{0\}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe27e28192da03862b7a7564c8fb6fe47c551553)
La función generadora se convierte en
![{\displaystyle (w_{1}+w_{2}+w_{1})(w_{1}+w_{1})=(2w_{1}+w_{2})2w_{1}=4w_{1}^{2}+2w_{1}w_{2}=\sum _{q=1}^{2}v_{0}(q)w_{q}\sum _{q=1}^{2}v_{1}(q)w_{q}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7eb2cb29702e88edc9f21ee5df03749303dba5f)
Extrayendo la diferenciación, hallamos la siguiente expresión para
:
![{\displaystyle {\frac {1}{2}}\left(4\times 1\left({\frac {d}{dw_{1}}}w_{1}^{2}\right)_{w_{1}=1}+2\times \left(1\left({\frac {d}{dw_{1}}}w_{1}w_{2}\right)_{w_{1}=w_{2}=1}+2\left({\frac {d}{dw_{2}}}w_{1}w_{2}\right)_{w_{1}=w_{2}=1}\right)\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/874eddd0199ddab85de6b208c549aa801ac39332)
o bien
![{\displaystyle {\frac {1}{2}}\left(4\times 2+2\times (1+2)\right)=7,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfd793b7e2c390cc3318512924817649a43d913e)
así que podemos esperar siete aristas.
De hecho, estas aristas son
![{\displaystyle 00\leftrightarrow 01,\,00\leftrightarrow 10,\,10\leftrightarrow 11,\,10\leftrightarrow 20,\,01\leftrightarrow 11,\,11\leftrightarrow 21,\,20\leftrightarrow 21.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb2f76cc29c8e8e5a60e7cf40f7e6fa223bde7ad)
El resultado encaja con lo que obtenemos sustituyendo en la fórmula. Tenemos
y
, y
y
lo que da
![{\displaystyle {\frac {1}{2}}\left(1\times \left({\frac {2}{3}}+{\frac {2}{2}}\right)+2\times \left({\frac {1}{3}}\right)\right)\times 3\times 2=7.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35b3dc5c7f71cac861f4564e0d6b967f527d3632)
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
![{\displaystyle T={\frac {1}{2}}\left(\sum _{j=1}^{l-1}j\sum _{k=0}^{t-1}v_{k}(j)\right)\,l^{t-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4877afa798ea975058cee1524f6e2ed8c2bee2b)
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
![{\displaystyle T={\frac {1}{2}}\left(1\times 2t+2\times (l-2)t\right)l^{t-1}=t\,(l-1)\,l^{t-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbe5946578f80686bd62a476715cc469c14d29c1)
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
![{\displaystyle E_{n}=\sum _{k=0}^{9n}(10^{n}+1)s_{n,k}\,g_{n,k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/479866d5fd248f15e2c134f76d34b7c184aca735)
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
![{\displaystyle F_{n}=\sum _{k=0}^{9n}g_{n,k}^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f089a5d410c56a832bc62baaacbda8e4e4070c34)
Ahora introducimos las dos siguientes funciones generatrices en dos variables:
![{\displaystyle G(z,u)=\sum _{n\geq 1,\,k\geq 0}g_{n,k}u^{k}z^{n}\quad {\mbox{y}}\quad S(z,u)=\sum _{n\geq 1,\,k\geq 0}s_{n,k}u^{k}z^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f4a05480120fb266cdd18c32d47a624db374a2e)
(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:
![{\displaystyle V(u)=\sum _{r=0}^{9}u^{r}\quad {\mbox{y}}\quad W(u)=\sum _{r=0}^{9}ru^{r}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8101d09e3fec1315bf88a17771f703f20fb52651)
Ahora, por la definición de
, se sigue inmediatamente que
![{\displaystyle G(z,u)=\sum _{n\geq 1}V(u)^{n}z^{n}={\frac {V(u)z}{1-V(u)z}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8da71b1fd60ed8bb3c3dbc9ae7aefbc814aab211)
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
,
![{\displaystyle s_{n,k}=\sum _{r=0}^{9}(10s_{n-1,k-r}+g_{n-1,k-r}r).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81d373fec6cfc84f68854bf560def4544f1d8f85)
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
![{\displaystyle \sum _{k\geq 0}s_{1,k}u^{k}z=\sum _{r=0}^{9}ru^{r}z=W(u)z.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83856b8c0316d25ce1d96706cf1296f6d16c3eb1)
Añadiendo todo, hallamos que
![{\displaystyle S(z,u)=zW(u)+10zV(u)S(z,u)+zW(u)G(z,u)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0412be028fed903390d57a5d9783cbd186b7c55d)
de donde
![{\displaystyle S(z,u)={\frac {zW(u)+zW(u)G(z,u)}{1-10zV(u)}}=zW(u){\frac {1+G(z,u)}{1-10zV(u)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7125855d2429d63d0504b6f36c489f3f3287461)
o bien
![{\displaystyle S(z,u)={\frac {zW(u)}{(1-zV(u))(1-10zV(u))}}={\frac {1}{9}}{\frac {W(u)}{V(u)}}\left({\frac {1}{1-10zV(u))}}-{\frac {1}{1-zV(u)}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f48c8dbd78d7de86b2dd08905d19c3d46ca037dd)
lo cual es una simple función generatriz racional.
Recordemos nuestra fórmula inicial, que podemos reescribir como
![{\displaystyle E_{n}=\sum _{k=0}^{9n}(10^{n}+1)[z^{n}u^{k}]S(z,u)\,[z^{n}u^{k}]G(z,u).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f45274438231e2dc407d23b63f4276de554c475)
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
![{\displaystyle E_{n}=(10^{n}+1)\sum _{k=0}^{9n}s_{n,k}\,g_{n,9n-k},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cec0c38b3c775607d087174e7ad43157ecbd17d)
lo cual nos da
![{\displaystyle E_{n}=(10^{n}+1)[u^{9n}]([z^{n}]G(z,u)[z^{n}]S(z,u)).\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19e1b7f2a982caf7f3104afca189f95fb954e220)
Pero
![{\displaystyle [z^{n}]S(z,u)={\frac {1}{9}}{\frac {W(u)}{V(u)}}\left(10^{n}V(u)^{n}-V(u)^{n}\right)={\frac {1}{9}}W(u)(10^{n}-1)V(u)^{n-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bd114e228a5b7c63bfe161f000d117ad02800328)
de modo que
![{\displaystyle E_{n}={\frac {1}{9}}(100^{n}-1)[u^{9n}]W(u)V(u)^{2n-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e4448163cd1736d35c62be5274e3d0992691f86)
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
![{\displaystyle s_{n,k}=\sum _{r=0}^{9}(10^{n-1}g_{n-1,k-r}r+s_{n-1,k-r}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc16b815c5cc46437c314f2a4f38a01b8ad0d4d9)
Sumando como antes, hallamos
![{\displaystyle S(z,u)=zW(u)+zW(u)G(10z,u)+zV(u)S(z,u)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b02b7f4f3ef48bc7f8c47770dd1d5685bbeb314)
Resolver esto para
produce, como esperábamos, la misma solución que antes:
![{\displaystyle S(z,u)=zW(u){\frac {1+G(10z,u)}{1-zV(u)}}={\frac {zW(u)}{(1-zV(u))(1-10zV(u))}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97f9046dc9c26d111a5f47a50389f515409ae842)
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
![{\displaystyle [z^{n}]G(z,1)=[z^{n}]{\frac {10z}{1-10z}}=10^{n},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/005ec9263faffd489d484af24f1d902e215ab776)
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
![{\displaystyle [z^{n}]S(z,1)=[z^{n}]{\frac {45z}{(1-10z)(1-100z)}}=[z^{n}]\left({\frac {1}{2}}{\frac {1}{1-100z}}-{\frac {1}{2}}{\frac {1}{1-10z}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf0359a3fbe6c3b4ad3ee62c555645b35fe96d45)
De ahí
![{\displaystyle [z^{n}]S(z,1)={\frac {1}{2}}100^{n}-{\frac {1}{2}}10^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11be6fd5986e66f331eb4ea80e87697a8d3e39ea)
Este también es el valor correcto, ya que
![{\displaystyle \sum _{k=0}^{10^{n}-1}k={\frac {1}{2}}(10^{n}-1)10^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ab7371de558edaf4733b013fdde4f51e7a8ce6a)
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
![{\displaystyle \Sigma =\left\{I,V,X\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd1c07721748928c0dedc3e610397d25f98946a3)
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:
![{\displaystyle G(z,u)=\sum _{n\geq 1,\;k\geq 1}u^{k}z^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cc76758d565a8ea582678467bfae15f605f6a55)
donde el monomio
representa una palabra de n barras (peso n) que tiene un valor k. Sea
Por definición, tenemos
![{\displaystyle {\begin{aligned}v_{1}&=u\\v_{2}&=u^{2}+u^{5}+u^{10}\\v_{n}&=uv_{n-1}+u^{5}v_{n-2}+u^{10}v_{n-2}\quad {\mbox{donde}}\quad n>2.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce294a857e4e519890c47757a906a35abfb60089)
Sumando la recurrencia con n hallamos
![{\displaystyle \sum _{n>2}v_{n}z^{n}=uz\sum _{n>2}v_{n-1}z^{n-1}+(u^{5}+u^{10})z^{2}\sum _{n>2}v_{n-2}z^{n-2}\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2646441c6800d24b8cba2fe1dd74b1364950ee8)
lo que da la siguiente ecuación para
:
![{\displaystyle G(z,u)-uz-(u^{2}+u^{5}+u^{10})z^{2}=uz(G(z,u)-uz)+(u^{5}+u^{10})z^{2}G(z,u).\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11b33817a217041de15b5c23f19215c32ccb033b)
Resolviendo para G, obtenemos
![{\displaystyle G(z,u)=-{\frac {uz\left(1+z{u}^{4}+z{u}^{9}\right)}{-1+uz+{z}^{2}{u}^{5}+{z}^{2}{u}^{10}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8ef6a4768d7d969bfb34e1a8e92e53a9bbdf101)
El valor esperado E(n) de una palabra de peso no es dado por la fórmula
![{\displaystyle E(n)={\frac {[z^{n}]\left.{\frac {\operatorname {d} }{\operatorname {d} u}}G(z,u)\right|_{u=1}}{[z^{n}]\left.G(z,u)\right|_{u=1}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcbe75639609bbf1fdf56d39c0e703a1a38cfda1)
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
![{\displaystyle {\frac {2}{3}}2^{n}+{\frac {1}{3}}(-1)^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5aa13350475217893786c9642efe5de04b65efeb)
De modo similar,
![{\displaystyle \left.{\frac {\operatorname {d} }{\operatorname {d} u}}G(z,u)\right|_{u=1}={\frac {14}{9}}\,\left(z+1\right)^{-2}-{\frac {31}{27}}\,\left(z+1\right)^{-1}+{\frac {17}{9}}\,\left(2\,z-1\right)^{-2}+{\frac {62}{27}}\,\left(2\,z-1\right)^{-1},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8da72d62dea91107f4ac3d1304133b220b248012)
así que la suma de sus valores es
![{\displaystyle \left({\frac {17}{9}}\,n-{\frac {11}{27}}\right){2}^{n}+\left({\frac {14}{9}}\,n+{\frac {11}{27}}\right)\left(-1\right)^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/507d31759cac6dc56511c018b67a229cb47e256e)
La conclusión es que el valor esperado es
![{\displaystyle E(n)={\frac {\left({\frac {17}{9}}\,n-{\frac {11}{27}}\right){2}^{n}+\left({\frac {14}{9}}\,n+{\frac {11}{27}}\right)\left(-1\right)^{n}}{{\frac {2}{3}}2^{n}+{\frac {1}{3}}(-1)^{n}}}\quad \approx {\frac {17}{6}}n-{\frac {11}{18}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb3800bc56ebaff9e274b681267706ded5d4bbff)
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]
- Bogomolny, Alexander. «Generating Functions». Interactive Mathematics Miscellany and Puzzles (en inglés). Consultado el 1 de agosto de 2008.
- Versión descargable (PDF) en inglés de Generatingfunctionology, de H. Wilf (consultado el 1 de agosto de 2008)
- 1031 Generating Functions (consultado el 1 de agosto de 2008)
- Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matemáticas
- Frederick Lecue; Riedel, Marko, et al., Permutation, Les-Mathematiques.net, en francés (el título desorienta un tanto)
- Ed Pegg, Jr. «Generating Functions». The Wolfram Demonstrations Project (en inglés). Wolfram Research. Consultado el 1 de agosto de 2008.
- León-Sotelo, José H. Nieto, Marko Riedel, et al., Alfa-barras, newsgroup es.ciencia.matemáticas