A019308 -id:A019308 - cp's OEIS frontend

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

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, 4600578044, 9201156088

Offset: 0

N. J. A. Sloane

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

			Bi-fix free words of lengths 1 through 4:
0, 1
10, 01
100, 110, 011, 001
1000, 1100, 1110, 0111, 0011, 0001.

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).

Alois P. Heinz, Table of n, a(n) for n = 0..3323 (first 501 terms from T. D. Noe)
E. Barcucci, A. Bernini, S. Bilotta and 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 [math.CO], 2015-2016.
Daniel Gabric and Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
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]
Jakob Radoszewski, Wojciech Rytter, and Tomasz Waleń, Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words, Int'l Symp. String Proc. Info. Retrieval (2024), Springer, Cham, LNCS Vol. 14899, 257-271.
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 [math.CO], 2015.
Sarah Nibs, Java program for this sequence and A122536.

Equals 2 * A045690 for n > 0. Complement gives A094536.

Cf. A019308, A019309, A094537, A242430.

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

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 *)

a(2*n+1) = 2*a(2*n), a(2*n) = 2*a(2*n-1) - a(n).
a(n)/2^n converges to A242430.
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

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

A019309 Number of "bifix-free" words of length n over a four-letter alphabet.

Original entry on oeis.org

1, 4, 12, 48, 180, 720, 2832, 11328, 45132, 180528, 721392, 2885568, 11539440, 46157760, 184619712, 738478848, 2953870260, 11815481040, 47261743632, 189046974528, 756187176720, 3024748706880, 12098991941952

Offset: 0

Jeffrey Shallit

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.
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.

Cf. A003000, A019308, A094547, A094559, A094578.

a[0]=1; a[n_]:=a[n]=4*a[n-1]-If[EvenQ[n], a[n/2], 0] (* Ed Pegg Jr, Jan 05 2005 *)

a(2n+1) = 4a(2n); a(2n) = 4a(2n-1) - a(n).

A262312 The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.

Original entry on oeis.org

7, 3, 2, 2, 1, 3, 1, 5, 9, 7, 8, 2, 1, 1, 0, 8, 8, 7, 6, 2, 3, 3, 2, 8, 5, 9, 6, 4, 1, 5, 6, 9, 7, 4, 4, 7, 4, 4, 4, 9, 4, 0, 1, 0, 2, 0, 0, 6, 5, 1, 5, 4, 6, 7, 9, 2, 3, 6, 8, 8, 1, 1, 1, 4, 8, 8, 7, 8, 5, 0, 6, 2, 2, 1, 4, 7, 6, 7, 2, 3, 7

Offset: 0

Danny Rorabaugh, Sep 17 2015

Word W over alphabet L is an instance of "aba" provided there exists a nonerasing monoid homomorphism f:{a,b}*->L* such that f(W)=aba. For example "oompaloompa" is an instance of "aba" via the homomorphism defined by f(a)=oompa, f(b)=l. For a proof of the formula or more information on Zimin words, see Rorabaugh (2015).
The second definition comes from a Comment in A094536: "The probability that a random, infinite binary string begins with an even-length palindrome is: lim n -> infinity a(n)/2^n ~ 0.7322131597821108... . - Peter Kagey, Jan 26 2015"
Also, the limit, as word-length approaches infinity, of the probability that a random binary word has a bifix; that is, 1-x where x is the constant from A242430. - Danny Rorabaugh, Feb 13 2016

			0.7322131597821108876233285964156974474449401020065154679236881114887...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.17, p. 369.

Danny Rorabaugh, Table of n, a(n) for n = 0..1000
Danny Rorabaugh, Toward the Combinatorial Limit Theory of Free Words, arXiv:1509.04372 [math.CO], 2015, University of South Carolina, ProQuest Dissertations Publishing (2015). See section 5.1.

Cf. A003000, A094536, A123121, A242430, A262313 (abacaba).

N(sum([2*(1/4)^(2^j)*(-1)^j/prod([1-2*(1/4)^(2^k) for k in range(j+1)]) for j in range(8)]),digits=81) #For more than 152 digits of accuracy, increase the j-range.

