Question

Um palíndromo é uma seqüência no qual a sua inversa é idêntica à seqüência. Por exemplo, as cadeias de bits “1001” e “0110110” são palíndromos. Quantas cadeias de bits de tamanho n são palíndromos?​

Answer 1

Utilizando lógica de construção para análises combinatórias, temos ao todo$2^{\frac{n}{2}}$forma diferentes de criar palindromos de n digitos.

Explicação:

Note que para uma cadeia de bits ser um palindromo, então sua primeira metade tem de ser igual a sua segunda metade, então não importa quantas formas façamos a segunda metade, desde que esta seja igual a primeira metade.

Assim levando em consideração para a conta somente a primeira metade da conta, então temos n/2 espaços para colocarmos 0s ou 1s, então cada espaço tem 2 opções, pode ser 0 ou 1, então a combinação de quantos palindromos temos é dado por:

2.2.2.2.2.2.... (até a casa de posição n/2)

Ou seja, ao todo temos:

$2^{\frac{n}{2}}$

Sendo n um número inteiro. No caso de n ser um número impar, basta arredondar n/2 para baixo, para pegar a primeira metade da mesma forma.