# Asymptotics for forbidden subwords

Fix an alphabet $A$ and consider words of length $n$ over $A$. Fix a set $B$ of $k$ forbidden subwords (subword is not necessarily connected, i.e. $abb$ is a subword of $abcb$). Can anything be said about the asymptotics of number of permissible words (i.e. words that don't containt any word from $B$ as a subword)? (a particular case - what if $n=k^{1+\epsilon}$ and we let $k \rightarrow \infty$?)

-
This is a question that I was planned to ask myself indeed. The situation for B consisting of only one forbidden word is very clear and it is described e.g. in Knuth-Graham-Patashnik's book "Concrete mathematics". – Pietro Majer Nov 7 '10 at 19:23

If you fix $B$ then the situation is described by a DFA (deterministic finite automaton), i.e. the set of permissible words is a regular language, and so has a rational generating function; therefore, the number of permissible words grows either exponentially or polynomially.
Re your general question, if you take $B = \{ a : a \in A \}$ (or better, $B$ consists of the empty word) then there are no permissible words. On the other hand, if all the words in $B$ have size greater than $n$, then all words are permissible. So $n = k^{1+\epsilon}$ is not really meaningful.
Maybe you're worried that the last example (all words in $B$ are bigger than $n$) is cheating. You can take $A = \{a,b,c,d\}$ and $B = \{a^kb^{m-k} : 0 \leq k \leq m \}$. The set $B$ is reduced (i.e. no word is a subword of any other word), and yet the number of permissible words is exponential; we can construct such sets $B$ with arbitrary size.
It seems reasonable (see Bill's comment below) to assume that the set of words under the subword relation is a wqo (well-quasi-ordering), and so there is no infinite reduced $B$. Therefore we can't ask whether there's an infinite reduced $B$ which allows exponential growth; if $B$ need not be reduced, take $B = \{a^m : m \geq 1\}$.