|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|