The constant is Sum_{n>=0} A003000(n)*(1/4)^n.
Using the recursive definition of A003000, one can derive the series Sum_{j>=0} 2*(-1)^j*(1/4)^(2^j)/(Product_{k=0..j} 1-2*(1/4)^(2^k)), which converges more quickly to the same limit and without having to calculate terms of A003000.
For ternary words, the constant is Sum_{n>=0} A019308(n)*(1/9)^n.
For quaternary words, the constant is Sum_{n>=0} A019309(n)*(1/16)^n.

A094559 Number of words of length n over an alphabet of size 4 that are not "bifix-free".

Original entry on oeis.org

0, 0, 4, 16, 76, 304, 1264, 5056, 20404, 81616, 327184, 1308736, 5237776, 20951104, 83815744, 335262976, 1341097036, 5364388144, 21457733104, 85830932416, 343324451056, 1373297804224, 5493194102464, 21972776409856, 87891117178864

Offset: 0

N. J. A. Sloane, Jun 06 2004

See A019308, A019309 and A003000 for much more information. Cf. A094578.

a:=proc(n) if n=0 or n=1 then 0 elif n mod 2 = 0 then 4*a(n-1)-a(n/2)+4^(n/2) else 4*a(n-1) fi end: seq(a(n),n=0..28); # Emeric Deutsch, Feb 04 2006

Equals 4^n - A019309(n).

a(0)=a(1)=0, a(2n)=4^n + 4a(2n-1) - a(n), a(2n+1)=4a(2n). - Emeric Deutsch, Feb 04 2006

More terms from Emeric Deutsch, Feb 04 2006

A094538 Number of ternary words of length n that are not "bifix-free".

Original entry on oeis.org

0, 0, 3, 9, 33, 99, 315, 945, 2883, 8649, 26091, 78273, 235233, 705699, 2118339, 6355017, 19068729, 57206187, 171629595, 514888785, 1544699313, 4634097939, 13902392691, 41707178073, 125121830427, 375365491281

Offset: 0

N. J. A. Sloane, Jun 06 2004

See A019308 and A003000 for much more information. Cf. A094539.

Equals 3^n - A019308(n).

A094539 a(n) = A094538(n)/3.

Original entry on oeis.org

0, 0, 1, 3, 11, 33, 105, 315, 961, 2883, 8697, 26091, 78411, 235233, 706113, 2118339, 6356243, 19068729, 57209865, 171629595, 514899771, 1544699313, 4634130897, 13902392691, 41707276809, 125121830427, 375365787489, 1126097362467

Offset: 0

N. J. A. Sloane, Jun 06 2004

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A003000, A019308, A094538.

a[0] = 1; a[n_] := a[n] = 3*a[n - 1] - If[EvenQ[n], a[n/2], 0]; Insert[Table[(3^(n) - a[n])/3, {n, 1, 30}], 0, 1] (* Stefan Steinerberger, Mar 24 2006 *)

More terms from Stefan Steinerberger, Mar 24 2006

A342239 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that are bifix free; n >= 1, k >= 1.

Original entry on oeis.org

1, 2, 0, 3, 2, 0, 4, 6, 4, 0, 5, 12, 18, 6, 0, 6, 20, 48, 48, 12, 0, 7, 30, 100, 180, 144, 20, 0, 8, 42, 180, 480, 720, 414, 40, 0, 9, 56, 294, 1050, 2400, 2832, 1242, 74, 0, 10, 72, 448, 2016, 6300, 11900, 11328, 3678, 148, 0, 11, 90, 648, 3528, 14112, 37620, 59500, 45132, 11034, 284, 0

Offset: 1

Peter Kagey, Mar 06 2021

			Table begins:
n\k | 1  2   3    4     5      6       7        8         9
----+------------------------------------------------------
  1 | 1  0   0    0     0      0       0        0         0
  2 | 2  2   4    6    12     20      40       74       148
  3 | 3  6  18   48   144    414    1242     3678     11034
  4 | 4 12  48  180   720   2832   11328    45132    180528
  5 | 5 20 100  480  2400  11900   59500   297020   1485100
  6 | 6 30 180 1050  6300  37620  225720  1353270   8119620
  7 | 7 42 294 2016 14112  98490  689430  4823994  33767958
  8 | 8 56 448 3528 28224 225344 1802752 14418488 115347904

Peter Kagey, Antidiagonals n = 1..100, flattened

Rows: A003000 (n=2), A019308 (n=3), A019309 (n=4).

Columns: A002378 (k=1), A045991 (k=2), A047927 (k=3).

