Ejemplos de funciones generadoras

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.

Contenido

1 Ejemplo resuelto A: básico
2 Ejemplo resuelto B: números de Fibonacci
3 Ejemplo resuelto C: aristas en un grafo no orientado
4 Ejemplo resuelto D: funciones generadoras en dos variables y sumas de los dígitos
5 Ejemplo resuelto E: pseudo números romanos
6 Enlaces externos

Ejemplo resuelto A: básico

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

$G(1;x)=\sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$

y sustituyendo $x$ por $2 x$ , obtenemos:

$G(1;2x)=\frac{1}{1-2x} = 1+(2x)+(2x)^2+\cdots+(2x)^n+\cdots=G(2^n;x).$

Ejemplo resuelto B: números de Fibonacci

Consideremos el problema de hallar una fórmula cerrada para los números de Fibonacci F_n definidos por F₀ = 0, F₁ = 1, y F_n = F_n−1 + F_n−2 para n ≥ 2. Formamos la función generadora ordinaria

$f = \sum_{n \ge 0} F_n x^n$

para esta sucesión. La función generadora para la sucesión (F_n−1) es xf y la de (F_n−2) es x²f. A partir de la relación de recurrencia, vemos, por lo tanto, que la serie de potencias xf + x²f concuerda con f excepto en los dos primeros coeficientes:

$\begin{array}{rcrcrcrcrcrcr} f & = & F_0x^0 & + & F_1x^1 & + & F_2x^2 & + & \cdots & + & F_ix^i & + &\cdots\\ xf & = & & & F_0x^1 & + & F_1x^2 & + & \cdots & + &F_{i-1}x^i & + &\cdots\\ x^2f & = & & & & & F_0x^2 & + & \cdots & + &F_{i-2}x^i & +&\cdots\\ (x+x^2)f & = & & & F_0x^1 & + & (F_0+F_1)x^2 & + & \cdots & + & (F_{i-1}+F_{i-2})x^i & +&\cdots\\ & = & & & & & F_2x^2 & + & \cdots & + & F_ix^i & +& \cdots\\ \end{array}$

Teniendo en cuenta éstos, hallamos que

$f = xf + x^2 f + x . \,\!$

