cp's OEIS Frontend

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

%I A254128 #20 Mar 24 2017 00:47:57
%S A254128 0,0,0,4,8,20,40,88,176,364,728,1480,2960,5960,11920,23920,47840,
%T A254128 95828,191656,383608,767216,1535000,3070000,6141136,12282272,24566776,
%U A254128 49133552,98271568,196543136,393095120,786190240,1572398176,3144796352,6289627948,12579255896
%N A254128 Number of binary strings of length n that begin with an odd-length palindrome.
%C A254128 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).
%C A254128 '1011' is an example of a string that begins with an odd-length palindrome: the palindrome '101', which is of length 3.
%C A254128 '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'.)
%C A254128 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.
%H A254128 Peter Kagey, <a href="/A254128/b254128.txt">Table of n, a(n) for n = 0..1000</a>
%F A254128 a(2*n) = 2*a(2*n-1) = A094536(2*n) - A003000(n) for all n > 0.
%F A254128 a(2*n+1) = 2*a(2*n) + 2^(n+1) - a(n+1) = A094536(2*n+1) for all n.
%e A254128 For n = 4 the a(3) = 8 solutions are: 0000 0001 0100 0101 1010 1011 1110 1111.
%o A254128 (Ruby)
%o A254128 s = [0, 0]
%o A254128 (2..N).each { |n| s << 2 * s[-1] + (n.even? ? 0 : 2**(n/2+1) - s[n/2+1]) }
%Y A254128 Cf. A003000. A094536 is the analogous sequence for even-length palindromes.
%K A254128 nonn,base,easy
%O A254128 0,4
%A A254128 _Peter Kagey_, Jan 25 2015