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 com tamanho 2 (cada uma tem só um vizinho proibido), quasi-endpoints com tamanho 2 (cada uma tem dois vizinhos, um em e um em ) e médios com tamanho 22 (cada uma tem dois vizinhos em ). Vamos calcular quantas transições válidas há de cada categoria para cada categoria.
Passo 3
Montamos a matriz de transição , em cuja entrada está o número de letras da categoria que podemos escolher depois de uma letra da categoria . O resultado é
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á