A003000 -id:A003000 - cp's OEIS frontend

A334600 Number of length-n binary strings having a unique border.

0, 2, 2, 8, 14, 32, 62, 130, 254, 528, 1038, 2102, 4194, 8436, 16826, 33756, 67438, 135076, 270022, 540410, 1080542, 2161904, 4323226, 8647964, 17294978, 34592956, 69183794, 138373842, 276743558, 553499312, 1106990758, 2214005762, 4427995526, 8856040664

Offset: 1

Jeffrey Shallit, May 07 2020

nonn

A border of a string x is a nonempty prefix w != x that is also a suffix of x. For example, "ent" is a border of "entanglement".

The formula given in Harju and Nowotka (2005) below does not seem to be correct.

			For n = 5 the 14 strings counted are {00010, 00110, 01000, 01001, 01100, 01101, 01110} and their binary complements.

Daniel Gabric, Table of n, a(n) for n = 1..3322
Daniel Gabric and Jeffrey Shallit, Smallest and Largest Block Palindrome Factorizations, arXiv:2302.13147 [math.CO], 2023.
T. Harju and D. Nowotka, Counting bordered and primitive words with a fixed weight, Theoret. Comput. Sci. 340 (2005), 273-279.

Cf. A003000.

#code to count the number of words over a
#k-letter alphabet that have a unique border
N=10000
k=2
u = [0 for i in range(N+1)]
dictionary={}
def B(n,t,k):
    if n - 2*t < 0:
        return 0
    if n - 2*t < t:
        return k**(n-2*t)
    if (n,t,k) not in dictionary:
        total = 0
        for i in range(2*t, n//2+1):
            total += B(i,t,k)*(k**(n-2*i))
        if n - 2*t >= t and (n+t) % 2 == 0:
            total += B((n+t)//2, t,k)
        dictionary[(n,t,k)] = (k**(n-2*t))-total
    return dictionary[(n,t,k)]
#compute the number of binary unbordered words (A003000)
u[0] = 1
for i in range(1, N+1):
    if i % 2 == 0:
        u[i] = k*u[i-1]-u[i//2]
    else:
        u[i] = k*u[i-1]
for n in range(1, N+1):
    total = 0
    for t in range(1, n//2+1):
        total += u[t]*B(n,t,k)
    print(n, total)

Formula due to Daniel Gabric: let u(n) denote the number of unbordered words of length n (that is, A003000(n)). Then
a(n) = Sum_{i = 1..floor(n/2)} u(i)*B(n,i), where
B(n,t) = 0 for n < 2t;
B(n,t) = k^(n-2t) for 2t <= n < 3t;
B(n,t) = k^(n-2t) - Sum_{i=2t..floor(n/2)} B(i,t)*k^(n-2i), for n >= 3t and (n+t) mod 2 = 1;
B(n,t) = k^(n-2t) - B((n+t)/2,t) - Sum_{i=2t..floor(n/2)} B(i,t)*k^(n-2i) for n >= 3t and (n+t) mod 2 = 0.
Asymptotically the number of such strings is C*2^n, where C = 0.51549041372...

A107284 a(n)/4^n is the measure of the subset of [0,1] remaining when all intervals of the form [b/2^m - 1/2^(2m), b/2^m + 1/2^(2m)] have been removed, with b and m positive integers, b < 2^m and m <= n.

Original entry on oeis.org

1, 2, 6, 20, 74, 284, 1116, 4424, 17622, 70340, 281076, 1123736, 4493828, 17973080, 71887896, 287542736, 1150153322, 4600578044, 18402241836, 73608826664, 294435025580, 1177739540168, 4710957036936, 18843825900272, 75375299107260

Offset: 0

Henry Bottomley, May 19 2005

nonn

Removing all such intervals (without an upper limit on n) leaves a nowhere dense subset of [0,1]. It is of positive measure, namely 0.2677868402178891123766714035843..., the limit of a(n)/4^n. This is the same as the limit of A003000(n)/2^n and of A045690(n)/2^n and half the limit of A105284(n)/4^n.

It can be shown that this sequence also counts the pairs of binary sequences with Conway number 0. These Conway numbers arise in the analysis of Penney's game and measure to what degree two sequences overlap; see the Nishiyama paper in the links for further details. - Reed Phillips, Jun 09 2020

			At the start the interval [0,1] has measure 1 = 1/1. The first step removes the interval [1/4,3/4], leaving a subset with measure of 1/2 = 2/4. The second step in addition removes the intervals [3/16,1/4) and (3/4,13/16], leaving a subset with measure of 3/8 = 6/16. The third step in addition removes the intervals [7/64,9/64] and [55/64,57/64], leaving a subset with measure of 5/16 = 20/64.

Yutaka Nishiyama, Pattern Matching Probabilities and Paradoxes as a New Variation on Penney's Coin Game, International Journal of Pure and Applied Mathematics, Volume 59 No. 3 2010, 357-366.

Cf. A003000, A045690, A105284.

a(n) = 4*a(n-1) - A003000(n) = 2*A105284(n-1).
a(2*n+1) = 6*a(2*n) - 8*a(2*n-1).
a(4*n) = 6*a(4*n-1) - 8*a(4*n-2) - a(n).
a(4*n+2) = 6*a(4*n+1) - 8*a(4*n) - 2*a(n).

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.

A277134 Number of "unbordered" n X n binary arrays.

Original entry on oeis.org

1, 2, 14, 496, 64902, 33480816, 68683762160, 562879053495808, 18446172258948389894, 2417833047807055774900336, 1267648177654223684013845739628, 2658454721440933587372867150275542528

Offset: 0

Jeffrey Shallit, Oct 01 2016

nonn

An n X n array is bordered if there exists some i,j, with 1 <= i, j < n, such that the first i rows are the same as the last i rows, and the first j columns are the same as the last j columns. Otherwise it is unbordered.

			For n = 2 the only bordered arrays are the arrays of all 0's and all 1's.

This is one possible 2-dimensional analog of A003000.

A306742 Number of length-n binary words that can be written as the concatenation of two unbordered binary words.

Original entry on oeis.org

0, 4, 6, 14, 26, 54, 104, 210, 412, 832, 1654, 3330, 6670, 13452, 27004, 54414, 109400, 220264, 442938, 891256, 1791894, 3603128, 7241452, 14552628, 29234478, 58720290, 117911510, 236729446, 475169660, 953616548, 1913446072, 3838773120, 7700145556, 15443494464, 30969376788, 62096345834, 124493833506

Offset: 1

Jeffrey Shallit, Mar 07 2019

nonn

A word w is bordered if it has a nonempty prefix, unequal to w, that is also a suffix. A word is unbordered if it is not bordered.

			For n = 5, the 6 words that are not so expressible are 00000, 00100, 01010, and their complements.

Cf. A003000.

a(23)-a(37) from Bert Dobbelaere, Mar 24 2019

cp's OEIS Frontend

A334600 Number of length-n binary strings having a unique border.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A107284 a(n)/4^n is the measure of the subset of [0,1] remaining when all intervals of the form [b/2^m - 1/2^(2m), b/2^m + 1/2^(2m)] have been removed, with b and m positive integers, b < 2^m and m <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

A277134 Number of "unbordered" n X n binary arrays.

Views

Author

Keywords

Comments

Examples

Crossrefs

A306742 Number of length-n binary words that can be written as the concatenation of two unbordered binary words.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions