login
A291365
Number of closed Sturmian words of length n.
1
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
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
KEYWORD
nonn,more
AUTHOR
Gabriele Fici, Aug 23 2017
EXTENSIONS
a(17)-a(40) from Michael S. Branicky, Sep 27 2021
STATUS
approved