cp's OEIS Frontend

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

%I A003000 M0328 #114 Jun 14 2025 17:15:23
%S A003000 1,2,2,4,6,12,20,40,74,148,284,568,1116,2232,4424,8848,17622,35244,
%T A003000 70340,140680,281076,562152,1123736,2247472,4493828,8987656,17973080,
%U A003000 35946160,71887896,143775792,287542736,575085472,1150153322,2300306644,4600578044,9201156088
%N A003000 Number of bifix-free (or primary, or unbordered) words of length n over a two-letter alphabet.
%C A003000 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
%C A003000 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
%C A003000 Also the number of binary "prime palstars" of length 2n (Rampersad, Shallit, & Wang 2011). - _Jeffrey Shallit_, Aug 14 2014
%D A003000 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 28.
%D A003000 M. Lothaire, Combinatorics on Words, Cambridge University Press, NY, 1997, see p. 153.
%D A003000 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003000 Alois P. Heinz, <a href="/A003000/b003000.txt">Table of n, a(n) for n = 0..3323</a> (first 501 terms from T. D. Noe)
%H A003000 E. Barcucci, A. Bernini, S. Bilotta and R. Pinzani, <a href="http://arxiv.org/abs/1502.05275">Cross-bifix-free sets in two dimensions</a>, arXiv preprint arXiv:1502.05275 [cs.DM], 2015.
%H A003000 S. Bilotta, E. Pergola and R. Pinzani, <a href="http://arxiv.org/abs/1112.3168">A new approach to cross-bifix-free sets</a>, arXiv preprint arXiv:1112.3168 [cs.FL], 2011.
%H A003000 G. Blom, <a href="http://dx.doi.org/10.1137/1037139">Problem 94-20: Overlapping binary sequences</a>, SIAM Review 37 (1995), 619-620.
%H A003000 Joshua Cooper and Danny Rorabaugh, <a href="http://arxiv.org/abs/1510.03917">Asymptotic Density of Zimin Words</a>, arXiv preprint arXiv:1510.03917 [math.CO], 2015-2016.
%H A003000 Daniel Gabric and Jeffrey Shallit, <a href="https://arxiv.org/abs/1906.03689">Borders, Palindrome Prefixes, and Square Prefixes</a>, arXiv:1906.03689 [cs.DM], 2019.
%H A003000 O. Georgiou, C. P. Dettmann and E. G. Altmann, <a href="http://arxiv.org/abs/1207.7000">Faster than expected escape for a class of fully chaotic maps</a>, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
%H A003000 D. J. Greaves and S. J. Montgomery-Smith, <a href="http://faculty.missouri.edu/~stephen/preprints/unforgeable.html">Unforgeable Marker Sequences</a>.
%H A003000 L. J. Guibas and A. M. Odlyzko, <a href="http://dx.doi.org/10.1016/0097-3165(81)90038-8">Periods in Strings</a>, Journal of Combinatorial Theory A 30 (1981) 19-42. Their L_n(0) is A003000(n).
%H A003000 H. Harborth, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN243919689_0271&amp;DMDID=DMDLOG_0012&amp;IDDOC=256062">Endliche 0-1-Folgen mit gleichen Teilblöcken</a>, J. für Reine Angewandte Math. 271 (1974), 139-154, see p. 143.
%H A003000 T. Harju and D. Nowotka, <a href="http://www.tucs.fi/Publications/attachment.php?fname=TR546.pdf">Border correlation of binary words</a>.
%H A003000 P. Tolstrup Nielsen, <a href="http://dx.doi.org/10.1109/TIT.1973.1055065">A note on bifix-free sequences</a>, IEEE Trans. Info. Theory IT-19 (1973), 704-706. [<a href="http://orbit.dtu.dk/files/4640005/Tolstrup.pdf">pdf</a>]
%H A003000 Jakob Radoszewski, Wojciech Rytter, and Tomasz Waleń, <a href="https://doi.org/10.1007/978-3-031-72200-4_20">Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words</a>, Int'l Symp. String Proc. Info. Retrieval (2024), Springer, Cham, LNCS Vol. 14899, 257-271.
%H A003000 N. Rampersad, J. Shallit, and M.-w. Wang, <a href="http://dx.doi.org/10.1016/j.ipl.2011.01.018">Inverse star, borders, and palstars</a>, Info. Proc. Letters 111 (2011), 420-422. - _Jeffrey Shallit_, Aug 14 2014
%H A003000 N. Rampersad, J. Shallit, and M.-w. Wang, <a href="http://arxiv.org/abs/1008.2440">Inverse star, borders, and palstars</a>, arXiv:1008.2440 [cs.FL], 2010.
%H A003000 D. Rorabaugh, <a href="http://arxiv.org/abs/1509.04372">Toward the Combinatorial Limit Theory of Free Words</a>, arXiv preprint arXiv:1509.04372 [math.CO], 2015.
%H A003000 Sarah Nibs, <a href="/A122536/a122536.txt">Java program for this sequence and A122536</a>.
%F A003000 a(2*n+1) = 2*a(2*n), a(2*n) = 2*a(2*n-1) - a(n).
%F A003000 a(n)/2^n converges to A242430.
%F A003000 a(0)=1; a(n)=2*a(n-1)-(1/2)*(1+(-1)^n)*a([n/2]). - _Farideh Firoozbakht_, Jun 10 2004
%F A003000 G.f.: g(x) satisfies (1-2*x)*g(x) = 2 - g(x^2). - _Robert Israel_, Jan 12 2015
%e A003000 Bi-fix free words of lengths 1 through 4:
%e A003000 0, 1
%e A003000 10, 01
%e A003000 100, 110, 011, 001
%e A003000 1000, 1100, 1110, 0111, 0011, 0001.
%p A003000 A[0]:= 1:
%p A003000 for n from 1 to 100 do
%p A003000 if n::odd then A[n]:= 2*A[n-1] else A[n]:= 2*A[n-1]-A[n/2] fi
%p A003000 od:
%p A003000 seq(A[n],n=0..100); # _Robert Israel_, Aug 14 2014
%t A003000 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}]
%t A003000 a[0]=1; a[n_]:=a[n]=2*a[n-1]-If[EvenQ[n], a[n/2], 0] (* _Ed Pegg Jr_, Jan 05 2005 *)
%Y A003000 Equals 2 * A045690 for n > 0. Complement gives A094536.
%Y A003000 Cf. A019308, A019309, A094537, A242430.
%K A003000 nonn,easy,nice
%O A003000 0,2
%A A003000 _N. J. A. Sloane_
%E A003000 New description and reference from _Jeffrey Shallit_, Sep 15 1996
%E A003000 Additional comments from Torsten.Sillke(AT)lhsystems.com, Jan 17 2001
%E A003000 More terms from _Farideh Firoozbakht_, Jun 10 2004