(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

$f = \frac{x} {1 - x - x^2} .$

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

$f = \frac{1}{\sqrt{5}} \left (\frac{1}{1-\varphi_1 x} - \frac{1} {1- \varphi_2 x} \right ) .$

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

$F_n = \frac{1} {\sqrt{5}} (\varphi_1^n - \varphi_2^n).$

Ejemplo resuelto C: aristas en un grafo no orientado

El foco de este ejemplo es el uso de las funciones generadoras en muchas variables para alcanzar la meta de clasificar los elementos $m$ de un conjunto $E$ de acuerdo con muchos parámetros $r_0(m), \, r_1(m), \, \ldots$ a través de la correspondencia $m \leftrightarrow w_0^{r_0(m)} w_1^{r_1(m)} \cdots$ . Aquí las variables de la función generadora son $w_0, \, w_1, \, \ldots$ y la función generadora $f$ es

$f(w_0, w_1, \ldots) = \sum_{m\in E} w_0^{r_0(m)} w_1^{r_1(m)} \cdots$

de modo que el número $c$ de elementos de $E$ que corresponden a la tupla de parámetros $(r_0, r_1, \ldots)$ es dado por

$c = [w_0^{r_0} w_1^{r_1} \cdots] f(w_0, w_1, \ldots),$

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 $G = (V, E)$ cuyos vértices $V$ corresponden a palabras de longitud $t$ a partir de un alfabeto $Σ$ que contiene exactamente $l$ letras, es decir:

$\Sigma=\{a_1,a_2, \ldots,a_l\} \quad \mbox{and} \quad V \subseteq \Sigma^t.$

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

Además, nos dan un conjunto de funciones $p_k: \Sigma \rightarrow 2^\Sigma$ que determinan cuál de los vértices posibles $l^t\,$ aparecen en el grafo, y cuáles son las aristas. De modo más preciso, $p k (λ)$ especifica un conjunto de posibles sustitutos para $λ$ , si se presenta en una posición $k$ . En ese caso, $λ$ puede cambiarse por cualquier letra que se presente en $p k (λ)$ , 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 $p k$ ofrecen los vecinos de una letra particular que se presenta en una posición $k$ , 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 $p k (λ)$ . Queda garantizado que los $p k$ son tales que la adyacencia siempre funciona en ambos sentidos, esto es, si $\mu \in p_k(\lambda)$ , entonces $\lambda \in p_k(\mu)$ . Las palabras que contienen letras en posiciones en las que no tienen vecinos, es decir, en las que $| p k (λ) | = 0$ , 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 $V$ , y tenemos que clasificar los vértices $m$ de acuerdo con el número de letras que tienen $1, 2, 3 \ldots$ vecinos, de modo que

$m \leftrightarrow w_1^{r_1(m)} w_2^{r_2(m)} \cdots,$

siendo $r 1 (m)$ el número de letras que tienen un vecino en su posición, $r 2 (m)$ 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 $m$ es dado por

$\left( \sum_{j=1}^{l-1} j \frac{d}{d w_j} w_1^{r_1(m)} w_2^{r_2(m)} \cdots \right)_{w_1=\ldots=w_{l-1}=1}.$

Esto se debe a que $w_q^{r_q}$ indica la presencia de $r q$ letras que tienen $q$ vecinos en $m$ , que aportan $q \, r_q$ aristas, pero

$q \, r_q = q \, \left( \frac{d}{d w_q} w_q^{r_q} \right)_{w_q=1}.$

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

$T = \frac{1}{2} \left( \sum_{j=1}^{l-1} j \frac{d}{d w_j} f(w_1, \ldots, w_{l-1}) \right)_{w_1=\ldots=w_{l-1}=1}.$

Falta por hallar $f(w_1, \ldots, w_{l-1})$ . Con esto en mente, introducimos las cantidades $v k (q)$ , el número de letras de una posición $k$ que tienen $q$ vecinos, esto es,

$v_k(q) = [z^q] \sum_{\lambda\in\Sigma} z^{|p_k(\lambda)|}.$

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

L k = l - v k (0).

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

Entonces, la función generadora $f$ es dada por

$f(w_1, \ldots, w_{l-1}) = \prod_{k=0}^{t-1} \sum_{q=1}^{l-1} v_k(q) w_q.$

Calcular la respuesta

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

$\left( \frac{d}{d w_j} f(w_1, \ldots, w_{l-1}) \right)_{w_1=\ldots=w_{l-1}=1}$

equivale a

$\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}$

que se simplifica como

$\prod_{k=0}^{t-1} L_k \sum_{k=0}^{t-1} \frac{v_k(j)}{L_k},$

y resulta

$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.$

Un ejemplo sencillo

Tomemos $Σ = {0,1,2}$ , de modo que $l = 3$ , y consideremos las palabras (vértices) que consisten en dos letras, es decir, $t = 2$ . El conjunto de funciones vecinas $p k$ es dado por

$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\}.$

La función generadora se convierte en

$(w_1 + w_2 + w_1) (w_1 + w_1) = (2w_1 + w_2) 2 w_1 = 4 w_1^2 + 2 w_1 w_2 = \sum_{q=1}^2 v_0(q) w_q \sum_{q=1}^2 v_1(q) w_q.$

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

$\frac{1}{2} \left( 4 \times 1 \left( \frac{d}{d w_1} w_1^2 \right)_{w_1=1} + 2 \times \left( 1 \left( \frac{d}{d w_1} w_1 w_2 \right)_{w_1=w_2=1} + 2 \left( \frac{d}{d w_2} w_1 w_2 \right)_{w_1=w_2=1} \right) \right),$

o bien

$\frac{1}{2} \left( 4 \times 2 + 2 \times ( 1 + 2 ) \right) = 7,$

así que podemos esperar siete aristas.

De hecho, estas aristas son

$00 \leftrightarrow 01, \, 00 \leftrightarrow 10, \, 10 \leftrightarrow 11, \, 10 \leftrightarrow 20, \, 01 \leftrightarrow 11, \, 11 \leftrightarrow 21, \, 20 \leftrightarrow 21.$

