cp's OEIS Frontend

A094536 Number of binary words of length n that are not "bifix-free".

%I A094536 #34 Jan 27 2015 01:14:14
%S A094536 0,0,2,4,10,20,44,88,182,364,740,1480,2980,5960,11960,23920,47914,
%T A094536 95828,191804,383608,767500,1535000,3070568,6141136,12283388,24566776,
%U A094536 49135784,98271568,196547560,393095120,786199088,1572398176,3144813974
%N A094536 Number of binary words of length n that are not "bifix-free".
%C A094536 Also the number of binary strings of length n that begin with an even length palindrome. (E.g., f(4) = 10 with strings 0000 0001 0010 0011 0110 1001 1100 1101 1110 1111.) - _Peter Kagey_, Jan 11 2015
%C A094536 The probability that a random, infinite binary string begins with an even-length palindrome is: lim n -> infinity a(n)/2^n ~ 0.7322131597821108... . - _Peter Kagey_, Jan 26 2015
%H A094536 Peter Kagey, <a href="/A094536/b094536.txt">Table of n, a(n) for n = 0..1000</a>
%F A094536 a(n) = 2^n - A003000(n).
%F A094536 Let b(0)=1; b(n) = 2*b(n-1) - 1/2*(1+(-1)^n)*b([n/2]); a(n) = 2^n - b(n). - _Farideh Firoozbakht_, Jun 10 2004
%F A094536 a(0) = 0; a(1) = 0; a(2*n+1) = 2*a(2*n); a(2*n) = 2*a(2*n-1) + 2^n - a(n). - _Peter Kagey_, Jan 11 2015
%F A094536 G.f. g(x) satisfies (1-2*x)*g(x) = 2*x^2/(1-2*x^2) - g(x^2). - _Robert Israel_, Jan 12 2015
%p A094536 a[0]:= 0:
%p A094536 for n from 1 to 100 do
%p A094536 if n::odd then a[n]:= 2*a[n-1]
%p A094536 else a[n]:= 2*a[n-1] + 2^(n/2) - a[n/2]
%p A094536 fi
%p A094536 od:
%p A094536 seq(a[i],i=0..100); # _Robert Israel_, Jan 12 2015
%t A094536 b[0]=1;b[n_]:=b[n]=2*b[n-1]-(1+(-1)^n)/2*b[Floor[n/2]]; a[n_]:=2^n-b[n];Table[a[n], {n, 0, 34}]
%o A094536 (Ruby)
%o A094536 s = [0,0]
%o A094536 (2..N).each { |n| s << 2 * s[-1] + (n.odd? ? 0 : 2**(n/2) - s[n/2]) }
%Y A094536 See A003000 for much more information.
%Y A094536 Cf. A094537.
%Y A094536 A254128(n) gives the number of binary strings of length n that begin with an odd-length palindrome.
%K A094536 nonn,easy
%O A094536 0,3
%A A094536 _N. J. A. Sloane_, Jun 06 2004
%E A094536 More terms from _Farideh Firoozbakht_, Jun 10 2004
%E A094536 Corrected by Don Rogers (donrogers42(AT)aol.com), Feb 15 2005