|
| |
|
|
A003000
|
|
Number of "bifix-free" words of length n over a two-letter alphabet.
(Formerly M0328)
|
|
12
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| 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 (callan(AT)stat.wisc.edu), Sep 25 2006
|
|
|
REFERENCES
| G. Blom, Problem 94-20: Overlapping binary sequences, SIAM Review 37 (1995), 619-620.
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\"ocken, J. f\"ur Reine Angewandte Math. 271 (1974), 139-154, see p. 143.
M. Lothaire, Combinatorics on Words, Cambridge University Press, NY, 1997.
P. Tolstrup Nielsen, A note on bifix-free sequences, IEEE Trans. Info. Theory IT-19 (1973), 704-706.
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
D. J. Greaves and S. J. Montgomery-Smith, Unforgeable Marker Sequences.
T. Harju and D. Nowotka, Border correlation of binary words.
Guy P. Srinivasan, Java program for this sequence and A122536
|
|
|
FORMULA
| a(2n+1) = 2a(2n), a(2n) = 2a(2n-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 (mymontain(AT)yahoo.com), Jun 10 2004
|
|
|
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., (ed(AT)mathpuzzle.com), Jan 05 2005)
|
|
|
CROSSREFS
| Equals 2 * A045690 for n > 0. Complement gives A094536. Cf. A019308, A019309, A094536, A094537.
Cf. A094536, A094537.
Sequence in context: A001679 A030435 A063886 * A122536 A052953 A128209
Adjacent sequences: A002997 A002998 A002999 * A003001 A003002 A003003
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
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 (mymontain(AT)yahoo.com), Jun 10 2004
|
| |
|
|