El resultado encaja con lo que obtenemos sustituyendo en la fórmula. Tenemos $v_0(1) = 2, \, v_0(2)=1$ y $v_1(1) = 2\,$ , y $L 0 = 3$ y $L 1 = 2,$ lo que da

$\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.$

Caso especial

Hay un caso especial importante que ofrece una fórmula más sencilla para $T$ . Este es el caso de cuando no hay letras «inertes», es decir, cuando todas las letras tienen vecinos o bien $v k (0) = 0$ en todas las posiciones, lo que implica que $L k = l$ para todo $k$ . La fórmula simplificada se convierte en

$T = \frac{1}{2} \left( \sum_{j=1}^{l-1} j \sum_{k=0}^{t-1} v_k(j) \right) \, l^{t-1}.$

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, $0$ y $l - 1$ ), y las demás letras tienen dos vecinos. De la sustitución resulta entonces

$T = \frac{1}{2} \left( 1 \times 2 t + 2 \times (l-2) t \right) l^{t-1} = t \, (l-1) \, l^{t-1}.$

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

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 $0$ a $10 2 n - 1$ , donde esos enteros que tienen menos de $2 n$ dígitos se completan con ceros a la izquierda, de forma que de todos ellos pueda considerarse que tienen $2 n$ dígitos. Por ejemplo, para $n = 3$ el abanico va desde $000000$ hasta $999999$ . Emplearemos funciones generadoras en dos variables para responder la siguiente cuestión: ¿cuál es la suma de los enteros en $[0,10 2 n - 1]$ 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 $n = 3$ , 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 $n$ (tómese $n = 20$ , por ejemplo).

Sea $E n$ la denotación de la suma deseada, e introdúzcase $g n, k$ , que da el número de enteros n cifras de largo (completándolos con ceros como antes, para obtener $10 n$ valores) cuyas cifras suman k, y $s n, k$ , 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

$E_n = \sum_{k=0}^{9 n} (10^n+1) s_{n, k} \, g_{n, k}.$

Para ver esto, establézcase k, la suma de los dígitos, y considérese el conjunto de enteros equilibrados de longitud $2 n$ , 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 $g n, k$ veces en la primera mitad (multiplicado por $10 n$ ), y $g n, k$ veces en la segunda mitad. Añadiendo todos estos enteros, resulta $s n, k .$ El número de sumandos que contribuyen a $E n$ es dado por

$F_n = \sum_{k=0}^{9 n} g_{n, k}^2.$

Ahora introducimos las dos siguientes funciones generadoras en dos variables:

$G(z, u) = \sum_{n \ge 1, \,k \ge 0} g_{n, k} u^k z^n \quad \mbox{y} \quad S(z, u) = \sum_{n \ge 1, \,k \ge 0} s_{n, k} u^k z^n.$

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

$V(u) = \sum_{r=0}^9 u^r \quad \mbox{y} \quad W(u) = \sum_{r=0}^9 r u^r.$

Ahora, por la definición de $G (z, u)$ , se sigue inmediatamente que

$G(z, u) = \sum_{n \ge 1} V(u)^n z^n = \frac{V(u) z}{1 - V(u) z}.$

Esto se debe a que los términos de $V (u) n$ 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 $u k$ se presente cada vez que los dígitos suman k.

La siguiente observación clave es que para $n>1\,$ ,

$s_{n, k} = \sum_{r=0}^9 (10 s_{n-1, k-r} + g_{n-1, k-r} r).$

Esto quiere decir sencillamente que los enteros que contribuyen a $s_{n, k}\,$ se pueden obtener a partir de los que contribuyen a $s_{n-1, k-r}\,$ , 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 $g_{n-1, k-r}\,$ enteros que contribuyen a $s_{n-1, k-r}.\,$ )

Ahora nos disponemos a reconstituir $S (z, u)$ sumando la recurrencia de arriba con $n>1,\, k\ge 0$ . El término para $[z^1] S(z, u)\,$ , esto es, $n = 1$ , 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

