We define $STR(n)$ to be the longest sequence of strings with $n$ symbols such that the $k$th string has at most k symbols, the symbols of the string are taken from an alphabet consisting of $n$ characters, and no string is a subsequence of a later one.


For example, $STR(1)=2$, because the longest sequence is "A", "". $STR(2)=4$, because the longest sequence is "A", "BB", "B", "". I'm not sure how big $STR(3)$ is (although it is at least 11 due to the sequence "A","BB","BC","CB","B","CCCCC","CCCC","CCC","CC","C","").


We do know, however, that $STR(n)$ is always finite, for the same reason that [$TREE(n)$](https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem#TREE.283.29) and [$SSCG(n)$](https://en.wikipedia.org/wiki/Friedman%27s_SSCG_function) (see [well-quasi-order](https://en.wikipedia.org/wiki/Well-quasi-ordering)).


My question, what is the growth rate of $STR(n)$? It is slower than $TREE(n)+1$, since strings can embed in trees.


(In particular, if we could find $n$ such that $STR(n)>TREE(3)$, that would be great.)



Growth rate of longest sequence of strings where no string is a subsequence of a later one
I suppose it's a good idea to turn my comment into an answer.


The function $STR$ is basically the function $F$ defined by Friedman in [this paper](https://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf) (more precisely, it's easy to show $STR(k)=F(k-1)+1$). Friedman pinpoints the growth rate of this function quite precisely in theorem 5.19 of that paper. He uses the following variant of fast-growing hierarchy: $$H\_1(x)=2x+1$$ $$H\_{\beta+1}(x)=H\_\beta^{x+1}(x)$$ $$H\_\lambda(x)=H\_{\lambda(x)}(x)$$
(where $\lambda(x)$ denotes the $x$-th element of a standard fundamental sequence of $\lambda$ when $\lambda<\varepsilon\_0$).


**Theorem:** The function $F$ eventually dominates all functions $H\_\beta$ for $\beta<\omega^\omega$ and is itself eventually dominated by $H\_{\omega^\omega+1}$.


Hence, in a very precise sense, $F$ has growth rate of approximately $H\_{\omega^\omega}$.


On the other hand the function $TREE$ is growing very much faster. An often-quoted lower bound is $f\_{\Gamma\_0}$ in the fast-growing hierarchy, but I don't think an exact bound like above has been proven.


This way or another, regarding your last question - I haven't bothered to check the details, but I imagine that even with $TREE(3)$ we can construct sequences of trees of length exceeding things like $STR^{STR(5)}(5)$, so we are not going to easily find $n$ such that $STR(n)>TREE(3)$.


