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

%I M0328 #113 Sep 29 2024 09:19:55

%S 1,2,2,4,6,12,20,40,74,148,284,568,1116,2232,4424,8848,17622,35244,

%T 70340,140680,281076,562152,1123736,2247472,4493828,8987656,17973080,

%U 35946160,71887896,143775792,287542736,575085472,1150153322,2300306644,4600578044,9201156088

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

%C 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 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 Also the number of binary "prime palstars" of length 2n (Rampersad, Shallit, & Wang 2011). - _Jeffrey Shallit_, Aug 14 2014

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

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

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

%H 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 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 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 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 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 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 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 D. J. Greaves and S. J. Montgomery-Smith, <a href="http://faculty.missouri.edu/~stephen/preprints/unforgeable.html">Unforgeable Marker Sequences</a>.

%H 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 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 T. Harju and D. Nowotka, <a href="http://www.tucs.fi/Publications/attachment.php?fname=TR546.pdf">Border correlation of binary words</a>.

%H 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 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 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 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 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 Guy P. Srinivasan, <a href="/A122536/a122536.txt">Java program for this sequence and A122536</a>.

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

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

%F a(0)=1; a(n)=2*a(n-1)-(1/2)*(1+(-1)^n)*a([n/2]). - _Farideh Firoozbakht_, Jun 10 2004

%F G.f.: g(x) satisfies (1-2*x)*g(x) = 2 - g(x^2). - _Robert Israel_, Jan 12 2015

%e Bi-fix free words of lengths 1 through 4:

%e 0, 1

%e 10, 01

%e 100, 110, 011, 001

%e 1000, 1100, 1110, 0111, 0011, 0001.

%p A[0]:= 1:

%p for n from 1 to 100 do

%p if n::odd then A[n]:= 2*A[n-1] else A[n]:= 2*A[n-1]-A[n/2] fi

%p od:

%p seq(A[n],n=0..100); # _Robert Israel_, Aug 14 2014

%t 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 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 Equals 2 * A045690 for n > 0. Complement gives A094536.

%Y Cf. A019308, A019309, A094537, A242430.

%K nonn,easy,nice

%O 0,2

%A _N. J. A. Sloane_

%E New description and reference from _Jeffrey Shallit_, Sep 15 1996

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

%E More terms from _Farideh Firoozbakht_, Jun 10 2004