Matemáticas | Funciones generadoras – Conjunto 2

Requisito previo: generación de funciones: introducción y requisitos previos
En el conjunto 1 llegamos a conocer los conceptos básicos sobre la generación de funciones. Ahora discutiremos más detalles sobre la generación de funciones y sus aplicaciones.

Funciones generadoras exponenciales –
Sea $h_0, h_1, h_2, ........., h_n, ......$ una secuencia. Entonces su función generadora exponencial, denotada por $g^e(x)$ está dada por,

$g^e(x) =\sum_{n=0}^{+\infty} \frac{x^n}{n!} h_n$

Ejemplo 1:- Sea {1, 1, 1…….} una secuencia. La función generadora de la secuencia es
$g^e(x) = \sum_{n=0}^{+\infty} \frac{x^n}{n!}$ ( Aquí $h_n$ = 1 para todo n )
Ejemplo 2: – Sea $permanente{n}{k}$ el número de k permutaciones en un conjunto de n elementos. Entonces la función generadora exponencial para la secuencia $^nP_0, ^nP_1, ......., ^nP_n$ es

$g^e(x) =\sum_{k=0}^{n} \frac{x^n}{n!} ^nP_k = \sum_{k=0}^{n} \frac{x^k}{k!} \frac{n!}{(n-k)!} = \sum_{k=0}^{n} \frac{n!}{k!(n-k)!} x_k = \sum_{k=0}^{n} \^nC_k x_k =(1+x)^n$

La función de generación exponencial se utiliza para determinar el número de n-permutaciones de un conjunto que contiene elementos repetitivos. Veremos ejemplos más adelante.

Uso de funciones generadoras para resolver relaciones de recurrencia: las relaciones de recurrencia
lineales homogéneas se pueden resolver utilizando la función generadora. Tomaremos un ejemplo aquí para ilustrar.

Ejemplo:- Resuelva la ecuación de recurrencia homogénea lineal $h_n=5h_{n-1}+6h_{n-2}$ .
Dado $h_0$ =1 y $h_1=-2$ .

Usamos la función generadora para resolver este problema. Sea g(x) la función generadora de la sucesión $h_0, h_1, h_2, ......, h_n, ....$ .
Por lo tanto g(x)= $h_0+h_1 x + h_2 x^2 +........+ h_n x^n+....$
Entonces obtenemos las siguientes ecuaciones.
g(x)= $h_0+h_1 x + h_2 x^2 +........+ h_n x^n+....$

-5xg(x)= $-h_0x+h_1 x^2 + h_2 x^3 +........+ h_n x^n+1+....$

$6x^2g(x)$ = $h_0 x^2+h_1 x^3 + h_2 x^4 +........+ h_n x^n+2+....$

Sumando estas 3 cantidades obtenemos
$(1+5-6x^2)g(x)=h_0 + (h_1-5h_0)x +(h_2-5h_1+6h_0)+....... +(h_n-5h_{n-1}+6h_{n-2})x^n+.....$

Ahora $h_n-5h_{n-1}+6h_{n-2}$ =0 para todo n>1. Asi que,

$(1+5x-6x^2)g(x)=h_0 + (h_1-5h_0)x = (1-7x)$

O g(x)= $\frac{(1-7x)}{(1+5-6x^2)}$

Ahora $(1+5x-6x^2)$ =(1-2x)(1-3x)

Entonces g(x)= $\frac{(1-7x)}{(1-2x)(1-3x)}$

Es fácil ver eso $\frac{(1-7x)}{(1-2x)(1-3x)}=\frac{5}{(1-2x)}-\frac{4}{(1-3x)}$

ahora $\frac{1}{(1-2x)}=1 + 2x+2^2 x^2 +2^3 x^3+.... +2^n x^n+......$
y $\frac{1}{(1-3x)}=1 + 3x+3^2 x^2 +3^3 x^3+.... +3^n x^n+......$

Entonces g(x)= $5(1 + 2x+2^2 x^2 +2^3 x^3+.... +2^n x^n+......)-4(1 + 3x+3^2 x^2 +3^3 x^3+.... +3^n x^n+......)$

Dado que esta es la función generadora de la sucesión $h_0, h_1, ......h_n$ , observamos que $h_n=5*2^n-4*3^n$

Por lo tanto, podemos resolver ecuaciones de recurrencia utilizando funciones generadoras.

Prueba de identidades a través de funciones generadoras:
también se pueden probar varias identidades utilizando funciones generadoras. Aquí ilustramos una de ellas.

Ejemplo: Demostrar que: $^nC_r=^{(n-1)}C_r+^{(n-1)}C_{r-1}$
Aquí usamos la función generadora de la secuencia, $^nC_0, ^nC_1, ......^nC_r....$ es decir $(1+x)^n$ .
Ahora, $(1+x)^n=(1+x)^{n-1}(1+x)=(1+x)^{n-1}+x(1+x)^{n-1}$
para LHS, el término que contiene $x^n$ es $^nC_r$ .Para RHS, el término que contiene $x^n$ es $^{(n-1)}C_r+^{(n-1)}C_{r-1}$ . Entonces $^nC_r=^{(n-1)}C_r+^{(n-1)}C_{r-1}$ (probado)