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.

Passo 1

Beleza, vamos dar uma olhada nesse exercício! A gente precisa trabalhar com sequências de tamanho onde cada número na sequência pode ser 0, 1, 2 ou 3. Além disso, números que estão um ao lado do outro na sequência têm que diferir exatamente por 1, considerando o módulo (ou seja, diferenças circulares). Nosso objetivo aqui é montar um sistema de equações de recorrência que nos ajude a contar quantas dessas sequências são possíveis para um determinado .

Passo 2

Primeiro, vamos entender melhor o que são equações de recorrência. Elas são como receitas que nos permitem calcular termos em uma sequência usando os termos anteriores. No nosso caso, queremos expressar o número de sequências de tamanho em função do número de sequências de tamanhos menores.

Passo 3

Vamos chamar de o número de sequências de tamanho que terminam em 0, 1, 2 e 3, respectivamente. Isso ajuda a organizar nossa contagem com base no último número da sequência.

Passo 4

Agora, vamos pensar nas possíveis maneiras de chegar a um número final específico, considerando que números vizinhos precisam diferir por 1 (mod 4).
  • Terminar com 0 ( ): O número anterior tem que ser , porque e diferem por 1.
  • Terminar com 1 ( ): O número anterior pode ser ou , já que ambos diferem de por 1.
  • Terminar com 2 ( ): O número anterior pode ser ou .
  • Terminar com 3 ( ): O número anterior tem que ser , porque e diferem por 1.

Passo 5

Com base nisso, podemos escrever as seguintes equações de recorrência:
Aqui, cada equação expressa o fato de que para uma sequência terminar com um certo número, o número anterior tem que ser um dos permitidos conforme discutimos.

Passo 6

Essas equações formam um sistema de recorrência que podemos usar para calcular o número de sequências para qualquer tamanho , começando com condições iniciais apropriadas (como para ).

Resposta

O sistema de equações de recorrência é:

Exercícios relacionados

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?
Reveja a definição de Números de Bell no Corolário 3.1.8. Mostre a seguinte recorrência:
Dica: note que o número de Bell é o número de possíveis relações de equivalência um conjunto , sendo . Fixe então um elemento de e denote por o número de elementos da classe de equivalência que contém esse elemento.
Encontre uma recorrência para , o número de sequências de letras dentre ou , que não têm letras vizinhas.
Seja o número de permutações caóticas de . Sem usar a fórmula para , deduza a equação de recorrência