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,4

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.

Links

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

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.

Example

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

Prog

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

Crossrefs

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

Sequence in context: A301138 A008136 A357060 * A047196 A009889 A334706

Adjacent sequences: A254125 A254126 A254127 * A254129 A254130 A254131

Keyword

nonn,base,easy

Author

Peter Kagey, Jan 25 2015

Status

approved