Encontre uma recorrência para , o número de sequências de letras dentre ou , que não têm letras vizinhas.

Passo 1

Então, a gente precisa encontrar uma recorrência para , que representa o número de sequências de letras escolhidas entre ou , garantindo que não tenham letras vizinhas. Para resolver isso, vamos usar conceitos de recursão e contar as possibilidades passo a passo.

Passo 2

Vamos analisar como a sequência pode terminar. O último caractere da sequência pode ser:
  1. Uma letra diferente de (ou seja, , , ou ).
  2. A letra .

Passo 3

Caso 1: Se o último caractere for , ou , então as primeiras letras podem formar qualquer sequência válida de tamanho (já que não estamos impondo restrições adicionais). Como temos 3 opções para o último caractere, isso dá um total de:

Passo 4

Caso 2: Se o último caractere for , precisamos garantir que o caractere antes dele não seja (para evitar duas juntas). Assim, as primeiras letras devem formar uma sequência válida de tamanho , e o penúltimo caractere pode ser , ou (3 opções). Então, esse caso contribui com:

Passo 5

Somando os dois casos, a recorrência que relaciona com os termos anteriores fica:

Resposta

A recorrência para é:

Exercícios relacionados

Considere o conjunto das sequências de tamanho tais que cada entrada pertence a e entradas vizinhas sempre diferem por 1 em módulo. Descreva um sistema de equações de recorrência para resolver este problema.
Um esporte pouco conhecido é o de subir escadas. Encontre uma relação de recorrência para o número de maneiras de se subir degraus de uma escada, se a cada passo pode-se escolher subir um ou dois degraus. Se considerarmos a questão de iniciar com o pé direito ou esquerdo, como ficará a recorrência?
Seja o número de permutações caóticas de . Sem usar a fórmula para , deduza a equação de recorrência
Uma triangulação de um polígono convexo é uma divisão de em triângulos usando algumas de suas diagonais de modo que suas diagonais não se intersectem, veja a Figura 3.10. Encontre uma relação de recorrência
Figura 3.10. Duas triangulações diferentes do pentágono .
para , onde denota o número de triangulações de um polígono convexo de lados.
Dica: para ajudar na contagem, fixe um lado do polígono e o triângulo que contém esse lado, e faça a contagem. Depois some sobre todos os triângulos possíveis que contém esse lado.