A291365 Number of closed Sturmian words of length n.

2, 2, 4, 6, 12, 16, 26, 36, 52, 64, 86, 108, 142, 170, 206, 242, 294, 340, 404, 468, 544, 610, 698, 786, 894, 990, 1104, 1218, 1360, 1494, 1658, 1822, 2006, 2174, 2366, 2558, 2786, 2996, 3230, 3464

Offset

1,1

Comments

A word is closed if it has length 1 or contains a proper factor that occurs only as a prefix and as a suffix in it.

A finite Sturmian word w satisfies the following:

for any factors u, v of the same length, one has abs(|u|_a - |v|_a|) <= 1

for every letter a, where |x|_a denotes the number of a's appearing in string x (see refs). - Michael S. Branicky, Sep 27 2021

Links

Table of n, a(n) for n=1..40.

Michael S. Branicky, Python program

Michelangelo Bucci, Alessandro De Luca and Gabriele Fici, Enumeration and structure of trapezoidal words, Theor. Comput. Sci. 468: 12-22 (2013).

Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.

Alessandro De Luca and Gabriele Fici, Open and Closed Words, in Lecture Notes in Computer Science, vol. 8079, pp. 132-142, 2013. Available at arXiv, arXiv:1306.2254 [math.CO], 2013.

Alessandro De Luca, Gabriele Fici and Luca Q. Zamboni. The sequence of open and closed prefixes of a Sturmian word. Advances in Applied Mathematics Volume 90, September 2017, Pages 27-45. Available at arXiv, arXiv:1701.01580 [cs.DM], 2017.

Formula

a(n) <= min{A226452(n), A005598(n)}. - Michael S. Branicky, Sep 27 2021

Example

For n = 4, the closed Sturmian words of length n are "aaaa", "abab", "abba", "baab", "baba" and "bbbb".

Prog

(Python) # see link for faster, bit-based version
from itertools import product
def is_strm(w): # w is a finite Sturmian word
    for l in range(2, len(w)):
        facts = set(w[j:j+l] for j in range(len(w)-l+1))
        counts = set(f.count('0') for f in facts)
        if max(counts) - min(counts) > 1:
            return False
    return True
def is_clsd(w): # w is a closed word
    if len(set(w)) <= 1: return True
    for l in range(1, len(w)):
        if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
            return True
    return False
def is_cs(w):   # w is a closed Sturmian word
    return is_clsd(w) and is_strm(w)
def a(n):
    return 2*sum(is_cs("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(1, 17)]) # Michael S. Branicky, Sep 27 2021

Crossrefs

Cf. A260881, A226452, A005598.

Sequence in context: A228892 A267610 A336940 * A154779 A332983 A010101

Adjacent sequences: A291362 A291363 A291364 * A291366 A291367 A291368

Keyword

nonn,more

Author

Gabriele Fici, Aug 23 2017

Extensions

a(17)-a(40) from Michael S. Branicky, Sep 27 2021

Status

approved