$\sum_{k \ge 0} s_{1, k} u^k z = \sum_{r=0}^9 r u^r z = W(u) z.$

Añadiendo todo, hallamos que

$S(z, u) = z W(u) + 10z V(u) S(z, u) + z W(u) G(z, u)\,$

de donde

$S(z, u) = \frac{z W(u) + z W(u) G(z, u)}{1 - 10z V(u)} = z W(u) \frac{1 + G(z, u)}{1 - 10z V(u)}$

o bien

$S(z, u) = \frac{z W(u)}{(1 - z V(u))(1 - 10z V(u))} = \frac{1}{9} \frac{W(u)}{V(u)} \left( \frac{1}{1 - 10z V(u))} - \frac{1}{1 - z V(u)} \right)$

lo cual es una simple función generadora racional.

Recordemos nuestra fórmula inicial, que podemos reescribir como

$E_n = \sum_{k=0}^{9 n} (10^n+1) [z^n u^k] S(z, u) \, [z^n u^k] G(z, u).$

Ahora podemos calcular el $E n$ , ya que tenemos formas cerradas para $G (z, u)$ y $S (z, u).$ Esto nos da la siguiente tabla para $n$ y $E n$ :

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

Fórmula explícita alternativa

Una fórmula explícita para $E n$ , 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 $S(z, u)\,$ y empleando la simetría de $[z^n] G(z, u)\,$ para observar que

$E_n = (10^n+1) \sum_{k=0}^{9 n} s_{n, k} \, g_{n, 9n-k},$

lo cual nos da

$E_n = (10^n+1) [u^{9n}] ([z^n] G(z, u) [z^n] S(z, u)).\,$

Pero

$[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}$

de modo que

$E_n = \frac{1}{9} (100^n - 1) [u^{9n}] W(u) V(u)^{2n-1}.$

Recurrencia alternativa

El lector sagaz habrá observado que obtuvimos la recurrencia para $s n, k$ añadiendo el dígito r a uno de los contribuyentes de $s_{n-1, k-r}\,$ . Por supuesto, es enteramente posible preañadir r a esos contribuyentes, lo que resulta en la recurrencia alternativa

$s_{n, k} = \sum_{r=0}^9 (10^{n-1} g_{n-1, k-r} r + s_{n-1, k-r}).$

Sumando como antes, hallamos

$S(z, u) = z W(u) + z W(u) G(10z, u) + z V(u) S(z, u)\,$

Resolver esto para $S (z, u)$ produce, como esperábamos, la misma solución que antes:

$S(z, u) = z W(u) \frac{1 + G(10z, u)}{1 - z V(u)} = \frac{z W(u)}{(1 - z V(u))(1 - 10z V(u))}.$

Verificación

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, $G(z, 1)\,$ 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

$[z^n] G(z, 1) = [z^n]\frac{10z}{1-10z} = 10^n,$

lo cual es correcto. De modo similar. $S(z, 1)\,$ 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

$[z^n] S(z, 1) = [z^n] \frac{45 z}{(1 - 10z)(1-100z)} = [z^n] \left( \frac{1}{2} \frac{1}{1-100z} - \frac{1}{2} \frac{1}{1-10z} \right).$

De ahí

$[z^n] S(z, 1) = \frac{1}{2} 100^n - \frac{1}{2} 10^n.$

Este también es el valor correcto, ya que

$\sum_{k=0}^{10^n-1} k = \frac{1}{2} (10^n - 1) 10^n.$

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

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

$\Sigma = \left\{ I, V, X \right\}$

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:

$G(z, u) = \sum_{n\ge 1, \; k\ge 1} u^k z^n$

donde el monomio $z n u k$ representa una palabra de n barras (peso n) que tiene un valor k. Sea $v n = [z n] G (z, u).$ Por definición, tenemos

$\begin{align} v_1 & = u \\ v_2 & = u^2 + u^5 + u^{10} \\ v_n & = u v_{n-1} + u^5 v_{n-2} + u^{10} v_{n-2} \quad \mbox{donde} \quad n>2. \end{align}$

Sumando la recurrencia con n hallamos

