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,3

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

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

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

Prog

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

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.

Sequence in context: A325508 A238439 A121880 * A323445 A307768 A370583

Adjacent sequences: A094533 A094534 A094535 * A094537 A094538 A094539

Keyword

nonn,easy

Author

N. J. A. Sloane, Jun 06 2004

Extensions

More terms from Farideh Firoozbakht, Jun 10 2004

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

Status

approved