T(n,0)    = n.
T(n,2k)   = n*T(n,2k-1) - T(n,k).
T(n,2k+1) = n*T(n,2k).

A045694 Number of ternary words of length n (beginning with 0) with autocorrelation function 2^(n-1).

Original entry on oeis.org

1, 2, 6, 16, 48, 138, 414, 1226, 3678, 10986, 32958, 98736, 296208, 888210, 2664630, 7992664, 23977992, 71930298, 215790894, 647361696, 1942085088, 5826222306, 17478666918, 52435902018, 157307706054, 471922821954, 1415768465862

Offset: 1

TORSTEN.SILLKE(AT)LHSYSTEMS.COM

Equals A019308/3.

a:=proc(n) if n=1 then 1 elif n mod 2 = 0 then 3*a(n-1)-a(n/2) else 3*a(n-1) fi end: seq(a(n),n=1..31); # Emeric Deutsch, Aug 08 2005

a(2n) = 3*a(2n-1) - a(n) for n >= 1; a(2n+1) = 3*a(2n) for n >= 1.

More terms from Emeric Deutsch, Aug 08 2005

A330651 a(n) = n^4 + 3n^3 + 2n^2 - 2*n.

Original entry on oeis.org

0, 4, 44, 174, 472, 1040, 2004, 3514, 5744, 8892, 13180, 18854, 26184, 35464, 47012, 61170, 78304, 98804, 123084, 151582, 184760, 223104, 267124, 317354, 374352, 438700, 511004, 591894, 682024, 782072, 892740, 1014754, 1148864, 1295844

Offset: 0

Ed Pegg Jr, Jan 15 2020

a(n)/A269657(n) gives unforgeable word approximations (A003000) with increasing accuracy, as follows: 4/15, 44/79, 174/253, ... ~ 0.26 (A242430), 0.5569 (A019308), 0.68774 (A019309), 0.8055770, 0.83674321, 0.85937882, 0.87654509, 0.89000100, 0.9008270111, ....

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A269657, A242430, A003000, A019308, A019309.

A330651 := n -> (((n+3)*n+2)*n-2)*n; # M. F. Hasler, Feb 29 2020

Numerator/@Table[(-2 n+2 n^2+3 n^3+n^4)/(1+3 n+6 n^2+4 n^3+n^4),{n,0,33}] (* Ed Pegg Jr, Jan 15 2020 *)

Vec(2*x*(2 + 12*x - 3*x^2 + x^3) / (1 - x)^5 + O(x^40),-40) \\ Colin Barker, Jan 15 2020

apply( {A330651(n)=(((n+3)*n+2)*n-2)*n}, [0..44]) \\ M. F. Hasler, Feb 29 2020

From Colin Barker, Jan 15 2020: (Start)
G.f.: 2*x*(2 + 12*x - 3*x^2 + x^3) / (1 - x)^5.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>5.
(End)
E.g.f.: exp(x)*x*(4 + 18*x + 9*x^2 + x^3). - Stefano Spezia, Feb 03 2020

A182024 Size of the set CBFS_2(n) of cross-bifix-free binary words of length n.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 14, 23, 42, 72, 132, 227, 429

Offset: 3

N. J. A. Sloane, Apr 06 2012

nonn

S. Bilotta, E. Pergola and R. Pinzani, A new approach to cross-bifix-free sets, arXiv preprint arXiv:1112.3168, 2011

Cf. A003000, A019308, A019309.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A019309 Number of "bifix-free" words of length n over a four-letter alphabet.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A262312 The limit, as word-length approaches infinity, of the probability that a random binary word is an instance of the Zimin pattern "aba"; also the probability that a random infinite binary word begins with an even-length palindrome.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Sage

Formula

A094559 Number of words of length n over an alphabet of size 4 that are not "bifix-free".

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

Extensions

A094538 Number of ternary words of length n that are not "bifix-free".

Views

Author

Keywords

Crossrefs

Formula

A094539 a(n) = A094538(n)/3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A342239 Table read by upward antidiagonals: T(n,k) is the number of strings of length k over an n-letter alphabet that are bifix free; n >= 1, k >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A045694 Number of ternary words of length n (beginning with 0) with autocorrelation function 2^(n-1).

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

Extensions

A330651 a(n) = n^4 + 3*n^3 + 2*n^2 - 2*n.

Views

Author

A330651 a(n) = n^4 + 3n^3 + 2n^2 - 2*n.