Number of sequences that contain a given "run" Consider sequences of numbers 0, 1, 2 with length n. There are $3^n$ such sequences.
I want to know how many sequences there are that contain a k-run of 1's followed by 2. As a regular expression: 

(^|.*[^1])[1]{k}[2].*

Even better would be to know the number of sequences that contain a maximal k-run of 1's followed by 2 i.e. that contain no other K-run with K > k.
Let $\#(k)$ be the number of sequences that contain a maximal k-run of 1's followed by 2. 
These are obvious conditions, #(k) must fulfil:


*

*$\#(n-1) = 1$

*$\sum_{k = 0..n-1} \#(k)= 3^n$
I am looking for a closed form for $\#(k)$. If this is too hard to achieve, I would be happy with a closed form for the number of sequences that contain an arbitrary (not necessarily maximal) k-run of 1's followed by 2.
 A: As an answer to questions of the type "how many words of a particular length avoid/contain such-and-such patterns", there is a general method called the Goulden-Jackson cluster method  that efficiently produces a generating function for the aforementioned sequence. The main result of the method is that if $a_n$ is the number of words over an alphabet of $m$ letters that avoid a list of specified patterns, then the generating function $f(z)=\sum a_n z^n$ has the form
$$f(z)=\frac1{1-mz-C},$$
where $C$ is the weight of the "clusters" (words formed from overlapping sequences of the specified patterns). The weights of clusters ending in the various patterns satisfy a system of linear equations that depend on how the patterns overlap. (The reference is a classic paper by Zeilberger and Noonan and is highly recommended reading.) In this problem, there is a single pattern, a run of $k$ ones followed by a two. It's immediate from the G-J method that $C=-z^{k+1}$. So, if we fix $a_n$ to be the number of words over the alphabet $0,1,2$ of length $n$ that avoid this single pattern, then 
$$f(z)=\sum_na_nz^n=\frac1{1-3z+z^{k+1}}.$$
You can expand this generating function first like a geometric series and then use the binomial theorem to obtain an exact expression for the coefficients $a_n$.
$$\begin{eqnarray*}
f(z)&=&\frac1{1-3z(1-\frac{z^k}3)}\\
&=&\sum_n3^nz^n(1-\frac{z^k}3)^n\\
&=&\sum_n3^nz^n\sum_j\binom nj(-\frac13)^jz^{kj}.
\end{eqnarray*}
$$
So, the number of sequences of length $n$ that contain a $k$-run of ones followed by a two is
$$3^n-\sum_j (-1)^j3^{n-(k+1)j}\binom{n-kj}j.$$
This is consistent with @Giovanni Resta's result for $k=2$. 
Edit: As to your second question about $\#(k)= $ the number of strings of length $n$ with $k$-runs but no $K$-runs for $K>k$, this is just a matter of subtraction, i.e., it coincides with the number of strings that avoid $k+1$ runs minus the number of strings that avoid $k$ runs. So,
$$\#(k)=\sum_j (-1)^j3^{n-(k+2)j}\binom{n-(k+1)j}j-\sum_j (-1)^j3^{n-(k+1)j}\binom{n-kj}j.$$
A: This is a just a partial answer, but there was not enough space in a comment.
The problem seems not so easy. It is easy to see that the number of sequences of length $n$ that do contain "$12$" are
$$
   3^n - F_{2n+2}\,
$$
where $F_k$ denotes the $k$-th Fibonacci number.
The resulting sequence $0, 1, 6, 26, 99, 352, 1200, 3977,\dots$ is in the OEIS as Sequence A186314, i.e. Number of ternary strings of length n which contain 01. You can follow the link for more details.
Looking for $112$, things escalate quickly.
Indeed, the resulting sequence is not in the OEIS, but the complement sequence ($3^n-a(n)$) is there, as Sequence A076264 aka Number of ternary (0,1,2) sequences without a consecutive '012'. 
This sequence can be described easily with a recurrence, but can also be described with a sum. Putting together the OEIS info we got that the number of 
sequences of length $n$ that contain "$112$" are
$$
3^n-\sum_{k=0}^{\lfloor n/3\rfloor}(-1)^k {n-2k\choose k} 3^{n-3k}
$$
Maybe you or somebody else can generalize upon these partial results. I don't know if looking for maximal subsequences makes the problem easier or harder.
