Función generadora ordinaria y exponencial

Dada una sucesión de números reales $\{ a_n \}$, la función generadora ordinaria de dicha sucesión es definida como $f(x):= \sum_{n\geq 0} a_n x^n$. Es importante remarcar que no se tienen en cuenta los dominios de convergencia de $f$: solo nos interesa conocer y manejar los coeficientes de cada monomio particular.

De acuerdo a lo trabajado en la sección del teorema multinomial:

$$(1+x)^n \ \text{genera la secuencia } \binom{n}{0}, \binom{n}{1}, \dotsb , \binom{n}{n}, 0,0, \dotsb$$

$$(1+x)^{-n} \ \text{genera la secuencia } \binom{n-1}{0}, \binom{n}{1}, \dotsb , \binom{n+r-1}{r}, \dotsb$$

, donde $n$ es un natural cualquiera. Generalmente, en situaciones de conteo, este tipo de desarrollos no suelen ser muy útiles. En particular, si se plantea el reparto uniforme ($n$ objetos iguales, sin importar el orden de recibimiento), una función generadora ordinaria puede englobar todas las combinaciones de reparto. Por cada usuario $i$ que interviene el reparto, se diseña:

$$f_i(x) = a_{i0} + a_{i1} x + a_{i2} x^2 + \dotsb + a_{in}x^n$$

, donde cada monomio $a_{ij}x^j$ trabaja la posibilidad del usuario $i$ a recibir $j$ unidades en el reparto. Según sea posible o no:

$$a_{ij} := \begin{cases} 1 & , \text{ si el usuario } i \text{ puede recibir } j \text{ unidades} \\ 0 & , \text{ en otro caso} \end{cases} \quad , j=0,...,n$$

Si se consideran $m$ usuarios sobre los que repartir, la función generadora global del problema es el producto de las particulares (¿Por qué?):

$$f(x) := f_1 (x) \dotsb f_m (x) = \prod_{l=1}^m \sum_{j=0}^n a_{lj}x^j$$

Por ejemplo, si repartimos $12$ pelotas idénticas entre tres jugadores, de manera que el primero no recibe más de $3$ y el segundo debe recibir al menos una, la función generadora ordinaria a plantear es:

$$f(x) = (1+x+x^2+x^3) (x+\dotsb +x^{12}) (1+x+\dotsb + x^{11})$$

Ya que repartimos $12$ pelotas, la cantidad de hacerlo entre los tres jugadores establecidos es el coeficiente de $x^{12}$ en $f(x)$. En muchas ocasiones, es conveniente extender el desarrollo de la función generadora al desarrollo en serie:

$$1+x+x^2 + \dotsb = (1-x)^{-1} := \sum_{r=0}^\infty \binom{1+r-1}{r} x^r$$

, y trabajar el coeficiente buscado a partir de estos desarrollos. En el caso que hemos planteado, solo podemos considerar este desarrollo en los dos últimos factores, pues se conserva el coeficiente de $x^{12}$ en ese caso:

$$\tilde{f}(x) = (1+x+\dotsb + x^3) (x+x^2 +\dotsb) (1+x+\dotsb) = \frac{1-x^4}{1-x} \cdot \frac{x}{1-x} \cdot \frac{1}{1-x}$$

El coeficiente de $x^{12}$ en $x(1-x^4) (1-x)^{-3}$ es:

$$\binom{3+11-1}{11} - \binom{3+7-1}{7} = 42$$

, concluyendo que hay $42$ formas de hacer el reparto. Este problema se puede realizar aplicando el principio de inclusión exclusión sobre la ecuación:

$$x_1 + x_2 + x_3 = 12 \quad , x_1 \leq 3, x_2 \geq 1 ; x_i \in \mathbb{Z}^+$$

, ya que el reparto realizado es de objetos idénticos.

A partir del ejemplo anterior, vemos que la función $f(x) = \frac{1}{1-x}$ será muy frecuentada. Esta función es denominada operador suma, y es la generadora de la secuencia de unos: $1,1,1,...$. Sus derivadas permiten generar secuencias monótonas útiles para desarrollos posteriores. Por ejemplo:

$$f(x) = \frac{1}{1-x} = 1+x + x^2 + \dotsb \Longrightarrow f'(x) = \frac{1}{(1-x)^2}=1+2x+3x^2+\dotsb$$

