This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet. (Formerly M0328) 21
 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 (list; graph; refs; listen; history; text; internal format)
 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 T. D. Noe, Table of n, a(n) for n = 0..500 E. Barcucci, A. Bernini, S. Bilotta, 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 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, 2015 Guy P. Srinivasan, Java program for this sequence and A122536 FORMULA a(2n+1) = 2*a(2*n), a(2*n) = 2*a(2*n-1) - a(n). A003000[n]/2^n converges to 0.2677868402178891123766714035843025525550598979934845320763118885112149... 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. Sequence in context: A001679 A030435 A063886 * A216957 A122536 A238014 Adjacent sequences:  A002997 A002998 A002999 * A003001 A003002 A003003 KEYWORD nonn,easy,nice AUTHOR 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

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

Last modified August 14 17:44 EDT 2018. Contains 313751 sequences. (Running on oeis4.)