login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A094536 Number of binary words of length n that are not "bifix-free". 8
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 (list; graph; refs; listen; history; text; internal format)
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 A297183

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)