Pattern-avoiding sequences

As another form of constraint one can require, say, that no pair of identical blocks ever appear together in a sequence, so that the sequence does not match {___, x__, x__, ___}. With just two possible elements, no sequence above length 3 can satisfy this constraint. But with k = 3 possible elements, there are infinite nested sequences that can, such as the one produced by the substitution system {0  {0, 1, 2}, 1  {0, 2}, 2  {1}}, starting with {0}. One can find the sequences of length n that work by using

Nest[DeleteCases[Flatten[Map[Table[Append[#, i - 1], {i, k}] &, #], 1], {___, x__, x__, ___}] &, {{}}, n]

and the number of these grows roughly like 3^n/4.

The constraint that no triple of identical blocks appear together turns out to be satisfied by the Thue–Morse nested sequence from page 83—as already noted by Axel Thue in 1906. (The number of sequences that work seems to grow roughly like 2^n/2.)

For any given k, many combinations of blocks will inevitably occur in sufficiently long sequences (compare page 1068). (For example, with k = 2, {___, x__, y__, x__, y__, ___} always matches any sequence with length more than 18.) But some patterns of blocks can be avoided. And for example it is known that for k ≥ 2 any pattern with length 6 or more (excluding the ___'s) and only two different variables (say x__ and y__) can always be avoided. But it also known that among the infinite sequences which do this, there are always nested ones (sometimes one has to iterate one substitution rule, then at the end apply once a different substitution rule). With more variables, however, it seems possible that there will be patterns that can be avoided only by sequences with a more complicated structure. And a potential sign of this would be patterns for which the number of sequences that avoid them varies in a complicated way with length.