# Subsequence Avoiding Sequences

An answer of mine disagrees with an answer in a math book I'm reading, and so I wanted to sanity check it to see if there's something obvious I'm missing.

The book Foundations of Mathematical Analysis by Paul J. Sally Jr. defines a subsequence avoiding sequence to be a sequence $$x_1, x_2, ..., x_n$$ such that, for any indices $$0 < i < j \leq n/2,$$ $$x_i, x_{i+1}, ..., x_{2i}$$ is not a subsequence of $$x_j, x_{j+1}, ..., x_{2j}.$$

He defines $$n(k)$$ to be the length of the longest subsequence avoiding sequence whose terms lie in $$\{1, 2, ..., k\}.$$ He states that $$n(1) = 3, n(2) = 11.$$

I agree that $$n(1) = 3,$$ but I believe that the sequence

$$1,1,2,2,2,2,1,2,1,2,1,2$$

is subsequence avoiding and of length 12, contradicting his claim that $$n(2) = 11.$$

Now, the subsequences of that sequence of the form $$x_i, ..., x_{2i}$$ for $$i\leq n/2$$ are, respectively, $$1, 1,$$ $$1,2,2,$$ $$2,2,2,2,$$ $$2,2,2,1,2,$$ $$2,2,1,2,1,2$$ $$2,1,2,1,2,1,2.$$

It's clear that none of them contain each other. So, have I made some silly mistake? Or was there a typo in the entry $$n(2) = 11$$?

• What is the definition of subsequence in this context? Normally, in subsequences you can skip elements, so that $2,2,2,2$ is a subsequence of $2,2,2,1,2.$ If you can't skip elements, I think this is usually called a sublist (at least in computer science.) If one can't skip elements, your example looks right. If one can skip elements, I'd like to see the example with $11$ terms. – saulspatz May 26 at 13:54
• Ah! I think you may be right--you can skip elements. The book does not provide an example with 11 terms, although now I know what to start looking for! – Michael Barz May 26 at 14:13
• @saulspatz - Here's the example with $11$ terms: $1222111111x.$ There are only $5$ candidates: $12, 222, 2211, 21111, 111111$ and none is a subseq of another. The last letter $x$ is not part of any candidate and can be either symbol. (This also means all $n(k)$ must be odd, as the last symbol is not part of any candidate if total length is odd.) – antkam May 26 at 14:54
• @antkam I think you should make that an answer, since the OP didn't have an example. – saulspatz May 26 at 14:56

Using the definition from @saulspatz that a subsequence allows skipping terms, here is an example with $$11$$ terms: $$1222111111x$$
There are only $$5$$ candidates: $$12, 222, 2211, 21111, 111111$$ and none is a subsequence of another. The last letter $$x$$ is not part of any candidate and can be either symbol. (This also means all $$n(k)$$ must be odd, as the last symbol is not part of any candidate if the total length is odd.)
BTW I found this by "manual backtracking" :) - it turns out starting with $$11$$ limits you to a shorter length. And starting with $$12$$ means once another $$1$$ appears the rest must be all $$1$$s (except for the last $$x$$) so it's just a matter of how many $$2$$s you can fit in before the reappearance of $$1$$.