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

%I #39 Feb 08 2024 01:43:00

%S 0,2,2,8,14,32,62,130,254,528,1038,2102,4194,8436,16826,33756,67438,

%T 135076,270022,540410,1080542,2161904,4323226,8647964,17294978,

%U 34592956,69183794,138373842,276743558,553499312,1106990758,2214005762,4427995526,8856040664

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

%C 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".

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

%H Daniel Gabric, <a href="/A334600/b334600.txt">Table of n, a(n) for n = 1..3322</a>

%H Daniel Gabric and Jeffrey Shallit, <a href="https://arxiv.org/abs/2302.13147">Smallest and Largest Block Palindrome Factorizations</a>, arXiv:2302.13147 [math.CO], 2023.

%H T. Harju and D. Nowotka, <a href="https://doi.org/10.1016/j.tcs.2005.03.040">Counting bordered and primitive words with a fixed weight</a>, Theoret. Comput. Sci. 340 (2005), 273-279.

%F Formula due to Daniel Gabric: let u(n) denote the number of unbordered words of length n (that is, A003000(n)). Then

%F a(n) = Sum_{i = 1..floor(n/2)} u(i)*B(n,i), where

%F B(n,t) = 0 for n < 2t;

%F B(n,t) = k^(n-2t) for 2t <= n < 3t;

%F 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;

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

%F Asymptotically the number of such strings is C*2^n, where C = 0.51549041372...

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

%o (Python)

%o #code to count the number of words over a

%o #k-letter alphabet that have a unique border

%o N=10000

%o k=2

%o u = [0 for i in range(N+1)]

%o dictionary={}

%o def B(n,t,k):

%o if n - 2*t < 0:

%o return 0

%o if n - 2*t < t:

%o return k**(n-2*t)

%o if (n,t,k) not in dictionary:

%o total = 0

%o for i in range(2*t, n//2+1):

%o total += B(i,t,k)*(k**(n-2*i))

%o if n - 2*t >= t and (n+t) % 2 == 0:

%o total += B((n+t)//2, t,k)

%o dictionary[(n,t,k)] = (k**(n-2*t))-total

%o return dictionary[(n,t,k)]

%o #compute the number of binary unbordered words (A003000)

%o u[0] = 1

%o for i in range(1, N+1):

%o if i % 2 == 0:

%o u[i] = k*u[i-1]-u[i//2]

%o else:

%o u[i] = k*u[i-1]

%o for n in range(1, N+1):

%o total = 0

%o for t in range(1, n//2+1):

%o total += u[t]*B(n,t,k)

%o print(n, total)

%Y Cf. A003000.

%K nonn

%O 1,2

%A _Jeffrey Shallit_, May 07 2020