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

0, 0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1480, 2980, 5960, 11960, 23920, 47914, 95828, 191804, 383608, 767500, 1535000, 3070568, 6141136, 12283388, 24566776, 49135784, 98271568, 196547560, 393095120, 786199088, 1572398176, 3144813974

Offset: 0

Author

N. J. A. Sloane, Jun 06 2004

Keywords

• nonn
• easy

Comments

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

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

Links

• Peter Kagey, Table of n, a(n) for n = 0..1000

Crossrefs

See A003000 for much more information.

Cf. A094537.

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

Programs

Maple

a[0]:= 0:
for n from 1 to 100 do
if n::odd then a[n]:= 2*a[n-1]
else a[n]:= 2*a[n-1] + 2^(n/2) - a[n/2]
fi
od:
seq(a[i],i=0..100); # Robert Israel, Jan 12 2015

Mathematica

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}]

Ruby

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

Formula

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

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

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

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

Extensions

More terms from Farideh Firoozbakht, Jun 10 2004

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