A282212 -id:A282212 - cp's OEIS frontend

A006156 Number of ternary squarefree words of length n.

1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264, 342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418, 7032, 9198, 11892, 15486, 20220, 26424, 34422, 44862, 58446, 76122, 99276, 129516, 168546, 219516, 285750, 372204, 484446, 630666, 821154

Offset: 0

N. J. A. Sloane, Jeffrey Shallit, Doron Zeilberger

a(n), n > 0, is a multiple of 3 by symmetry. - Michael S. Branicky, Jul 21 2021

			Let the alphabet be {a,b,c}. Then:
a(1)=3: a, b, c.
a(2)=6: all xy except aa, bb, cc.
a(3)=12: aba, abc, aca, acb and similar words beginning with b and c, for a total of 12.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Hans Havermann, Table of n, a(n) for n = 0..110 [Terms 1-90 come from The Entropy of Square-Free Words by Baake, Elser, & Grimm (pages 10, 11). Terms 91-110 come from Grimm's Improved Bounds on the Number of Ternary Square-Free Words (page 3).]
M. Baake, V. Elser and U. Grimm, The entropy of square-free words, arXiv:math-ph/9809010, 1998.
Jean Berstel, Some recent results on squarefree words, STACS 84, Symposium of Theoretical Aspects of Computer Science Paris, 11-13, 1984, pp 14-25.
F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms, Theoretical Computer Sci., 23 (1983), 69-82.
J. Brinkhuis, Non-repetitive sequences on three symbols, Quart. J. Math. Oxford, 34 (1983), 145-149.
S. Ekhad and D. Zeilberger, There are more than 2^(n/17) n-letter ternary square-free words, J. Integer Sequences, Vol. 1 (1998), Article 98.1.9.
U. Grimm, Improved bounds on the number of ternary square-free words, J. Integer Sequences, Vol. 4 (2001), Article 01.2.7.
Mari Huova, Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014.
Mari Huova and Juhani Karhumäki, On Unavoidability of k-abelian Squares in Pure Morphic Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
R. Kolpakov, Efficient Lower Bounds on the Number of Repetition-free Words, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.
Vladislav Makarov, Counting ternary square-free words quickly, arXiv:2012.03926 [cs.FL], 2020.
J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations, arXiv:math/9806036 [math.CO], 1998.
C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words, arXiv:math/0302302 [math.CO], 2003.
A. M. Shur, Growth properties of power-free languages, Computer Science Review, Vol. 6 (2012), 187-208.
A. M. Shur, Numerical values of the growth rates of power-free languages, arXiv:1009.4415 [cs.FL], 2010.
Yuriy Tarannikov, The minimal density of a letter in an infinite ternary square-free word is 0.2746..., Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.2.
Eric Weisstein's World of Mathematics, Squarefree Word

Cf. A060688, A282212.

Second column of A215075, multiplied by 3!=6.

(* A simple solution (though not at all efficient beyond n = 12) : *) a[0] = 1; a[n_] := a[n] = Length @ DeleteCases[Tuples[Range[3], n] , {a___, b__, b__, c___} ]; s = {}; Do[Print["a[", n, "] = ", a[n]]; AppendTo[s, a[n]], {n, 0, 12}]; s (* Jean-François Alcover, May 02 2011 *)
Length/@NestList[DeleteCases[Flatten[Outer[Append, #, Range@3, 1], 1], {_, x__, x__, _}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)

def isf(s): # incrementally squarefree (check factors ending in last letter)
    for l in range(1, len(s)//2 + 1):
        if s[-2*l:-l] == s[-l:]: return False
    return True
def aupton(nn, verbose=False):
    alst, sfs = [1], set("0")
    for n in range(1, nn+1):
        an = 3*len(sfs)
        sfsnew = set(s+i for s in sfs for i in "012" if isf(s+i))
        alst, sfs = alst+[an], sfsnew
        if verbose: print(n, an)
    return alst
print(aupton(40)) # Michael S. Branicky, Jul 21 2021

a(n) >= 2^(n/17), see Zeilberger. Let L = lim_{n->infinity} a(n)^(1/n); then L exists and Grimm proves 1.109999 < L < 1.317278. - Charles R Greathouse IV, Nov 29 2013

L exists since a(n) is submultiplicative; 1.3017597 < L < 1.3017619 (Shur 2012); the gap between the bounds can be made less than any given constant. - Arseny Shur, Apr 22 2015

Links corrected by Eric Rowland, Sep 16 2010

A323487 Number of length-n ternary words that are bi-maximally squarefree.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 18, 0, 24, 0, 48, 42, 18, 12, 48, 78, 36, 66, 108, 102, 240, 222, 360, 330, 696, 690, 858, 1086, 1692, 1920, 2604, 3156, 4284, 5370, 7308, 9270, 12036, 15756, 20688, 26562, 34500, 44274, 59058, 75576

Offset: 1

Jeffrey Shallit, Jan 16 2019

nonn

A word is squarefree if it contains no block of the form XX, where X is a nonempty block. A word is bi-maximally squarefree if it cannot be extended on either the left or right to a longer squarefree word.

All terms are multiples of 6 due to possible renamings of letters. - Michael S. Branicky, Sep 01 2021

			For n = 7 the six possibilities are 0102010 and all renamings of the letters.
For n = 15 the six possibilities are 010210120102101 and all renamings of the letters.

Cf. A282212, which is the one-sided version of maximally squarefree.

def isf(w): # incrementally squarefree (check factors ending in last letter)
    for l in range(1, len(w)//2 + 1):
        if w[-2*l:-l] == w[-l:]: return False
    return True
def is_bmsf(w, sfsnew): # is w bi-maximally squarefree
    lefts, rights = [c+w for c in "123"], [w+c for c in "123"]
    return all(x not in sfsnew for x in lefts + rights)
def aupton(nn):
    alst, sfs = [], set("123")
    for n in range(1, nn+1):
        sfsnew = set(w+c for w in sfs for c in "123" if isf(w+c))
        an = len([w for w in sfs if is_bmsf(w, sfsnew)])
        alst.append(an)
        sfs = sfsnew
    return alst
print(aupton(30)) # Michael S. Branicky, Sep 01 2021

a(31)-a(58) from Michael S. Branicky, Sep 01 2021

cp's OEIS Frontend

A006156 Number of ternary squarefree words of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions