A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet. (Formerly M0328)

1, 2, 2, 4, 6, 12, 20, 40, 74, 148, 284, 568, 1116, 2232, 4424, 8848, 17622, 35244, 70340, 140680, 281076, 562152, 1123736, 2247472, 4493828, 8987656, 17973080, 35946160, 71887896, 143775792, 287542736, 575085472, 1150153322, 2300306644, 4600578044, 9201156088

Offset

0,2

Comments

This is the number of binary words w of length n such that there is no nonempty word x, different from w, which is both a prefix and a suffix of w. - N. J. A. Sloane, Nov 09 2012

Many authors use the term "unbordered" for "bifix-free". The Lothaire (1997) reference refers to bifix-free words as primary words (Chapter 8). - David Callan, Sep 25 2006

Also the number of binary "prime palstars" of length 2n (Rampersad, Shallit, & Wang 2011). - Jeffrey Shallit, Aug 14 2014

References

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 28.

M. Lothaire, Combinatorics on Words, Cambridge University Press, NY, 1997, see p. 153.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..3323 (first 501 terms from T. D. Noe)

E. Barcucci, A. Bernini, S. Bilotta and R. Pinzani, Cross-bifix-free sets in two dimensions, arXiv preprint arXiv:1502.05275 [cs.DM], 2015.

S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, arXiv preprint arXiv:1112.3168 [cs.FL], 2011.

G. Blom, Problem 94-20: Overlapping binary sequences, SIAM Review 37 (1995), 619-620.

Joshua Cooper and Danny Rorabaugh, Asymptotic Density of Zimin Words, arXiv preprint arXiv:1510.03917 [math.CO], 2015-2016.

Daniel Gabric and Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.

O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From N. J. A. Sloane, Dec 23 2012

D. J. Greaves and S. J. Montgomery-Smith, Unforgeable Marker Sequences.

L. J. Guibas and A. M. Odlyzko, Periods in Strings, Journal of Combinatorial Theory A 30 (1981) 19-42. Their L_n(0) is A003000(n).

H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Reine Angewandte Math. 271 (1974), 139-154, see p. 143.

T. Harju and D. Nowotka, Border correlation of binary words.

P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706. [pdf]

N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, Info. Proc. Letters 111 (2011), 420-422. - Jeffrey Shallit, Aug 14 2014

N. Rampersad, J. Shallit, and M.-w. Wang, Inverse star, borders, and palstars, arXiv:1008.2440 [cs.FL], 2010.

D. Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv preprint arXiv:1509.04372 [math.CO], 2015.

Guy P. Srinivasan, Java program for this sequence and A122536.

Formula

a(2*n+1) = 2*a(2*n), a(2*n) = 2*a(2*n-1) - a(n).

a(n)/2^n converges to A242430.

a(0)=1; a(n)=2*a(n-1)-(1/2)*(1+(-1)^n)*a([n/2]). - Farideh Firoozbakht, Jun 10 2004

G.f.: g(x) satisfies (1-2*x)*g(x) = 2 - g(x^2). - Robert Israel, Jan 12 2015

Example

Bi-fix free words of lengths 1 through 4:
0, 1
10, 01
100, 110, 011, 001
1000, 1100, 1110, 0111, 0011, 0001.

Maple

A[0]:= 1:
for n from 1 to 100 do
if n::odd then A[n]:= 2*A[n-1] else A[n]:= 2*A[n-1]-A[n/2] fi
od:
seq(A[n], n=0..100); # Robert Israel, Aug 14 2014

Mathematica

a[0]=1; a[n_]:=a[n]=2*a[n-1]-(1+(-1)^n)/2*a[Floor[n/2]]; Table[a[n], {n, 0, 34}]
a[0]=1; a[n_]:=a[n]=2*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

Crossrefs

Equals 2 * A045690 for n > 0. Complement gives A094536.

Cf. A019308, A019309, A094537, A242430.

Sequence in context: A001679 A030435 A063886 * A216957 A122536 A238014

Adjacent sequences: A002997 A002998 A002999 * A003001 A003002 A003003

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

New description and reference from Jeffrey Shallit, Sep 15 1996

Additional comments from Torsten.Sillke(AT)lhsystems.com, Jan 17 2001

More terms from Farideh Firoozbakht, Jun 10 2004

Status

approved