Ejemplos de funciones generadoras

Ejemplos de funciones generadoras

Ejemplos de funciones generadoras

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

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 2x, 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 Fn definidos por F0 = 0, F1 = 1, y Fn = Fn−1 + Fn−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 (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:


\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 = (1 + √5)/2 y φ2 = (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, pk(λ) 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 pk(λ), 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 pk 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 pk(λ). Queda garantizado que los pk 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 | pk(λ) | = 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 r1(m) el número de letras que tienen un vecino en su posición, r2(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 derq 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 vk(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 Lk, el número de letras que de hecho se presentan en la posición k, es decir,

Lk = lvk(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 pk 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 L0 = 3 y L1 = 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 vk(0) = 0 en todas las posiciones, lo que implica que Lk = 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 102n − 1, donde esos enteros que tienen menos de 2n dígitos se completan con ceros a la izquierda, de forma que de todos ellos pueda considerarse que tienen 2n 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,102n − 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 En la denotación de la suma deseada, e introdúzcase gn,k, que da el número de enteros n cifras de largo (completándolos con ceros como antes, para obtener 10n valores) cuyas cifras suman k, y sn,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 2n, 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 gn,k veces en la primera mitad (multiplicado por 10n), y gn,k veces en la segunda mitad. Añadiendo todos estos enteros, resulta sn,k. El número de sumandos que contribuyen a En 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 gn,k = 0 y sn,k = 0 para k > 9n, porque 9n 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 uk 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 En, ya que tenemos formas cerradas para G(z,u) y S(z,u). Esto nos da la siguiente tabla para n y En:

    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 En, 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 sn,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 znuk representa una palabra de n barras (peso n) que tiene un valor k. Sea vn = [zn]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 / 5n 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


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

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”