Funciones generatrices

“Una función generatriz es una cuerda donde tendemos una sucesión de números.”

— Herbert Wilf

Definición

Dada una sucesión numérica, su función generatriz es la serie de potencias formal cuyos coeficientes son los elementos de la sucesión. Es decir, si la sucesión es \(a_0\), \(a_1\), \(a_2\), \(a_3\), \(\dots\), la función generatriz es

\[ A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n=0}^\infty a_n x^n \]

Propiedades básicas

1. Sean \(A(x)\) y \(B(x)\) las funciones generatrices de las sucesiones \((a_n)_0^\infty\) y \((b_n)_0^\infty\), respectivamente. Halla las sucesiones correspondientes a las siguientes funciones:

   • \(cA(x)\), \(c \in \R\)
   • \(xA(x)\)
   • \(A(x) + B(x)\)
   • \(A(x)B(x)\)
   Solución

   • Al multiplicar la serie \(A(x)\) por una constante \(c\), todos sus coeficientes quedan multiplicados por \(c\). Así, la función generatriz \(cA(x)\) corresponde a la sucesión \((ca_n)_0^\infty\).
   • Al multiplicar por \(x\), el grado de todos los monomios aumenta en \(1\). Por lo tanto, \(xA(x)\) describe la sucesión \(0, a_0, a_1, a_2, \dots\).
   • \(a_0+b_0, a_1+b_1, a_2+b_2, \dots = (a_n+b_n)_0^\infty\)
   • \(a_0b_0, a_0b_1+a_1b_0, a_0b_2+a_1b_1+a_2b_0, \dots = (\sum_{k=0}^n a_k b_{n-k})_0^\infty\)

2. Si \(A(x)\) es la función generatriz de la sucesión \((a_n)_0^\infty\), ¿qué sucesión corresponde a \(\frac{A(x)}{1-x}\)?

   Solución

   Sea \((b_n)_0^\infty\) la sucesión buscada. Entonces,

   \[ \begin{align*} a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots &= (1-x)(b_0 + b_1 x + b_2 x^2 + b_3 x^3 + \cdots) \\ &= b_0 + (b_1-b_0) x + (b_2-b_1) x^2 + (b_3-b_2) x^3 + \cdots \end{align*} \]

   Igualando los coeficientes correspondientes, tenemos \(a_0 = b_0\) y \(a_n = b_n - b_{n-1}\) para \(n \geq 1\). Reordenando términos, \(b_n = a_n + b_{n-1}\), y sustituyendo repetidamente

   \[ \begin{align*} b_n &= a_n + b_{n-1} \\ &= a_n + a_{n-1} + b_{n-2} \\ &= a_n + a_{n-1} + a_{n-2} + b_{n-3} \\ &= \cdots \\ &= a_n + a_{n-1} + a_{n-2} + a_{n-3} + \cdots + a_0 \\ &= \sum_{k=0}^n a_k \end{align*} \]

   Es decir, la sucesión \((b_n)_0^\infty\) corresponde a las sumas parciales de \((a_n)_0^\infty\).

   \[ \frac{A(x)}{1-x} = a_0 + (a_0+a_1) x + (a_0+a_1+a_2) x^2 + (a_0+a_1+a_2+a_3) x^3 + \cdots = \sum_{n=0}^\infty\left(\sum_{k=0}^n a_k\right) x^n \]

3. Halla las funciones generatrices para las siguientes sucesiones:

   • \(1, 0, 1, 0, 1, 0, \dots\)
   • \(1, 2, 4, 8, 16, \dots\)
   • \(1, 2, 3, 4, 5, 6, \dots\)
   • \(1, 3, 6, 10, 15, 21, \dots\)
   Solución

   • Sea \(A(x) = 1 + x^2 + x^4 + \cdots\), entonces, \(x^2 A(x) = A(x) - 1\). Despejando,

   \[ A(x) = \frac{1}{1-x^2} \]

   • Sea \(B(x) = 1 + 2x + 4x^2 + 8x^3 + \cdots\), entonces, \(2x B(x) = B(x) - 1\). Despejando,

   \[ B(x) = \frac{1}{1-2x} \]

   • Sea \(C(x) = 1 + 2x + 3x^2 + 4x^3 + \cdots\), entonces, \(x C(x) = x + 2x^2 + 3x^3 + \cdots\) y restando obtenemos \(C(x) - xC(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}\). Despejando,

   \[ C(x) = \frac{1}{(1-x)^2} \]

   • La sucesión corresponde a las sumas parciales de la sucesión anterior. Por lo tanto, su función generatriz es la de la anterior dividida entre \(1-x\) (podríamos haber hecho lo mismo en el apartado anterior),

   \[ D(x) = \frac{1}{(1-x)^3} \]

Fibonacci

