login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A254128 Number of binary strings of length n that begin with an odd-length palindrome. 3
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 (list; graph; refs; listen; history; text; internal format)
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: A156303 A301138 A008136 * A047196 A009889 A334706

Adjacent sequences:  A254125 A254126 A254127 * A254129 A254130 A254131

KEYWORD

nonn,base,easy

AUTHOR

Peter Kagey, Jan 25 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 20:00 EDT 2022. Contains 353957 sequences. (Running on oeis4.)