1
$\begingroup$

Derive the number of all even length palindromic sequences with length $\leq n$.

If $n=4$, I have to count the number of non-palindromes of length 0, 2, and 4.

Also, $2p = n$, so a string of length $n = 4$ has $p = 2$. This comes in handy later.

$x$ represents the number of possible characters in the given alphabet- so $x = 26$ for English, 2 for binary, etc.

I chose to approach by counting, using this thought process.

$$\sum_{k=0}^{p} (x^{2k} - x^k)$$ In other words - a summation of all possible even length strings up to length $n$, subtracting cases that are palindromes.

I tested this with binary, up to length 4. (Binary non-palindromes of length 0, 2, and 4). This means $p$ goes from 0, to 1, to 2.

This evaluates to: $$ 2^0 - 2^0 +$$ $$2^2 - 2^1 + $$ $$2^4 - 2^2$$

Which sums to a total of 14 non palindromes.

All possible combinations are {}, 11, 00, 10, 01, 1111, 1100, 1000, 0000, 0001, 0011, 0111, 1010, 0101, 0110, 1001 1110, 1101, 0010, 1011, 0100.

14 of these are not palindromes, confirming my approach.

The solution states the formula is $$\frac{x^{2p+1}-2x^{p+1}+x}{x-1}$$ Following the same logic...

With $p = 2$, $x = 2$, $n = 4$, we have

$$\frac{2^{4+1}-2(2)^{3}+2}{2-1}$$

Which works out to 18, not 14. I have worked this out several times, and I'm not exactly sure what/if I am misunderstanding. Any help would be greatly appreciated. Thanks!

$\endgroup$
2
$\begingroup$

A palindrome is a sequence of characters that reads the same forwards as backwards.

If the sequence has even length, say $n = 2k$, selecting the first $k$ characters completely determines the palindrome since the remaining $k$ characters can be found by repeating the sequence in the reverse order. Hence, the number of palindromes of even length at most $n$ in an alphabet with $x$ characters is $$x^0 + x^1 + x^2 + x^3 + \cdots + x^k = \frac{1 - x^{k + 1}}{1 - x}$$ where we have used the formula for the sum of a geometric series with initial term $1$ and common ratio $x$.

In your example of binary sequences of even length at most $4$, there are seven palindromes: $$\emptyset, 00, 11, 0000, 0110, 1001, 1111$$ Notice that our formula yields $$2^0 + 2^1 + 2^2 = 1 + 2 + 4 = 7$$ or $$\frac{1 - 2^{2 + 1}}{1 - 2} = \frac{1 - 2^3}{-1} = \frac{-7}{-1} = 7$$

Since there are a total of $$x^0 + x^2 + x^4 + \ldots + x^{2k} = \frac{1 - x^{2k + 2}}{1 - x^2}$$ sequences of even length at most $n = 2k$ in an alphabet with $x$ characters, the number of sequences of even length at most $n = 2k$ that are not palindromes is \begin{align*} \frac{1 - x^{2k + 2}}{1 - x^2} - \frac{1 - x^{k + 1}}{1 - x} & = \frac{1 - x^{2k + 2}}{1 - x^2} - \frac{1 - x^{k + 1}}{1 - x} \cdot \frac{1 + x}{1 + x}\\ & = \frac{1 - x^{2k + 2}}{1 - x^2} - \frac{1 + x - x^{k + 1} - x^{k + 2}}{1 - x^2}\\ & = \frac{-x + x^{k + 1} + x^{k + 2} - x^{2k + 2}}{1 - x^2} \end{align*} In your example of binary sequences of even length at most $4$, the total number of sequences is $$2^0 + 2^2 + 2^4 = 1 + 4 + 16 = 21$$ of which seven are palindromes, so there are $14$ non-palindromes as you found. Notice that our formulas yield $$\frac{1 - 2^{2 \cdot 2 + 2}}{1 - 2^2} = \frac{1 - 2^6}{1 - 2^2} = \frac{1 - 64}{1 - 4} = \frac{-63}{-3} = 21$$ total sequences and $$\frac{-2 + 2^{2 + 1} + 2^{2 + 2} - 2^{2 \cdot 2 + 2}}{1 - 2^2} = \frac{-2 + 2^3 + 2^4 - 2^6}{1 - 2^2} = {-2 + 8 + 16 - 64}{1 - 4} = \frac{-42}{-3} = 14$$ non-palindromes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.