4. Sea \(F(x)\) la función generatriz de la sucesión \(f_0\), \(f_1\), \(f_2\), \(f_3\), … Halla las funciones generatrices para las siguientes sucesiones:

   • \(0\), \(f_0\), \(f_1\), \(f_2\), \(f_3\), \(\dots\)
   • \(0\), \(0\), \(f_0\), \(f_1\), \(f_2\), \(f_3\), \(\dots\)
   • \(0\), \(0\), \(0\), \(f_0\), \(f_1\), \(f_2\), \(f_3\), \(\dots\)
   Solución

   • \(xF(x)\)
   • \(x^2F(x)\)
   • \(x^3F(x)\)

5. La sucesión de Fibonacci \((f_n)_0^\infty\) es la generada por \(f_0=0\), \(f_1=1\) y la recurrencia \({f_n = f_{n-1} + f_{n-2}}\) para \(n \geq 2\). Usa el apartado anterior para hallar la función generatriz de la sucesión de Fibonacci.

   Solución

   Sea \(F(x)\) la función generatriz de la sucesión de Fibonacci. Entonces,

   \[ \begin{align*} F(x) &= f_0 &+ &f_1 x &+ &f_2 x^2 &+ f_3 x^3 &+ f_4 x^4 &+ \cdots \\ xF(x) &= 0 &+ &f_0 x &+ &f_1 x^2 &+ f_2 x^3 &+ f_3 x^4 &+ \cdots \\ x^2F(x) &= 0 &+ &0 &+ &f_0 x^2 &+ f_1 x^3 &+ f_2 x^4 &+ \cdots \\ \end{align*} \]

   Despejando,

   \[ \begin{align*} F(x) - xF(x) - x^2F(x) &= \overbrace{f_0}^{0} + \overbrace{(f_1 - f_0)}^{1} x + \sum_{n=2}^\infty{\overbrace{(f_n-f_{n-1}-f_{n-2})}^{0 \text{ (recurrencia)}}}x^n \\ F(x)(1 - x - x^2) &= x \\ F(x) &= \frac{x}{1-x-x^2} \end{align*} \]

6. Usa la descomposición en fracciones parciales para hallar una expresión cerrada para los números de Fibonacci.

Dados

Podemos representar un dado con cualquier número de caras y cualesquiera valores en sus caras mediante una función generatriz. Por ejemplo:

• \(\{1,2,3,4,5,6\} \to x+x^2+x^3+x^4+x^5+x^6\)
• \(\{2,2,4,7,7,7\} \to x^2+x^2+x^4+x^7+x^7+x^7 = 2x^2+x^4+3x^7\)
• \(\{1,1,3,4\} \to x+x+x^3+x^4 = 2x+x^3+x^4\)

Es decir, cada cara con un valor \(k\) corresponde a un monomio \(x^k\). Si hay \(c_k\) caras con ese valor, la función generatriz contendrá el monomio \(c_k x^k\).

7. Sean \(A(x)\) y \(B(x)\) las funciones generatrices para dos dados cualesquiera.

   • ¿Qué representa \(A(1)\)?
   • ¿Qué información contiene la sucesión cuya función generatriz es \(A(x)B(x)\)?
   • Halla la función generatriz cuyos coeficientes \(c_k\) dan la probabilidad de obtener una suma de \(k\) al lanzar los dados \(A\) y \(B\).
   Solución

   • El número de caras del dado.
   • Cada coeficiente representa el número de combinaciones de caras de \(A\) y \(B\) para una suma dada.
   • El apartado anterior da el número de combinaciones. Para obtener la probabilidad debemos dividir entre el número total de combinaciones, que es el producto de las caras de \(A\) por las caras de \(B\). Es decir, la función generatriz buscada es

   \[ \frac{A(x)B(x)}{A(1)B(1)} \]

