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

%I #34 Jan 27 2015 01:14:14

%S 0,0,2,4,10,20,44,88,182,364,740,1480,2980,5960,11960,23920,47914,

%T 95828,191804,383608,767500,1535000,3070568,6141136,12283388,24566776,

%U 49135784,98271568,196547560,393095120,786199088,1572398176,3144813974

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

%C 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 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 Peter Kagey, <a href="/A094536/b094536.txt">Table of n, a(n) for n = 0..1000</a>

%F a(n) = 2^n - A003000(n).

%F 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 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 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 a[0]:= 0:

%p for n from 1 to 100 do

%p if n::odd then a[n]:= 2*a[n-1]

%p else a[n]:= 2*a[n-1] + 2^(n/2) - a[n/2]

%p fi

%p od:

%p seq(a[i],i=0..100); # _Robert Israel_, Jan 12 2015

%t 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 (Ruby)

%o s = [0,0]

%o (2..N).each { |n| s << 2 * s[-1] + (n.odd? ? 0 : 2**(n/2) - s[n/2]) }

%Y See A003000 for much more information.

%Y Cf. A094537.

%Y A254128(n) gives the number of binary strings of length n that begin with an odd-length palindrome.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Jun 06 2004

%E More terms from _Farideh Firoozbakht_, Jun 10 2004

%E Corrected by Don Rogers (donrogers42(AT)aol.com), Feb 15 2005