A094536 -id:A094536 - cp's OEIS frontend

A094537 A094536/2.

0, 0, 1, 2, 5, 10, 22, 44, 91, 182, 370, 740, 1490, 2980, 5980, 11960, 23957, 47914, 95902, 191804, 383750, 767500, 1535284, 3070568, 6141694, 12283388, 24567892, 49135784, 98273780, 196547560, 393099544, 786199088, 1572406987, 3144813974

Offset: 0

N. J. A. Sloane, Jun 06 2004

Cf. A003000, A094536.

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

Let b(0)=1; b(n)=2*b(n-1)-1/2*(1+(-1)^n)*b([n/2]); a(n)=2^(n-1)-b(n)/2 - Farideh Firoozbakht, Jun 10 2004

More terms from Farideh Firoozbakht, Jun 10 2004

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

Original entry on oeis.org

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

A121880 a(n) = 2^n - A122536(n).

Original entry on oeis.org

0, 2, 4, 10, 20, 44, 88, 182, 364, 738, 1476, 2972, 5944, 11924, 23848, 47768, 95536, 191214, 382428, 765136, 1530272, 3061104, 6122208, 12245530, 24491060, 48984342, 97968684, 195941804, 391883608, 783776080, 1567552160, 3135122038, 6270244076

Offset: 1

N. J. A. Sloane, Sep 21 2006

nonn

Number of binary sequences of length n with curling number > 1. See A122536 for much more information.

Robert Price, Table of n, a(n) for n = 1..200
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
Index entries for sequences related to curling numbers

Cf. A122536. Similar to but different from A094536.

A226452 Number of closed binary words of length n.

Original entry on oeis.org

1, 2, 2, 4, 6, 12, 20, 36, 62, 116, 204, 364, 664, 1220, 2240, 4132, 7646, 14244, 26644, 49984, 94132, 177788, 336756, 639720, 1218228, 2325048, 4446776, 8520928, 16356260, 31447436, 60552616, 116753948, 225404486, 435677408, 843029104, 1632918624, 3165936640

Offset: 0

Jeffrey Shallit, Jun 07 2013

nonn

A word is closed if it contains a proper factor that occurs both as a prefix and as a suffix but does not have internal occurrences.

a(n+1) <= 2*a(n); for n > 1: a(n) <= A094536(n). - Reinhard Zumkeller, Jun 15 2013

			a(4) = 6 because the only closed binary words of length 4 are 0000, 0101, 0110, and their complements.

Lars Blomberg, Table of n, a(n) for n = 0..38
Michael S. Branicky, Python program
G. Badkobeh, G. Fici, Z. Lipták, On the number of closed factors in a word, in A.-H. Dediu et al., eds., LATA 2015, LNCS 8977, 2015, pp. 381-390. Available at arXiv, arXiv:1305.6395 [cs.FL], 2013-2014.
Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.
Daniel Gabric, Asymptotic bounds for the number of closed and privileged words, arXiv:2206.14273 [math.CO], 2022.

Cf. A297183, A297184, A297185.

import Data.List (inits, tails, isInfixOf)
a226452 n = a226452_list !! n
a226452_list = 1 : 2 : f [[0,0],[0,1],[1,0],[1,1]] where
   f bss = sum (map h bss) : f ((map (0 :) bss) ++ (map (1 :) bss)) where
   h bs = fromEnum $ or $ zipWith
           (\xs ys -> xs == ys && not (xs `isInfixOf` (init $ tail bs)))
           (init $ inits bs) (reverse $ tails $ tail bs)
-- Reinhard Zumkeller, Jun 15 2013

# see link for faster, bit-based version
from itertools import product
def closed(w): # w is a closed word
    if len(set(w)) <= 1: return True
    for l in range(1, len(w)):
        if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
            return True
    return False
