A006156 -id:A006156 - cp's OEIS frontend

A194923 The (finite) list of ternary abelian squarefree words.

0, 1, 2, 0, 1, 0, 2, 1, 0, 1, 2, 2, 0, 2, 1, 0, 1, 0, 0, 1, 2, 0, 2, 0, 0, 2, 1, 1, 0, 1, 1, 0, 2, 1, 2, 0, 1, 2, 1, 2, 0, 1, 2, 0, 2, 2, 1, 0, 2, 1, 2, 0, 1, 0, 2, 0, 1, 2, 0, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 0, 0, 2, 1, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 0, 2, 1, 1, 2, 0, 1, 1, 2, 0, 2, 1, 2, 1, 0, 2, 0, 1, 0, 2, 0

Offset: 1

M. F. Hasler, Sep 04 2011, based on deleted sequence A138036 from Roger L. Bagula, May 02 2008

Lexicographically ordered list of words of increasing length L=1,2,3,... over the alphabet {0,1,2}, excluding those which contain two adjacent subsequences with the same multiset of symbols regardless of internal order. E.g., 0,0 or 1,1 or 2,2 or 0,1,0,1 or 0,1,2,1,0,2, etc.
Peter Lawrence, Sep 06 2011: In other words, this is the sequence of all possible lists over the letters "0", "1", "2", such that within a list no two adjacent segments of any length contain the same multiset of symbols, first sorted by length of list, second lists of same length are sorted lexicographically. Recursively, to each list of length N create up to two lists of length N+1 by appending the two letters that are different from the last letter of the first list, and then check for and eliminate longer abelian squares; keeping all the lists sorted as in the previous description.
The number of sequences of the successive lengths are 3, 6, 12, 18, 30, 30, 18, for total row lengths of 3, 12, 36, 72,150, 180, 126.

			Starting with words of length 1, the allowed ones are:
{{0}, {1}, {2}};
{{0, 1}, {0, 2}, {1, 0}, {1, 2}, {2, 0}, {2, 1}};
{{0, 1, 0}, {0, 1, 2}, {0, 2, 0}, {0, 2, 1}, {1, 0, 1}, {1, 0, 2}, {1, 2, 0}, {1, 2, 1}, {2, 0, 1}, {2, 0, 2}, {2, 1, 0}, {2, 1, 2}};
{{0, 1,0, 2}, {0, 1, 2, 0}, {0, 1, 2, 1}, {0, 2, 0, 1}, {0, 2, 1, 0}, {0, 2, 1, 2}, {1, 0, 1, 2}, {1, 0, 2, 0}, {1, 0, 2, 1}, {1, 2, 0, 1}, {1, 2, 0, 2}, {1, 2, 1, 0}, {2, 0, 1, 0}, {2, 0, 1, 2}, {2, 0, 2, 1}, {2, 1, 0, 1}, {2, 1, 0, 2}, {2, 1, 2, 0}},
{{0, 1, 0, 2, 0}, {0, 1, 0, 2, 1}, {0, 1, 2, 0, 1}, {0, 1, 2, 0, 2}, {0, 1, 2, 1, 0}, {0, 2, 0,1, 0}, {0, 2, 0, 1, 2}, {0, 2, 1, 0, 1}, {0, 2, 1, 0,2}, {0, 2, 1, 2, 0}, {1, 0,1, 2, 0}, {1, 0, 1, 2, 1}, {1, 0, 2, 0, 1}, {1, 0, 2, 1, 0}, {1, 0, 2, 1, 2}, {1, 2, 0, 1, 0}, {1, 2, 0, 1, 2}, {1, 2, 0, 2, 1}, {1, 2, 1, 0, 1}, {1, 2, 1, 0, 2}, {2, 0,1, 0, 2}, {2, 0, 1, 2, 0}, {2, 0, 1, 2, 1}, {2, 0, 2,1, 0}, {2, 0, 2, 1, 2}, {2,1, 0, 1, 2}, {2, 1, 0, 2, 0}, {2, 1, 0, 2, 1}, {2, 1, 2, 0, 1}, {2, 1, 2, 0, 2}},
{{0, 1, 0, 2, 0, 1}, {0, 1, 0, 2, 1, 0}, {0, 1,0, 2, 1, 2}, {0, 1, 2, 0, 1, 0}, {0, 1, 2, 1, 0, 1}, {0, 2, 0, 1, 0, 2}, {0, 2, 0, 1, 2, 0}, {0, 2, 0, 1, 2, 1}, {0, 2, 1, 0, 2, 0}, {0, 2, 1, 2, 0, 2}, {1, 0, 1, 2, 0, 1}, {1, 0, 1, 2, 0, 2}, {1, 0, 1, 2, 1, 0}, {1, 0, 2, 0, 1, 0}, {1, 0, 2, 1, 0, 1}, {1, 2, 0, 1, 2, 1}, {1, 2, 0, 2, 1, 2}, {1, 2, 1, 0, 1, 2}, {1, 2, 1, 0, 2, 0}, {1, 2, 1, 0, 2, 1}, {2, 0, 1, 0, 2, 0}, {2, 0, 1, 2, 0, 2}, {2, 0, 2, 1, 0, 1}, {2, 0, 2, 1, 0, 2}, {2, 0, 2, 1, 2, 0}, {2, 1, 0, 1, 2, 1}, {2, 1, 0, 2, 1, 2}, {2, 1, 2, 0, 1, 0}, {2, 1, 2, 0, 1, 2}, {2, 1, 2, 0, 2, 1}},
{{0, 1, 0, 2, 0, 1, 0}, {0,1, 0, 2, 1, 0, 1}, {0, 1, 2, 1, 0, 1, 2}, {0, 2, 0, 1, 0, 2, 0}, {0, 2, 0, 1, 2, 0, 2}, {0, 2, 1, 2, 0, 2, 1}, {1, 0, 1, 2, 0, 1, 0}, {1, 0, 1, 2, 1, 0, 1}, {1, 0, 2, 0, 1, 0, 2}, {1, 2, 0, 2, 1, 2, 0}, {1, 2, 1, 0, 1, 2, 1}, {1, 2, 1, 0, 2, 1, 2}, {2, 0, 1, 0, 2, 0, 1}, {2, 0, 2,1, 0, 2, 0}, {2, 0, 2, 1, 2, 0, 2}, {2,1, 0, 1, 2, 1, 0}, {2, 1, 2, 0, 1, 2, 1}, {2, 1, 2, 0, 2, 1, 2}}

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..579 (Complete list)
V. Keränen, New Abelian Square-Free DT0L-Languages over 4 Letters
E. Weisstein, from MathWorld: Squarefree Word

Cf. A194942, A001285, A007413, A005679, A036584, A099054, A100337, A006156, A099951.

f[n_, k_] := NestList[ DeleteCases[ Flatten[ Map[ Table[ Append[#, i - 1], {i, k}] &, #], 1], {_, u__, v__} /; Sort[{u}] == Sort[{v}]] &, {{}}, n]; f[7, 3] // Flatten (* initially from Roger L. Bagula and modified by Robert G. Wilson v, Sep 06 2011 *)

Edited by Franklin T. Adams-Watters, Sep 05 2011

A012212 Number of squarefree palindromes over {0, 1, 2} of length 2n+1.

Original entry on oeis.org

3, 6, 6, 12, 12, 12, 12, 18, 18, 24, 36, 48, 60, 84, 102, 138, 186, 246, 306, 378, 486, 630, 816, 1050, 1350, 1782, 2328, 2988, 3870, 5076, 6624, 8616, 11112, 14454, 18882, 24630, 31944, 41442, 53988, 70422, 91614, 119046, 154896, 201834, 262824, 341688

Offset: 0

Jeffrey Shallit

Giovanni Resta, Table of n, a(n) for n = 0..55

Cf. A006156.

s = {"1","2","3"}; L=s; a={3}; ext[w_] := Select[#<>w<># & /@ s, StringFreeQ[#, x__ ~~ x__] &]; Do[L = Flatten[ext /@ L, 1]; AppendTo[a, Length@ L], {30}]; a (* Giovanni Resta, Aug 26 2018 *)

a(31)-a(45) from Giovanni Resta, Aug 26 2018

A066297 Number of ternary squarefree necklaces.

Original entry on oeis.org

1, 3, 6, 6, 12, 0, 18, 0, 24, 0, 0, 66, 72, 78, 0, 30, 48, 0, 252, 228, 300, 42, 462, 690, 720, 750, 702, 810, 1260, 2088, 3870, 5022, 5568, 4752, 5916, 10920, 16416, 18870, 21660, 23556, 34320, 51414, 75852, 93654, 108372, 126360, 172914, 245058, 343872

Offset: 0

Paul Parsons (paul.parsons6(AT)btinternet.com)

A square is an adjacent pair of repeats, e.g., "aa" or "abcabc". A necklace is a word that may be rotated before being tested (for squares).
Several similar sequences (with same zeros) can be constructed from equivalence classes of the loops.
Higher terms: a(n) > 0 for 30 < n <= 56; no zeros known after a(17).
This is also the number of ternary "circular" squarefree words.  The Currie paper proves no 0 entries after a(17). - Jeffrey Shallit, Jul 11 2012

			a(1)=3, size of {"a","b","c"}; a(6)=18, size of {"abacbc","bacbca",...,"cbabca"}.

J. D. Currie, There are ternary circular square-free words of length n for n >= 18, Elect. J. Combinatorics 9 (2002), Paper N10.

Variant of A006156. See also A001037, A006206.

a(31)-a(36) from Jeffrey Shallit, Jan 22 2019

a(37)-a(48) from Sean A. Irvine, Oct 07 2023

A088953 Number of numbers that are ternary squarefree words of length n.

Original entry on oeis.org

1, 3, 4, 8, 12, 20, 28, 40, 52, 72, 96, 136, 176, 228, 304, 412, 532, 696, 928, 1220, 1592, 2120, 2764, 3612, 4688, 6132, 7928, 10324, 13480, 17616, 22948, 29908, 38964, 50748, 66184, 86344, 112364, 146344, 190500

Offset: 0

Reinhard Zumkeller, Oct 25 2003

nonn

Eric Weisstein's World of Mathematics, Squarefree Word

Cf. A088952, A007089.

a(n) = A006156(n)*2/3 for n>1 [Corrected by Rémy Sigrist, Aug 19 2020].

A309623 Numbers k for which there is an extremal ternary word of length k.

Original entry on oeis.org

25, 41, 48, 50, 63

Offset: 1

Jeffrey Shallit, Oct 20 2019

A ternary word is one over a three-letter alphabet, such as {0,1,2}. Such a word is called "squarefree" if it contains no subblock of the form XX, where X is a nonempty contiguous block. A word x is extremal if it is squarefree, but every possible insertion of a single letter, that is, every word of the form x' a x'' with x = x' x'', a in {0,1,2}, is not squarefree.

The Grytczuk paper proves there are arbitrarily long extremal words.

			The smallest extremal word is of length 25, which is 0120102120121012010212012 and is unique up to renaming of the letters. The next smallest are of length 41, and there are two (up to renaming), namely 01021012021020121021201021012021020121021 and 02102012102120102101202102012102120102101. The next is of length 48, and is unique (up to renaming): 010212012102010212012101202120121020102120121020. The next is of length 50 and is unique (up to renaming): 01021201021012021020121012021201021012021020121020.
The next smallest are of length 63, and there are two (up to renaming): 010210120210201021202102012102120102101202102010212021020121021, 012010212012101202120121020120210120102120121012021201210201202. - _Michael S. Branicky_, May 06 2022
For lengths 25, 41, 48, 50, and 63, there is a unique extremal word up to both renaming and reversal. - _Pontus von Brömssen_, May 07 2022

J. Grytczuk, H. Kordulewski, and A. Niewadomski, Extremal square-free words, arxiv preprint arXiv:1910.06226v1 [math.CO], October 14 2019.
Jaroslaw Grytczuk, Hubert Kordulewski, and Artur Niewiadomski, Extremal Square-Free Words, Electronic J. Combinatorics, 27 (1), 2020, #1.48.

Cf. A006156, A332605.

a(5) from Michael S. Branicky, May 06 2022

A171761 Number of ternary squareful words of length n.

Original entry on oeis.org

0, 0, 3, 15, 63, 213, 687, 2127, 6483, 19575, 58905, 176943, 531177, 1593981, 4782513, 14348289, 43045923, 129139119, 387419097, 1162259637, 3486782013, 10460350023, 31381055463, 94143173409

Offset: 0

Mats Granvik, Dec 18 2009

nonn

Cf. A000244, A006156.

nmax = 23; 3^Range[0, nmax] - Length /@ NestList[ DeleteCases[ Flatten[ Outer[ Append, #, {1, 2, 3}, 1], 1], {_, x__, x__, _}] &, {{}}, nmax] (* Jean-François Alcover, Jun 12 2017, using Vladimir Reshetnikov's code for A006156 *)

a(n) = A000244(n) - A006156(n).

A321168 Maximum number of squarefree conjugates of a ternary word of length n.

Original entry on oeis.org

1, 2, 3, 4, 3, 6, 5, 8, 4, 6, 11, 12, 13, 10, 15, 16, 11, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

Offset: 1

Jeffrey Shallit, Jan 10 2019

Two words are conjugate if one is a cyclic shift of the other. A word is squarefree if it contains no block of the form XX, where X is any nonempty block.
Conjecture: a(n) = n for n >= 18. - Michael S. Branicky, Jul 21 2021
The conjecture is true: see Clokie et al. - James Rayman, Feb 14 2023

			For n = 9 the ternary word 012010212 is squarefree, as are three other conjugates of it:  {120102120, 201021201, 010212012}, and this is maximal for length 9.

T. Clokie, D. Gabric and J. Shallit Circularly squarefree words and unbordered conjugates: a new approach, arXiv:1904.08187 [cs.FL], Apr 2019
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A006156.

from itertools import product
def isf(s): # incrementally squarefree
    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 = [], set("012")
    for n in range(1, nn+1):
        # max(sum(s[i:]+s[:i] in sfs for i in range(len(s))) for s in sfs)
        an = 0
        for s in sfs:
            sfconjs = 0
            for i in range(len(s)):
                if s[i:] + s[:i] in sfs: sfconjs += 1
            an = max(an, sfconjs)
            if an == n: break # short circuit maximum max
        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(36)) # Michael S. Branicky, Jul 21 2021

a(n) = n for n != 5,7,9,10,14,17. - James Rayman, Feb 14 2023

a(16)-a(59) from Michael S. Branicky, Jul 21 2021

cp's OEIS Frontend

A194923 The (finite) list of ternary abelian squarefree words.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A012212 Number of squarefree palindromes over {0, 1, 2} of length 2n+1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A066297 Number of ternary squarefree necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A088953 Number of numbers that are ternary squarefree words of length n.

Views

Author

Keywords

Links

Crossrefs

Formula

A309623 Numbers k for which there is an extremal ternary word of length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A171761 Number of ternary squareful words of length n.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A321168 Maximum number of squarefree conjugates of a ternary word of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions