• 29 - Quantas sequências de quatro letras é possível formar tal que nenhum par de letras seja consecutivo?

Passo 1

A gente quer formar sequências de quatro letras do alfabeto (26 letras) de modo que nenhuma dupla de letras adjacentes na sequência seja consecutiva no alfabeto. O conteúdo aqui é contagem de sequências com restrição de vizinhança, e vamos usar uma abordagem de estados com recursão/matriz de transição para lidar com a dependência entre posições.

Passo 2

Classificamos as letras em três categorias: endpoints E=A,Z com tamanho 2 (cada uma tem só um vizinho proibido), quasi-endpoints B=B,Y com tamanho 2 (cada uma tem dois vizinhos, um em E e um em M) e médios M=C,dots,X com tamanho 22 (cada uma tem dois vizinhos em M). Vamos calcular quantas transições válidas há de cada categoria para cada categoria.

Passo 3

Montamos a matriz de transição T, em cuja entrada Tij está o número de letras da categoria j que podemos escolher depois de uma letra da categoria i. O resultado é
T = 2 & 1 & 22 1 & 2 & 21 2 & 1 & 21
onde as linhas/colunas seguem a ordem E,B,M.

Passo 4

O vetor inicial S registra quantas escolhas temos para a primeira letra em cada categoria:
S = [2, 2, 22]
Multiplicando S por T obtemos o vetor v2 que conta sequências de comprimento 2 acabando em cada categoria:
v2 = S,T = [50, 28, 548]

Passo 5

Para sequências de comprimento 3, multiplicamos novamente:
v3 = v2,T = [1224, 654, 13196]

Passo 6

Para sequências de comprimento 4, fazemos mais uma multiplicação:
v4 = v3,T = [29494, 15728, 317778]

Passo 7

A resposta final é a soma das três componentes de v4, que dá
29494 + 15728 + 317778 = 363000

Resposta

363000

Exercícios relacionados