Buscar

Matemática Discreta -Lista 4

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Lista 4 de Matema´tica Combinato´ria (Relac¸o˜es de Recorreˆncia)
1 Uma pessoa deseja subir uma escada. Supondo que cada passo a ser dado possa cubrir ou um u´nico degrau
ou dois degraus de uma vez, ache uma relac¸a˜o de recorreˆncia para an, onde an e´ o o nu´mero de maneiras
diferentes que essa pessoa pode subir uma escada com n degraus (n ≥ 1) (com as restric¸o˜es dadas).
2 (i)Determine a relac¸a˜o de recorreˆncia que fornece o nu´mero de diviso˜es que n retas provocam em um plano
se: na˜o existem duas retas paralelas, e treˆs retas na˜o se encontram em um mesmo ponto.
(ii)Resolva a relac¸a˜o de recorreˆncia encontrada em (i)
3 Determine a relac¸a˜o de recorreˆncia para an, o nu´mero de sequeˆncias terna´rias de n digitos que na˜o conteˆm
a subsequeˆncia 012
4 (i) Determine a relac¸a˜o de recorreˆncia que fornece o nu´mero de sequeˆncias quaterna´rias de n digitos que
conteˆm um nu´mero par de zeros.
(ii)Resolva a relac¸a˜o de recorreˆncia encontrada em (i)
5 Resolva as seguintes relac¸o˜es de recorreˆncia:
(i) an − 7an−1 + 12an−2 = 0, ao = 2 e a1 = 7,
(ii) an − 9an−2 = 0, ao = 2 e a1 = 0,
(iii) an = 4an−2, ao = 0 e a1 = 1,
(iv) an = 3an−2 − 2an−3, ao = 1, a1 = 0 e a2 = 0,
(v) an = 3an−1 + n+ 2, ao = 1,
(vi) an = 2an−1 − an−2 + 2
n, ao = 2 e a1 = 1.

Outros materiais