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

 

Logo


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

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

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.

License Agreements, Terms of Use, Privacy Policy .

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