def a(n):
    if n == 0: return 1
    return 2*sum(closed("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(22)]) # Michael S. Branicky, Jul 09 2022

a(17)-a(23) from Reinhard Zumkeller, Jun 15 2013

a(24)-a(36) from Lars Blomberg, Dec 28 2015

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.

A254128 Number of binary strings of length n that begin with an odd-length palindrome.

Original entry on oeis.org

0, 0, 0, 4, 8, 20, 40, 88, 176, 364, 728, 1480, 2960, 5960, 11920, 23920, 47840, 95828, 191656, 383608, 767216, 1535000, 3070000, 6141136, 12282272, 24566776, 49133552, 98271568, 196543136, 393095120, 786190240, 1572398176, 3144796352, 6289627948, 12579255896

Offset: 0

Peter Kagey, Jan 25 2015

This sequence gives the number of binary strings of length n that begin with an odd-length palindrome (not including the trivial palindrome of length one).
'1011' is an example of a string that begins with an odd-length palindrome: the palindrome '101', which is of length 3.
'1101' is an example of a string that does not begin with an odd-length palindrome. (It does begin with the even-length palindrome '11'.)
The probability of a random infinite binary string beginning with an odd-length palindrome is given by: limit n -> infinity a(n)/(2^n), which is approximately 0.7322131597821109.

			For n = 4 the a(3) = 8 solutions are: 0000 0001 0100 0101 1010 1011 1110 1111.

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

Cf. A003000. A094536 is the analogous sequence for even-length palindromes.

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

a(2*n) = 2*a(2*n-1) = A094536(2*n) - A003000(n) for all n > 0.

a(2*n+1) = 2*a(2*n) + 2^(n+1) - a(n+1) = A094536(2*n+1) for all n.

A331393 Sum, over all binary strings w of length n, of the length of the longest border of w.

Original entry on oeis.org

0, 2, 6, 16, 36, 82, 176, 372, 768, 1582, 3224, 6534, 13166, 26504, 53244, 106824, 214060, 428764, 858400, 1718056, 3437734, 6877896, 13759154, 27523128, 55052582, 110114618, 220242288, 440503282, 881031714, 1762100362, 3524251618, 7048576724, 14097253490

Offset: 1

Jeffrey Shallit, Jan 15 2020

nonn

A nonempty word w is a border of a string x if w is both a prefix and suffix of x, and w does not equal x.

			For n = 4 the 16 words are 0000,0001,0010,0011,0100,0101,0110,0111, and their binary complements.
0000 has longest border 3; 0010, 0100, 0110 have longest border 1; and 0101 has longest border 2.  So a(4) = 2*(3+3+2) = 16.

Shiyao Guo, Table of n, a(n) for n = 1..120

Cf. A094536, A331392.

More terms from Rémy Sigrist, Jan 16 2020

A323445 Number of length-n binary strings where some nonempty proper prefix is the reverse of a cyclic shift (conjugate) of a suffix.

Original entry on oeis.org

0, 2, 4, 10, 20, 44, 88, 182, 364, 740, 1484, 2990, 5992, 12030, 24092, 48278, 96628, 193458, 387052, 774486, 1549220, 3099106, 6198632, 12398466, 24797384, 49596654, 99193464, 198389538, 396777716, 793557898, 1587108968, 3174217032, 6348411948, 12696809070

Offset: 1

Jeffrey Shallit, Jan 15 2019

nonn

			For n=4 the 10 strings are {0000,0010,0100,0101,0110} and their bitwise complements.

Lars Blomberg, Table of n, a(n) for n = 1..40

Not the same as A094536.

a(21)-a(34) from Lars Blomberg, Feb 14 2019

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

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 4, 9, 10, 1, 0, 5, 16, 33, 20, 1, 0, 6, 25, 76, 99, 44, 1, 0, 7, 36, 145, 304, 315, 88, 1, 0, 8, 49, 246, 725, 1264, 945, 182, 1, 0, 9, 64, 385, 1476, 3725, 5056, 2883, 364, 1, 0, 10, 81, 568, 2695, 9036, 18625, 20404, 8649, 740, 1

Offset: 1

Peter Kagey, Mar 07 2021

A bifix is a nonempty substring that is both a prefix and a suffix.

			Table begins:
n\k | 1 2  3   4    5     6      7       8        9
----+----------------------------------------------
  1 | 0 1  1   1    1     1      1       1        1
  2 | 0 2  4  10   20    44     88     182      364
  3 | 0 3  9  33   99   315    945    2883     8649
  4 | 0 4 16  76  304  1264   5056   20404    81616
  5 | 0 5 25 145  725  3725  18625   93605   468025
  6 | 0 6 36 246 1476  9036  54216  326346  1958076
  7 | 0 7 49 385 2695 19159 134113  940807  6585649
  8 | 0 8 64 568 4544 36800 294400 2358728 18869824
For n = 2, k = 4, the A(2,4) = 10 length-4 strings over a 2-letter alphabet with a bifix are:
0000 with prefix and suffix 0,
0010 with prefix and suffix 0,
0100 with prefix and suffix 0,
0101 with prefix and suffix 01,
0110 with prefix and suffix 0,
1001 with prefix and suffix 1,
1010 with prefix and suffix 10,
1011 with prefix and suffix 1,
1101 with prefix and suffix 1, and
1111 with prefix and suffix 1.

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

Cf. A342239.
Rows: A094536 (n=2), A094538 (n=3), A094559 (n=4).
Columns: A000290 (k=3), A081437 (k=4).

from itertools import product
def has_bifix(s): return any(s[:i] == s[-i:] for i in range(1, len(s)//2+1))
def T(n, k): return sum(has_bifix(s) for s in product(range(n), repeat=k))
def atodiag(maxd): # maxd antidiagonals
  return [T(n, d-n+1) for d in range(1, maxd+1) for n in range(d, 0, -1)]
print(atodiag(11)) # Michael S. Branicky, Mar 07 2021

T(n,k) = n^k - A342239(n,k).

cp's OEIS Frontend

A094537 A094536/2.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A121880 a(n) = 2^n - A122536(n).

Views

Author

Keywords

Comments

Links

Crossrefs

A226452 Number of closed binary words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Python

Extensions

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

A254128 Number of binary strings of length n that begin with an odd-length palindrome.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Ruby

Formula

A331393 Sum, over all binary strings w of length n, of the length of the longest border of w.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A323445 Number of length-n binary strings where some nonempty proper prefix is the reverse of a cyclic shift (conjugate) of a suffix.

Views

Author

Keywords

Examples