login
A334600
Number of length-n binary strings having a unique border.
1
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,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 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
Cf. A003000.
Sequence in context: A002785 A301603 A292038 * A357787 A045686 A045677
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, May 07 2020
STATUS
approved