|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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
|
|
|
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))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|