Universidad Técnica Federico Santa María
Departamento de Informática
Fundamentos Informática II
Funciones Generatrices
1
Funciones Generatrices :









Motivación
Definición y Ejemplos
Técnicas de Cálculo
Metodología
Ejemplos
Ecuaciones Lineales Enteras
Particiones de Enteros
Función Generatriz Exponencial (Ejemplo)
Operador de Suma (Ejemplo)
2
Funciones Generatrices :
Motivación 1:
 Repartición de Naranjas:
(Ecuaciones Lineales Enteras)
De cuántas formas posibles se pueden
repartir 12 naranjas de manera que
Gabriel (G) reciba al menos 4 y María
(M) y Francisco (F) reciban al menos 2.
3
Funciones Generatrices :
Motivación: Repartición de Naranjas
(Ecuaciones Lineales Enteras)
 Buscamos la cantidad total de soluciones
de la ecuación:
x1 + x2 + x3 = 12
Donde:
4 ≤ x1 ≤ 8
xk : cantidad de
naranjas de
la persona k
2 ≤ x2 ≤ 6
2 ≤ x3 ≤ 6
4
Funciones Generatrices :
Motivación: Repartición de Naranjas
(Ecuaciones Lineales Enteras)
G 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8
2
3
4
5
6
2
3
4
5
2
3
4
3
2
2
M
F
6 5 4 3 2 5 4 3 2 4 3 2 2 3 2
Cantidad Total de Formas de Repartir: 15
5
Funciones Generatrices :
Motivación: Repartición de Naranjas
(Ecuaciones Lineales Enteras)
 Idea: (Euler & DeMoivre) Contar Formas de
Repartir como Producto de Polinomios !
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6) =
20
= ∑ αk
k=8
Cantidad Total de Formas de Repartir
xk
Dem !
20
= ∑ αkxk + 15 x12
k=8
k≠15
≈
x8 ∑ xk
k≥0
6
Funciones Generatrices :
Motivación 2: Sist. Ecs. Enteras
 De cuantas maneras podemos
seleccionar r objetos de n con
repeticiones ???
 Cantidad total de soluciones enteras de
la ecuación: (solución más adelante …)
x1 + x2 + x3 + ··· + xn-1 + xn = r
7
Funciones Generatrices :
Formas de solucion:
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
 Por convolucion:

En Matlab o Scilab:

conv([1 1 1 1 1 0 0 0 0], [1 1 1 1 1 0 0 ])

conv(ans, [1 1 1 1 1 0 0 ])

ans(20-12+1)
8
Funciones Generatrices :
Formas de solucion:
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
 Por fuerza bruta:
contador=0;
for x1=4:8,
for x2=2:6,
for x3=2:6,
if (x1+x2+x3)==12
contador=contador+1;
end
end
end
end
9
Funciones Generatrices :
Formas de solucion:
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
 Midiendo tiempos de ejecución

En Matlab:

tic toc
10
Funciones Generatrices :
Formas de solucion:
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)

Midiendo tiempos de ejecución

En C:
La forma de calcular el tiempo de CPU que toma una función
es muy simple:



tomamos el valor del reloj antes de realizar la llamada (t_ini),

llamamos a la rutina en cuestión, y

tomamos nuevamente el valor del reloj (t_fin).
La diferencia entre t_fin - t_ini nos da el total de tiempo que
tomó: 1) hacer la llamada a la rutina, 2) que esta haga su
trabajo, 3) que devuelva el resultado.
11
Funciones Generatrices :
Formas de solución:
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)

Midiendo tiempos de ejecucion en C

Para tomar el tiempo podemos usar la rutina clock(), que devuelve el
tiempo aproximado de CPU que transcurrió desde que nuestro programa
fue iniciado, dicho tiempo representado en un valor de tipo clock_t: un valor
entero que indica una cantidad de "tics" de reloj.
La precisión que tenemos con dicha rutina es de CLOCKS_PER_SEC (tics
de reloj por segundo), lo que significa que por cada segundo que pasa, la
función clock() nos devolverá CLOCKS_PER_SEC unidades más que el
valor anterior. En MinGW, CLOCKS_PER_SEC es igual a 1000, pero es
mejor no fiarse de esto, ya que en otras plataformas dicho valor varía.
Inclusive, según POSIX, la constante CLOCKS_PER_SEC debería ser
1000000.
12
Funciones Generatrices :
Formas de solución:
(x4+x5+x6+x7+x8)(x2+x3+x4+x5+x6) (x2+x3+x4+x5+x6)
#include <stdio.h>
#include <time.h>
int main(int argc, char *argv[])
{
clock_t t_ini, t_fin;
double secs;
t_ini = clock();
/* ...hacer algo... */
t_fin = clock();
secs = (double)(t_fin - t_ini) / CLOCKS_PER_SEC;
printf("%.16g milisegundos\n", secs * 1000.0);
return 0;
}
13
Funciones Generatrices :
Definición y Ejemplos:
 Dada una secuencia de números reales
a0, a1, ... ,an ,... la función definida por:
∞
G(x) = ∑ akxk
k=0
Se denomina Función Generatriz
asociada a la secuencia a0, a1 ,... ,an ,...
14
Funciones Generatrices :
Ejemplos y Técnicas de Cálculo:
 Si aK = 1 para todo k є N
