OFFSET
1,2
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.
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.
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...
EXAMPLE
For n = 5 the 14 strings counted are {00010, 00110, 01000, 01001, 01100, 01101, 01110} and their binary complements.
PROG
(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)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 07 2020
STATUS
approved