Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate. We assume a ternary alphabet $V=\{0,1,2\}$ and are looking for a generating function describing the number of words of $V^*$ fulfilling certain restrictions. The words I am interested in  do not contain runs of length $k+1$ (with $k\geq 1$) and  do contain the string $1^k2$, i.e. a run of $1$ of length $k$ followed by $2$.

I'm aware of two techniques which are useful for attacking questions of this kind.
Smirnow words: One of them is based upon Smirnov words, which are words with no consecutive equal letters. See e.g. example III.24 in  Analytic Combinatorics by P. Flajolet and R. Sedgewick. The Smirnov words of the three letter alphabet $V$ are represented by the generating function $S(z)$
  \begin{align*}
S(z)=\left(1-\frac{3z}{1+z}\right)^{-1}
\end{align*}
  Since we are looking for words having maximal runs of $0,1$ and $2$ of length $k$ we substitute
  \begin{align*}
z\rightarrow z+z^2+\cdots+z^k=z\frac{1-z^k}{1-z}
\end{align*}
  Words which do not contain runs of length $k+1$ can therefore obtained as
  \begin{align*}
\left(1-\frac{3z\frac{1-z^k}{1-z}}{1+z\frac{1-z^k}{1-z}}\right)^{-1}=\frac{1-z^{k+1}}{1-3z+2z^{k+1}}
\end{align*}

$$ $$

The Goulden-Jackson Cluster Method nicely presented by J. Noonan and D. Zeilberger is predestinated if we are looking for words which are not allowed to contain so-called bad words. Applying this technique it is easy to find a generating function $T(z)$ which do not contain the bad word $1^k2$. According to the formula in page $7$ of the referred paper we obtain
  \begin{align*}
T(z)=\frac{1}{1-3z+z^{k+1}}
\end{align*}
  The generating function $S(z)$ can also be easily obtained with this method. Again according to the formula in page $7$ we get
  \begin{align*}
S(z)=\frac{1}{1-3z+3\frac{z^{k+1}(1-z)}{1-z^{k+1}}}=\frac{1-z^{k+1}}{1-3z+2z^{k+1}}
\end{align*}

I have problems to derive a generating function which follows the combined requirements of counting words which do not contain words with runs of length $k+1$, but contain the substring $1^k2$. Any ideas?
Note: This question corresponds to the second part of this question.
 A: There is a general method to compute the generating function of any regular language $L$. In your case, $L$ would be $V^* - V^*(0^{k+1} + 1^{k+1} + 2^{k+1} + 1^k)V^*$, if I understood correctly.
The general method works as follows.
Step 1. Compute the minimal deterministic automaton of $L$. In your case, this automaton has $3k+1$ states, if I am not wrong.
Step 2. Compute an unambiguous regular expression for $L$. Recall that a regular expression $R$ is unambiguous if, for every $u \in L(R)$, there is only one $R$-parse of $u$. In other words, a union is unambiguous if and only if it is disjoint, a product $K = K_0K_1 \cdots K_r$ is unambiguous if every word of $K$ has a unique factorisation as $u = u_0u_1 \cdots u_r$, with $u_0 \in K_0$, ..., $u_r \in K_r$ and $K^*$ is unambiguous if the monoid $K^*$ is free of base $K$.
A standard way to obtain an unambiguous regular expression is to use Kleene's algorithm.
Step 3. The generating function $s(L)$ of $L$ can be now computed from the unambiguous regular expression by using the rules $s(u) = z^{|u|}$, where $|u|$ denotes the length of a word $u$, $s(L_0 + L_1) = s(L_0) + s(L_1)$, $s(L_0L_1) = s(L_0)s(L_1)$ and $s(L^*) = (1-s(L))^*$.
For instance, if $L = (a + ba + bba + bbb)^*$ (an unambiguous expression), one gets $s(a) = z$, $s(ba) = z^2$, $s(bba) = s(bbb) = z^3$, and finally 
$$
s(L) = \frac{1}{1-(z+z^2+2z^3)}
$$
Coming back to your case, I suggest to treat the cases $k=0, 1$ and $2$ by hand or with the help of a computer and then guess the general formula for any $k$ before trying a more formal proof.
