Download FUNCIONES GENERATRICES - Departamento de Matemática

MATEMÁTICA DISCRETA
TEMA 3
FUNCIONES
GENERATRICES
CURSO 2000-2001
DEPARTAMENTO
DE
M ATEMÁTICA APLICADA
F ACULTAD DE INFORMÁTICA U.P.M.
Matemática Discreta
Dpto. Matemática Aplicada. Facultad de Informática. UPM.
Curso 00-01
RELACIONES DE RECURRENCIA
1)
Resolver las siguientes relaciones de recurrencia, con sus condiciones iniciales:
an = 3 an−1
n ≥ 1,
a0 = 2.
an − an−1 = 3 n 2
n ≥ 1, a0 = 7.
an − 3 an−1 = 5. 7n
n ≥ 1,
a0 = 2.
n
.
an − 3 an−1 = 5 3
n ≥ 1,
a0 = 2.
2)
Problema de las Torres de Hanoi: Se tienen n discos y 3 estacas. Los discos están apilados en la
estaca 1, ordenados de mayor a menor. El objetivo es pasar los discos uno por uno a otra estaca,
colocados en el orden original. En el proceso no se permite que un disco mayor se coloque sobre
otro menor. Si an es el número de movimientos que se requieren para hacer esto, encontrar una
relación de recurrencia para an y resolverla.
3)
Sea C un conjunto con 2n números reales, n≥1. Sea an el número de comparaciones que deben
efectuarse entre los elementos de C para determinar el máximo y el mínimo de C. Encontrar una
relación de recurrencia para an y resolverla.
4)
Sean n rectas trazadas en el plano de manera que cada recta corte a las restantes, pero que no haya
tres coincidentes. Para cada n≥0, sea an el nº de regiones en que las n rectas dividen al plano.
Encontrar una relación de recurrencia para an y resolverla.
5)
Repetir el ejercicio anterior para b n , siendo b n el número de regiones infinitas.
6)
Resolver las siguientes relaciones de recurrencia, con sus condiciones iniciales:
an = 4 an–1 – 4 an–2
n ≥ 2,
a0 = 6, a1 = 8.
an = 7 an–1 – 10 an–2
n ≥ 2,
a0 = 2, a1 = 1.
an = 2 an–1 – an–2
n ≥ 2,
a0 = 4, a1 = 1.
an+2 = – 4 an+1 + 5 an
n ≥ 0,
a0 = 2, a1 = 8.
an = 6 an–1 – 11 an–2 + 6 an–3 n ≥ 3,
a0 = 2, a1 = 5, a2 = 15.
an = 5 an–1 – 6 an–2
n ≥ 2,
a0 = 1, a1 = 0.
7)
Sea an el número de palabras de longitud n formadas con los dígitos {0,1}, que no tienen ceros
consecutivos. Encontrar una relación de recurrencia para an y resolverla.
8)
Método de la burbuja para ordenar n números:
Sea L = {a1 ,a2 ,...,an } un conjunto de números naturales
Comparamos an con an–1 . Si an ≥ an–1 no modificamos la lista, si an < an–1 intercambiamos an y an–1 ,
obteniendo una nueva lista a la que llamamos L, como la anterior.
Comparamos an–1 con an–2 y reiteramos el proceso.
Después de n – 1 comparaciones, el menor término ocupa la posición a1 .
Si Sn es el número de comparaciones necesarias para ordenar n números por este método, encontrar
una relación de recurrencia para Sn y resolverla.
9)
Sea C = {a, b, c} y sea Sn el conjunto de cadenas de longitud n formadas con las letras de C que
tienen un número par de letras a consecutivas. Encontrar una relación de recurrencia para Sn y
resolverla.
10) Sea g(n) el nº de subconjuntos de k elementos que tiene un conjunto de n elementos, donde ambos
números son naturales, n ≥ k, y k fijo. Obtener una relación de recurrencia para g(n).
11) Encontrar una fórmula para la función g(n) definida del modo siguiente:
g(1) = 1
g(n) = g(n – 1) + 2n – 1, si n > 1.
12) Hallar una relación de recurrencia para el número de formas en que una persona puede subir n
escalones si puede subir uno o dos peldaños en cada paso.