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

Cf. A003000.

Sequence in context: A002785 A301603 A292038 * A357787 A045686 A045677

Adjacent sequences: A334597 A334598 A334599 * A334601 A334602 A334603

Keyword

nonn

Author

Jeffrey Shallit, May 07 2020

Status

approved