How many "words" of length n is it possible to create from {a,b,c,d} without any "a"s after a "b"? I think this is a hard question and I didn't come up with a solution. Could you please give me a hint or approach?
For instance, "bdca" is not ok, but "aabcd" is ok.
It is somehow similar to this question, but with some differences.
Thanks in advance.
 A: The answer is
$$3^n+ \sum_{k=1}^n 3^{k-1}\cdot 3^{n-k}=n3^{n-1}+3^n.$$
There are $3^n$ possible words with no occurrence of $b$.  Assume the first $b$ occurs at position $k$.  Then each of the first $k-1$ positions has three possible choices ($a, c, \text{ or } d$), and each of the last $n-k$ positions has three possible choices ($b, c, \text{ or } d$).
A: Hint
$\sum_{k=1}^n [f(k) \times g(k)].$
$f(k)$ is the # of possible sequences of length $k$, where the very first occurrence of the letter $b$ is on the $k$-th letter.
Note that this categorization facilitates mutually exclusive groupings.
$g(k)$ is the # of possible sequences of length $(n-k)$ where the letter $a$ is excluded from this sequence.
Two items need special handling:
What happens if the first $b$ in the sequence is on the last (i.e. $n$-th) letter?
What happens if the sequence does not contain any $b$'s.
A: Transition matrix with two states, the string has an $b$ or it doesn't.  State 0 will be no bs and state 1 will be some bs.  $M_{i, j}$ is "how many ways can we transist from a string of type $i$ to a string of type $j$" (by appending characters) :
$$M = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}$$
For example, $M_{1, 0} = 0$ there is no way to go from a string with some bs to a string with no bs.  $M_{1, 1} = 3$ there are 3 ways to go from a string with some bs to a string with some bs (by appending b, c, or d).
Initial state is $V=[1, 0]$ since the empty string is one string which does not contain a $b$.  Final state can be either containing or not containing a string so it is $F=\begin{bmatrix} 1 \\ 1 \end{bmatrix}$
$$C = VM^nF$$ counts the number of ways to go from the initial state (empty string) to the final state (any string reachable).  $M$ is a jordan normal form matrix so a closed form for it's exponent is well known:
$$C = [1, 0]\begin{bmatrix} 3^n & n \cdot 3^{n-1} \\ 0 & 3^n \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = 3^n + n3^{n-1}$$
