cp's OEIS Frontend

A343421 Number of Dean words of length n, i.e., squarefree reduced words over {0,1,2,3}.

%I A343421 #24 Jun 21 2022 05:06:58
%S A343421 4,8,16,24,40,64,104,144,216,328,496,720,1072,1584,2344,3384,4952,
%T A343421 7264,10632,15504,22656,33136,48488,70592,103032,150352,219400,319816,
%U A343421 466664,680872,993440,1447952,2111448,3079464,4491216,6548936,9550728,13927840,20311168
%N A343421 Number of Dean words of length n, i.e., squarefree reduced words over {0,1,2,3}.
%C A343421 A Dean word is a reduced word that does not contain occurrences of ww for any nonempty w.
%C A343421 a(n) is a multiple of 4 by symmetry. - _Michael S. Branicky_, Jun 20 2022
%H A343421 Martin Ehrenstein, <a href="/A343421/b343421.txt">Table of n, a(n) for n = 1..64</a>
%H A343421 Richard A. Dean, <a href="http://www.jstor.org/stable/2313498">A sequence without repeats on x, x^{-1}, y, y^{-1}</a>, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.
%H A343421 Tero Harju, <a href="https://arxiv.org/abs/2104.06837">Avoiding Square-Free Words on Free Groups</a>, arXiv:2104.06837 [math.CO], 2021.
%o A343421 (C++)
%o A343421 #include <iostream>
%o A343421 #include <vector>
%o A343421 bool good (const std::string& s) {
%o A343421     long n = s.size();
%o A343421     for (long i = 1; i <= n/2; i++) {
%o A343421         bool match = true;
%o A343421         for (long j = 0; j < i; j++) {
%o A343421             if (s[n-i+j] != s[n-2*i+j]) {
%o A343421                 match = false; break; } }
%o A343421         if (match) return false; }
%o A343421     return true; }
%o A343421 std::vector<std::string> s = {"01"}, t, d = {"02", "13"};
%o A343421 int main () {
%o A343421     std::cout << "1 4\n";
%o A343421     for (long i = 2; i < 40; i++) {
%o A343421         std::cout << i << " " << 8*s.size() << "\n";
%o A343421         for (char c : d[i%2]) {
%o A343421             for (const std::string& x : s) {
%o A343421                 if (good(x+c)) t.push_back(x+c); } }
%o A343421         s.swap(t); t = std::vector<std::string>(); } } // _James Rayman_, Apr 15 2021
%o A343421 (Python)
%o A343421 def isf(s): # incrementally squarefree (check factors ending in last letter)
%o A343421     for l in range(1, len(s)//2 + 1):
%o A343421         if s[-2*l:-l] == s[-l:]: return False
%o A343421     return True
%o A343421 def aupton(nn, verbose=False):
%o A343421     alst, sfs = [], set("0")
%o A343421     for n in range(1, nn+1):
%o A343421         an, eo = 4*len(sfs), ["02", "13"]
%o A343421         sfsnew = set(s+i for s in sfs for i in eo[n%2] if isf(s+i))
%o A343421         alst, sfs = alst+[an], sfsnew
%o A343421         if verbose: print(n, an)
%o A343421     return alst
%o A343421 print(aupton(30)) # _Michael S. Branicky_, Jun 20 2022
%Y A343421 Cf. A003324, A112658, A051041.
%K A343421 nonn
%O A343421 1,1
%A A343421 _Michel Marcus_, Apr 15 2021
%E A343421 More terms from _James Rayman_, Apr 15 2021