A254128 Number of binary strings of length n that begin with an odd-length palindrome.

0, 0, 0, 4, 8, 20, 40, 88, 176, 364, 728, 1480, 2960, 5960, 11920, 23920, 47840, 95828, 191656, 383608, 767216, 1535000, 3070000, 6141136, 12282272, 24566776, 49133552, 98271568, 196543136, 393095120, 786190240, 1572398176, 3144796352, 6289627948, 12579255896

Offset: 0

Author

Peter Kagey, Jan 25 2015

Keywords

• nonn
• base
• easy

Comments

This sequence gives the number of binary strings of length n that begin with an odd-length palindrome (not including the trivial palindrome of length one).

'1011' is an example of a string that begins with an odd-length palindrome: the palindrome '101', which is of length 3.

'1101' is an example of a string that does not begin with an odd-length palindrome. (It does begin with the even-length palindrome '11'.)

The probability of a random infinite binary string beginning with an odd-length palindrome is given by: limit n -> infinity a(n)/(2^n), which is approximately 0.7322131597821109.

Examples

			For n = 4 the a(3) = 8 solutions are: 0000 0001 0100 0101 1010 1011 1110 1111.
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A003000. A094536 is the analogous sequence for even-length palindromes.

Programs

Ruby

s = [0, 0]
(2..N).each { |n| s << 2 * s[-1] + (n.even? ? 0 : 2**(n/2+1) - s[n/2+1]) }

Formula

a(2*n) = 2*a(2*n-1) = A094536(2*n) - A003000(n) for all n > 0.

a(2*n+1) = 2*a(2*n) + 2^(n+1) - a(n+1) = A094536(2*n+1) for all n.