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

Author

Gabriele Fici, Aug 23 2017

Keywords

• nonn
• more

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

Examples

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

Links

• 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.

Crossrefs

Cf. A260881, A226452, A005598.

Programs

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

Formula

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

Extensions

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