$\sum_{n>2} v_n z^n = u z \sum_{n>2} v_{n-1} z^{n-1} + (u^5 + u^{10}) z^2 \sum_{n>2} v_{n-2} z^{n-2}\,,$

lo que da la siguiente ecuación para $G (z, u)$ :

$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).\,$

Resolviendo para G, obtenemos

$G(z, u) = -{\frac {uz \left( 1+z{u}^{4}+z{u}^{9} \right) }{-1+uz+{z}^{2}{u}^{5}+{z}^{2}{u}^{10}}}$

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

$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} },$

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

$\left. G(z, u) \right|_{u=1} = -1+1/3\, \left( z+1 \right) ^{-1}-2/3\, \left( 2\,z-1 \right) ^{-1}$ ,

así que el número de palabras es

$\frac{2}{3} 2^n + \frac{1}{3} (-1)^n.$

De modo similar,

$\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},$

así que la suma de sus valores es

$\left( {\frac {17}{9}}\,n-{\frac {11}{27}} \right) {2}^{n}+ \left( {\frac {14}{9}}\,n+ {\frac {11}{27}} \right) \left( -1 \right) ^{n}.$

La conclusión es que el valor esperado es

$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}.$

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 $3 / 5 n$ dígitos/letras, cuyo valor promedio es $17 / 3$ , dando un valor esperado aproximado de $17 / 5$ , 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

Funciones generadoras, índices de potencias y cambio de moneda (en inglés) en Cut-the-knot.org (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)
"Generating Functions" por Ed Pegg, Jr., en el sitio web The Wolfram Demonstrations Project, 2007. (consultado el 1 de agosto de 2008)
León-Sotelo, José H. Nieto, Marko Riedel, et al., Alfa-barras, newsgroup es.ciencia.matemáticas

Obtenido de "Ejemplos de funciones generadoras"

Categorías: Combinatoria | Exponenciales

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

Función generadora — 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… … Wikipedia Español
Distribución normal — Saltar a navegación, búsqueda Distribución normal Función de densidad de probabilidad La línea verde corresponde a la distribución normal estandar Función de distribución de probabilidad … Wikipedia Español
Producto de Euler — Saltar a navegación, búsqueda Leonhard Euler. En matemática, un producto de Euler es la expansión de un producto infinito, indexado por números primos p de una serie de Dirichlet. El nombre surge del caso especial de la función … Wikipedia Español
Matemáticas discretas — Las matemáticas discretas son un área de las matemáticas encargadas del estudio de los conjuntos discretos: finitos o infinitos numerables. En oposición a las matemáticas continuas, que se encarga del estudio de conceptos como la continuidad y el … Wikipedia Español
Parámetro estadístico — Saltar a navegación, búsqueda La media aritmética … Wikipedia Español
Energías renovables en la escala doméstica — Saltar a navegación, búsqueda Contenido 1 Energías Alternativas en la escala doméstica 2 La cuestión energética en la Argentina 3 Matriz energética … Wikipedia Español
Caesaraugusta — sobre plano moderno de la ciudad 1. Decumano (actuales calles Mayor, Espoz y Mina y Manifestación) 2. Cardo (actual calle Don Jaime) 3. Foro de Caesaraugusta 4. Puerto fluvial 5. Termas públicas 6. Teatro 7. Muralla … Wikipedia Español
Terrorismo — General Convenciones Contraterrorismo Guerra contra el terrorismo Tipos Nacionalista Religioso Patrocinado por Estados Racista Narcoterrorismo … Wikipedia Español
México — Para otros usos de este término, véase México (desambiguación). «Mexicano» redirige aquí. Para otras acepciones, véase Mexicano (desambiguación). «Mexicana» redirige aquí. Para la aerolínea, véase Mexicana de Aviación … Wikipedia Español
Electricidad — Este artículo o sección puede ser demasiado extenso(a). Algunos navegadores pueden tener dificultades al mostrar este artículo. Por favor, considera separar cada sección por artículos independientes, y luego resumir las secciones presentes en… … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Ejemplos de funciones generadoras

Ejemplos de funciones generadoras

Contenido

Ejemplo resuelto A: básico

Ejemplo resuelto B: números de Fibonacci