login
A194923
The (finite) list of ternary abelian squarefree words.
2
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,3
COMMENTS
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.
LINKS
EXAMPLE
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}}
MATHEMATICA
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 *)
KEYWORD
nonn,tabf,fini,full
AUTHOR
M. F. Hasler, Sep 04 2011, based on deleted sequence A138036 from Roger L. Bagula, May 02 2008
EXTENSIONS
Edited by Franklin T. Adams-Watters, Sep 05 2011
STATUS
approved