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