A094537 -id:A094537 - 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

A350838 Heinz numbers of partitions with no adjacent parts of quotient 2.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 64, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83

Offset: 1

Gus Wiseman, Jan 18 2022

nonn

Differs from A320340 in having 105: (4,3,2), 315: (4,3,2,2), 455: (6,4,3), etc.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are numbers with no adjacent prime indices of quotient 1/2.

			The terms and their prime indices begin:
      1: {}            19: {8}             38: {1,8}
      2: {1}           20: {1,1,3}         39: {2,6}
      3: {2}           22: {1,5}           40: {1,1,1,3}
      4: {1,1}         23: {9}             41: {13}
      5: {3}           25: {3,3}           43: {14}
      7: {4}           26: {1,6}           44: {1,1,5}
      8: {1,1,1}       27: {2,2,2}         45: {2,2,3}
      9: {2,2}         28: {1,1,4}         46: {1,9}
     10: {1,3}         29: {10}            47: {15}
     11: {5}           31: {11}            49: {4,4}
     13: {6}           32: {1,1,1,1,1}     50: {1,3,3}
     14: {1,4}         33: {2,5}           51: {2,7}
     15: {2,3}         34: {1,7}           52: {1,1,6}
     16: {1,1,1,1}     35: {3,4}           53: {16}
     17: {7}           37: {12}            55: {3,5}

The version with quotients >= 2 is counted by A000929, sets A018819.
                           <= 2 is A342191, counted by A342094.
                           < 2 is counted by A342096, sets A045690.
                           > 2 is counted by A342098, sets A040039.
The sets version (subsets of prescribed maximum) is counted by A045691.
These partitions are counted by A350837.
The strict case is counted by A350840.
For differences instead of quotients we have A350842, strict A350844.
The complement is A350845, counted by A350846.
A000041 = integer partitions.
A000045 = sets containing n with all differences > 2.
A003114 = strict partitions with no successions, ranked by A325160.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A116931 = partitions with no successions, ranked by A319630.
A116932 = partitions with differences != 1 or 2, strict A025157.
A323092 = double-free integer partitions, ranked by A320340.
A350839 = partitions with gaps and conjugate gaps, ranked by A350841.
Cf. A000302, A001105, A003000, A018819, A094537, A120641, A154402, A319613, A323093, A337135, A342097, A342095.

primeptn[n_]:=If[n==1,{},Reverse[Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],And@@Table[FreeQ[Divide@@@Partition[primeptn[#],2,1],2],{i,2,PrimeOmega[#]}]&]

A094536 Number of binary words of length n that are not "bifix-free".

Original entry on oeis.org

0, 0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1480, 2980, 5960, 11960, 23920, 47914, 95828, 191804, 383608, 767500, 1535000, 3070568, 6141136, 12283388, 24566776, 49135784, 98271568, 196547560, 393095120, 786199088, 1572398176, 3144813974

Offset: 0

N. J. A. Sloane, Jun 06 2004

Also the number of binary strings of length n that begin with an even length palindrome. (E.g., f(4) = 10 with strings 0000 0001 0010 0011 0110 1001 1100 1101 1110 1111.) - Peter Kagey, Jan 11 2015

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

Peter Kagey, Table of n, a(n) for n = 0..1000

See A003000 for much more information.
Cf. A094537.
A254128(n) gives the number of binary strings of length n that begin with an odd-length palindrome.

a[0]:= 0:
for n from 1 to 100 do
if n::odd then a[n]:= 2*a[n-1]
else a[n]:= 2*a[n-1] + 2^(n/2) - a[n/2]
fi
od:
seq(a[i],i=0..100); # Robert Israel, Jan 12 2015

b[0]=1;b[n_]:=b[n]=2*b[n-1]-(1+(-1)^n)/2*b[Floor[n/2]]; a[n_]:=2^n-b[n];Table[a[n], {n, 0, 34}]

s = [0,0]
(2..N).each { |n| s << 2 * s[-1] + (n.odd? ? 0 : 2**(n/2) - s[n/2]) }

a(n) = 2^n - A003000(n).
Let b(0)=1; b(n) = 2*b(n-1) - 1/2*(1+(-1)^n)*b([n/2]); a(n) = 2^n - b(n). - Farideh Firoozbakht, Jun 10 2004
a(0) = 0; a(1) = 0; a(2*n+1) = 2*a(2*n); a(2*n) = 2*a(2*n-1) + 2^n - a(n). - Peter Kagey, Jan 11 2015
G.f. g(x) satisfies (1-2*x)*g(x) = 2*x^2/(1-2*x^2) - g(x^2). - Robert Israel, Jan 12 2015

More terms from Farideh Firoozbakht, Jun 10 2004

Corrected by Don Rogers (donrogers42(AT)aol.com), Feb 15 2005

A350845 Heinz numbers of integer partitions with at least two adjacent parts of quotient 2.

Original entry on oeis.org

6, 12, 18, 21, 24, 30, 36, 42, 48, 54, 60, 63, 65, 66, 72, 78, 84, 90, 96, 102, 108, 114, 120, 126, 130, 132, 133, 138, 144, 147, 150, 156, 162, 168, 174, 180, 186, 189, 192, 195, 198, 204, 210, 216, 222, 228, 231, 234, 240, 246, 252, 258, 260, 264, 266, 270

Offset: 1

Gus Wiseman, Jan 20 2022

nonn

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), so these are numbers with at least two adjacent prime indices of quotient 1/2.

			The terms and corresponding partitions begin:
   6: (2,1)
  12: (2,1,1)
  18: (2,2,1)
  21: (4,2)
  24: (2,1,1,1)
  30: (3,2,1)
  36: (2,2,1,1)
  42: (4,2,1)
  48: (2,1,1,1,1)
  54: (2,2,2,1)
  60: (3,2,1,1)
  63: (4,2,2)
  65: (6,3)
  66: (5,2,1)
  72: (2,2,1,1,1)
  78: (6,2,1)
  84: (4,2,1,1)
  90: (3,2,2,1)
  96: (2,1,1,1,1,1)

The complement is A350838, counted by A350837.
The strict complement is counted by A350840.
These partitions are counted by A350846.
A000041 = integer partitions.
A000045 = sets containing n with all differences > 2.
A056239 adds up prime indices, row sums of A112798, counted by A001222.
A116931 = partitions with no successions, ranked by A319630.
A116932 = partitions with differences != 1 or 2, strict A025157.
A323092 = double-free integer partitions, ranked by A320340.
A325160 ranks strict partitions with no successions, counted by A003114.
A350839 = partitions with gaps and conjugate gaps, ranked by A350841.
Cf. A000929, A001105, A018819, A045690, A045691, A094537, A154402, A319613, A323093, A337135, A342094, A342095, A342098, A342191.

primeptn[n_]:=If[n==1,{},Reverse[Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],MemberQ[Divide@@@Partition[primeptn[#],2,1],2]&]

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

A350838 Heinz numbers of partitions with no adjacent parts of quotient 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A094536 Number of binary words of length n that are not "bifix-free".

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Ruby

Formula

Extensions

A350845 Heinz numbers of integer partitions with at least two adjacent parts of quotient 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica