Download FUNCIONES GENERATRICES - Departamento de Matemática
Document related concepts
Transcript
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.