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

Author

Jeffrey Shallit, May 07 2020

Keywords

• nonn

Comments

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.

Examples

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

Links

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

Crossrefs

Cf. A003000.

Programs

Python

#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

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