Por lo que $(1-x)^{-2}$ genera la secuencia: $1,2,3,...$. Podríamos multiplicar por $x$ y posteriormente derivar para generar la secuencia de cuadrados: $1^2, 2^2, 3^2,...$; y así sucesivamente.

CONVOLUCIÓN

Si $f(x) = \sum_{n\geq 0} a_n x^n, g(x) = \sum_{k\geq 0} b_k x^k$, donde $\{a_n \}, \{b_k \}\subseteq \mathbb{R}$, entonces el producto toma la forma:

$$f(x) \cdot g(x) = \sum_{n\geq 0} c_n x^n \quad , \text{ donde } c_n := \sum_{k=0}^n a_{k} b_{n-k} = \sum_{k=0}^n a_{n-k} b_{k}  \qquad (1)$$

Observar que si tomamos $g(x)$ como el operador suma, entonces los coeficientes de $f(x) g(x)$ son precisamente la suma acumulada de los términos que genera $f(x)$. Esto es: $c_n := \sum_{k=0}^n a_n$. De esta manera, la convolución permite conocer la expresión general de sumas finitas, siempre y cuando se conozca bien el producto $f(x)\cdot g(x)$ correspondiente.

FUNCIÓN GENERADORA EXPONENCIAL

Este tipo de función generadora es particularmente útil cuando repartimos objetos distintos (equivalentemente, importa el orden de asignación en el reparto). Previamente, prestábamos atención a combinaciones, pero en este caso hablamos de permutaciones, para poder así tener en cuenta el orden del reparto. Teniendo en cuenta: $C(n,r) = P(n,r) / r!$, los monomios a trabajar son de la forma $a_{ij} x^j / j!$. Se introduce así la siguiente definición:

(Función generadora exponencial) La función generadora exponencial de la sucesión $\{a_n \} \subseteq \mathbb{R}$ es definida como:

$$f(x) = a_0 + \frac{a_1}{1!} x + \frac{a_2}{2!} x^2 + \dotsb = \sum_{n\geq 0} a_n x^n /n! $$

La mecánica de planteamiento para un problema de reparto de $n$ objetos es idéntica al caso de generadora ordinaria, sin embargo buscamos el coeficiente de $x^n /n!$ en la función planteada.

EJERCICIOS PROPUESTOS

1. Determinar la cantidad de formas de distribuir $33$ pacientes idénticos en tres salas diferentes de una sala de emergencias, de manera que cada una reciba al menos cinco pacientes pero no más de 15. Solución.
2. En EEUU, hay monedas de 1,5,10,25,50 céntimos de dólar; y de $1$ dólar. ¿De cuántas formas podemos reunir un dólar con monedas?.
3. Calcula la cantidad de números telefónicos que se pueden formar usando los cuatro primeros números impares, de manera que cada uno de ellos o aparece al menos dos veces, o no aparece. Solución.
4. Determinar $\sum_{k=0}^n k^2 5^k$. Solución.
5. (EXAMEN) Una multinacional ofrece un concurso de méritos para contratar a un grupo de personas. Se presentan mil candidatos a estos puestos de trabajo, y finalmente son contratadas cien personas. Estos 100 nuevos empleados de la empresa deben ser asignados a cuatro sucursales, ubicadas en las siguientes provincias: Córdoba, Jaén, Salamanca y Valladolid. Calcular el número de repartos posibles de estas cien personas entre las cuatro sucursales en cada uno de los siguientes supuestos: a) En cada provincia el número de empleados nuevos no tiene limitación. b) Se debe establecer al menos un nuevo trabajador en cada provincia. c) Debe asignarse un número impar de empleados nuevos en las provincias de Córdoba y Jaén. d) En las provincias de Salamanca y Valladolid se establece un número impar de empleados nuevos, mientras que en las provincias de Córdoba y Jaén se asigna un número par de nuevos trabajadores (el cero se considera número par).
6. (EXAMEN) Calcular usando funciones generadoras: $$\sum_{k=1}^n (k-1)^2 \quad \sum_{k=1}^n (k-1)^3 \quad \sum_{k=1}^n ((k+5)^3- (k-1)^2) \quad \sum_{k=1}^n \sum_{r=1}^k (r^2 -2r+1)$$ , donde $n$ es un natural cualquiera.