8. Si lanzamos dos dados normales y calculamos su suma, hay:

   • 1 combinación de suma 2: \(1+1\)
   • 2 combinaciones de suma 3: \(1+2\), \(2+1\)
   • 3 combinaciones de suma 4: \(1+3\), \(2+2\), \(3+1\)
   • …
   • 1 combinación de suma 12: \(6+6\)

   Usando funciones generatrices, ¿puedes hallar dos dados de 6 caras no estándar cuya suma tenga la misma distribución que dos dados normales?

   Pista

   Debes factorizar polinomios.

   Solución

   Un dado normal se representa mediante

   \[ \begin{align*} D(x) &= x+x^2+x^3+x^4+x^5+x^6 \\ &= x(1+x+x^2+x^3+x^4+x^5) \\ &= x(1+x)(1+x^2+x^4) \\ &= x(1+x)(1+2x^2+x^4 - x^2) \\ &= x(1+x)((1+x^2)^2 - x^2) \\ &= x(1+x)(1+x+x^2)(1-x+x^2) \end{align*} \]

   Entonces, la suma de dos dados normales se puede representar mediante el producto de un dado por sí mismo, como se ha visto en el problema anterior:

   \[ \begin{align*} S(x) &= D(x) D(x) \\ &= x^2 (1+x)^2 (1-x+x^2)^2 (1+x+x^2)^2 \\ &= x^2 + 2x^3 + 3x^4 + 4x^5 + 5x^6 + 6x^7 + 5x^8 + 4x^9 + 3x^{10} + 2x^{11} + x^{12} \end{align*} \]

   Conociendo los factores, podemos buscar todas las formas de repartirlos entre dos polinomios, ambos representando dados de 6 caras. Aunque se puede hacer a mano, es laborioso, así que usaremos el sistema de cálculo SageMath. Puedes ejecutar y editar este código aquí.

   from itertools import product
   
   def caras(dado):
       # Convierte el polinomio dado en una lista de sus caras:
       #   caras(x+x^2+x^3+x^4+x^5+x^6) = [1, 2, 3, 4, 5, 6]
       #   caras(2x+x^3+x^4) = [1, 1, 3, 4]
       c = []
       for grado,coef in dado.dict().items():
           c.extend([grado] * coef)
       return sorted(c)
   
   R.<x> = PolynomialRing(ZZ)
   
   # f.g. de un dado
   dado = x + x^2 + x^3 + x^4 + x^5 + x^6
   
   # f.g. de la suma de dos dados
   suma_dados = dado * dado
   
   # lista de factores con multiplicidades
   factores = [(fac,exp) for fac,exp in suma_dados.factor()]
   
   # calculamos todas las formas posibles de repartir
   # los factores de suma_dados en dos polinomios P y Q
   for exps in product(range(3), repeat=4):
       P = prod(f[0]^exps[i] for i,f in enumerate(factores))
       Q = prod(f[0]^(2-exps[i]) for i,f in enumerate(factores))
   
       # si el número de caras de ambos dados es 6, los mostramos
       if P.subs(x=1) == Q.subs(x=1) == 6:
           print(caras(P))
           print(caras(Q))
           print('')
   

   Hay varias soluciones, pero la única no estándar y con todas las caras mayores que 0 es la formada por los dados

   \[ \boxed{\{1,2,2,3,3,4\} \text{ y } \{1,3,4,5,6,8\}} \]

Monedas

Una moneda también puede representarse mediante una función generatriz. Esto nos da un método muy general para resolver una gran variedad de problemas.

9. Sea \(u_k\) el número de maneras de obtener una suma de \(k\) euros con monedas de 1 €. Sea \(d_k\) el número de maneras de obtener una suma de \(k\) euros con monedas de 2 €.

   • Halla la sucesión \((u_n)_0^\infty\) y su función generatriz.
   • Halla la sucesión \((d_n)_0^\infty\) y su función generatriz.

10. Halla la función generatriz correspondiente a usar monedas de 1 € y monedas de 2 €. Por ejemplo, ahora una suma de 2 € se puede lograr de dos formas, con dos monedas de 1 € o con 1 moneda de 2 €.

11. En una cadena de restaurantes venden trozos de pollo en cajas de 6, 9 y 20. Halla la función generatriz que expresa el número de combinaciones de cajas con un total de \(k\) trozos de pollo.

Desarreglos

Un desarreglo es una permutación sin puntos fijos. Es decir, una ordenación de \(n\) elementos en la que ningún elemento \(k\) se encuentre en la posición \(k\). Por ejemplo, de las \(3! = 6\) permutaciones de 3 elementos, solo 2 no tienen puntos fijos. Por lo tanto, \(d_3 = 2\).

\[ \begin{array}{ccc} \cancel{1}\cancel{2}\cancel{3} & 21\cancel{3} & \boxed{312} \\ \cancel{1}32 & \boxed{231} & 3\cancel{2}1 \end{array} \]

Sea \(D(x)\) la función generatriz exponencial para la sucesión \((d_n)_0^\infty\), que es la función generatriz de la sucesión \((\frac{d_n}{n!})_0^\infty\),

\[ D(x) = \sum_{n=0}^\infty \frac{d_n}{n!}x^n = d_0 + d_1 x + \frac{d_2}{2!} x^2 + \frac{d_3}{3!} x^3 + \frac{d_4}{4!} x^4 + \cdots \]

Dado que hay \(n!\) permutaciones de \(n\) elementos, la fracción de las que son desarreglos es \(\frac{d_n}{n!}\).

12. Si \(A(x)\) y \(B(x)\) son funciones generatrices exponenciales para las sucesiones \((a_n)_0^\infty\) y \((b_n)_0^\infty\), respectivamente, y \(C(x) = A(x)B(x)\) es la función generatriz exponencial para la sucesión \((c_n)_0^\infty\), halla \(c_n\) en función de \((a_n)_0^\infty\) y \((b_n)_0^\infty\).

13. Usando el problema anterior,

    • halla una expresión racional para \(e^x D(x)\)
    • halla \(D(x)\)
    • halla una expresión cerrada para sus coeficientes \(\frac{d_n}{n!}\)
    • halla el límite \(\lim_{n \to \infty} \frac{d_n}{n!}\)