∞
G1(x) = ∑
xk
= (1 – x )
-1
k=0
 Si aK =
n
k
para k = 0,…,n
n
G2(x) =
∑
k=0
n
k
xk
= (1 + x )
n
15
Funciones Generatrices :
Técnicas de Cálculo:
 Si aK = 1 para k = 0,…,n
n
G3(x) = ∑ xk = (1 – xn+1 )/(1 – x )
k=0
 Como:
∞
G1'(x) = ∑ (k+1)xk = (1 – x )-2
k=0
Entonces aK = (k+1) para k = 0,1,2,…
16
Funciones Generatrices :
Técnicas de Cálculo:
 Como:
∞
G4(x) = xG1'(x) = ∑
kxk =
x /(1 – x )
2
k=0
Entonces aK = k para k = 0,1,2,…
 Como:
∞
G5(x) = xG4'(x) = ∑
k2xk =
x(x+1)/(1 – x )
3
k=0
Entonces aK = k2 para k = 0,1,2,…
17
Funciones Generatrices :
Técnicas de Cálculo:
 Por Desarrollo de Maclaurin:
∞
G6(x) = ∑
(-1)k n+k-1
k
k=0
xk
= (1+x )
-n
n
Entonces 1/(1+x ) es la función generatriz
de la secuencia:
aK =
(-1)k
n+k-1
k
= (-1)kC(n+k-1,k) k = 0,1,2,…
18
Funciones Generatrices :
Técnicas de Cálculo:
 Demostrar que: (Ejercicio)
∞
G7(x) = ∑
n+k-1
k
xk
= (1-x )
-n
k=0
n
Entonces 1/(1-x ) es la función generatriz
de la secuencia:
aK =
n+k-1
k
= C(n+k-1,k) para k = 0,1,2,…
19
Funciones Generatrices :
Combinaciones con Repetición y
Ecuaciones Lineales Enteras
 Teorema: El número de selecciones,
con repetición, de tamaño 1  r  n
de una colección de n objetos
indistingibles y el número de
soluciones enteras de la ecuación :
x1 + x2 + x3 + ... + xn = r
es C(n+r-1,r)
20
Funciones Generatrices :
Combinaciones con Repetición y
Ecuaciones Lineales Enteras
 Demostración:
La función generatriz del problema es:
G(x) = (1+x+x2+x3+ ... )n = (1-x)-n
Buscamos el p-ésimo coeficiente
que es C(n+r-1,r) (recordar G7)
21
Funciones Generatrices :
Metodología:
a) Se modela el problema de enumeración
como un producto de polinomios.
b) Se opera el producto de polinomios
obtenido mediante las Técnicas de
Cálculo vistas.
c) Se obtiene una combinación de
funciones generatrices conocidas
d) Se obtiene el coeficiente del polinomio de
la función generatriz que se busca
22
Funciones Generatrices :
Ejemplos:
a) Obtener la función generatriz de la
secuencia: 0, 2, 6, 12, 20, …
b) Resolver la ecuación lineal entera:
x1 + x2 = 13
2 ≤ x1 ≤ 10
3 ≤ x2 ≤ 11
c) Obtener el coeficiente de x5 en (1-2x)-7
d) Obtener el coeficiente de x8 en:
G(x) = [(x-3)(x-2)2]-1
23
Funciones Generatrices :
Particiones de Enteros
 Sea la función natural que entrega la
cantidad total de formas de obtener n
como una suma de naturales.
Buscamos obtener p(n) en función de n
Entonces:
n
p(n) = ∏1/(1-xk)
k=0
p(n=0) = 1
24
Funciones Generatrices :
Función Generatriz Exponencial:
 Dada una secuencia de números reales
a0, a1, ... ,an ,... la función definida por:
∞
GE (x) = ∑ akxk / k!
k=0
Se denomina Función Generatriz
Exponencial asociada a la secuencia a0,
a1 ,... ,an ,...
25
Funciones Generatrices :
F. G. Exponencial: Ejemplo

Un barco lleva 48 banderas, 12 de cada uno
de los colores: rojo, blanco azul y negro.
Doce (12) banderas, una señal, están
puesta en un mástil para comunicación
visual con otros barcos.
a) Cuántas señales tienen un número impar de
banderas azules y un número par de
banderas negras ?
b) Cuántas señales tienen al menos 3 banderas
blancas o no tienen banderas blancas ?
26
Funciones Generatrices :
Operador de Suma:
 Dada una secuencia de números reales
a0, a1, ... ,an ,... consideremos la función:
∞
G(x) = ∑ akxk
k=0
Luego:
∞
∞
G(x)/(1-x) = ∑ akxk ∑ xk
k=0
∞
k=0
n
= ∑ ∑ akxk
n=0 k=0
27
Funciones Generatrices :
Operador de Suma: Ejemplos
 Encuentre una fórmula en función de n
para expresar la secuencia:
n
an = ∑ i2
i=0
 Encuentre la función generatriz de la
secuencia:
n
an = ∑ (1/i!)
i=0
28
Descargar

Funciones Generatrices - Universidad Técnica Federico Santa María