%I #19 Sep 28 2021 04:53:04
%S 2,2,4,6,12,16,26,36,52,64,86,108,142,170,206,242,294,340,404,468,544,
%T 610,698,786,894,990,1104,1218,1360,1494,1658,1822,2006,2174,2366,
%U 2558,2786,2996,3230,3464
%N Number of closed Sturmian words of length n.
%C 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.
%C A finite Sturmian word w satisfies the following:
%C for any factors u, v of the same length, one has abs(|u|_a - |v|_a|) <= 1
%C 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
%H Michael S. Branicky, <a href="/A291365/a291365.txt">Python program</a>
%H Michelangelo Bucci, Alessandro De Luca and Gabriele Fici, <a href="https://doi.org/10.1016/j.tcs.2012.11.007">Enumeration and structure of trapezoidal words</a>, Theor. Comput. Sci. 468: 12-22 (2013).
%H Gabriele Fici, <a href="http://bulletin.eatcs.org/index.php/beatcs/article/viewFile/508/497">Open and Closed Words</a>, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.
%H Alessandro De Luca and Gabriele Fici, Open and Closed Words, in Lecture Notes in Computer Science, vol. 8079, pp. 132-142, 2013. Available at <a href="https://arxiv.org/abs/1306.2254">arXiv</a>, arXiv:1306.2254 [math.CO], 2013.
%H 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 <a href="https://arxiv.org/abs/1701.01580">arXiv</a>, arXiv:1701.01580 [cs.DM], 2017.
%F a(n) <= min{A226452(n), A005598(n)}. - _Michael S. Branicky_, Sep 27 2021
%e For n = 4, the closed Sturmian words of length n are "aaaa", "abab", "abba", "baab", "baba" and "bbbb".
%o (Python) # see link for faster, bit-based version
%o from itertools import product
%o def is_strm(w): # w is a finite Sturmian word
%o for l in range(2, len(w)):
%o facts = set(w[j:j+l] for j in range(len(w)-l+1))
%o counts = set(f.count('0') for f in facts)
%o if max(counts) - min(counts) > 1:
%o return False
%o return True
%o def is_clsd(w): # w is a closed word
%o if len(set(w)) <= 1: return True
%o for l in range(1, len(w)):
%o if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
%o return True
%o return False
%o def is_cs(w): # w is a closed Sturmian word
%o return is_clsd(w) and is_strm(w)
%o def a(n):
%o return 2*sum(is_cs("0"+"".join(b)) for b in product("01", repeat=n-1))
%o print([a(n) for n in range(1, 17)]) # _Michael S. Branicky_, Sep 27 2021
%Y Cf. A260881, A226452, A005598.
%K nonn,more
%O 1,1
%A _Gabriele Fici_, Aug 23 2017
%E a(17)-a(40) from _Michael S. Branicky_, Sep 27 2021