How do I start?

The answer equals the coefficient of $x^{12}$ in $\sum_{t=0}^{12}x^t (x^0+x^1+x^2+x^3)^{t+1}\dots(1)$

You can ask WolframAlpha to do the work by entering

Expand[Sum[x^t(1+x+x^2+x^3)^(t+1),{t,0,12}]]

and then picking out the relevant coefficient which is $\boxed{2872}$

Proof of (1)

Suppose we have a sequence satisfying the conditions of the problem. Suppose it contains T tails (and, obviously, 12-T heads). The tails punctuate runs of heads each of which has length less than 4. There will be T+1 runs of heads (some of which may be of length zero). We will work out how many such sequences there are, and then sum over all possible values of T to arrive at (1).

We have to find the number of compositions of 12 - T into T+1 bins where each element of the composition is restricted to 0,1,2 or 3. It is not too hard to work out that this equals the coefficient of $x^{12-T}$ in the expression $(x^0+x^1+x^2+x^3)^{T+1}$ . Note that this equals the coefficient of $x^{12}$ in $x^T(x^0+x^1+x^2+x^3)^{T+1}$ .

Summing this expression from T=0 to T=12 completes the proof.

Note

Here is a simple example to explain the logic of the second last paragraph.

Suppose you have five balls and three distinguishable buckets. In how many ways can you place the balls into the buckets, given that a bucket can hold zero, two, or three balls?

This problem is easy enough to solve by listing the six possible cases

$0,2,3 \dots 0,3,2 \dots 2,0,3 \dots 2,3,0 \dots 3,0,2 \dots 3,2,0$

Six is also the coefficient of $x^5$ in the expansion of $\left(x^0+x^2+x^3\right)^3$ .

The explanation is that each of the three factors $\left(x^0+x^2+x^3\right)$ represents one of the buckets, and the exponents 0,2 and 3 represent the number of balls which are allowed in each bucket. When the three brackets are multiplied out you get a list of products, and each product uses one term from each bracket, corresponding to the number of balls placed in that bucket. When you multiply the terms you add the exponents, and so we are interested in all the terms whose exponent equals 5, the number of balls at our disposal.

You can find more about this by searching for 'compositions' on line.

If $X_n$ is the number of ways of tossing $n$ coins without obtaining $4$ heads in a row, then $X_1 = 2$ , $X_2 = 4$ , $X_3 = 8$ , $X_4 = 15$ , and $X_n \; = \; X_{n-1} + X_{n-2} + X_{n-3} + X_{n-4} \qquad \qquad n \ge 5 \;,$ where the four summands are obtained by counting the number of ways of tossing $n$ coins without obtaining $4$ heads in a row, given that the first few tosses are T, HT, HHT, HHHT respectively. This information is sufficient to tell us that $X_{12} = \boxed{2872}$ .

Consider the following matrix representing the number of ways to transition from a given number of heads in a row to the next: {{1, 1, 0, 0}, {1, 0, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 0}}. Note that we only care about 0, 1, 2, and 3 heads in a row. Then if we raise this matrix to the 12th power, we get the number of ways to start with a given number of heads in a row and end with a given number of heads in a row. This matrix is the following: {{1490, 773, 401, 208}, {1382, 717, 372, 193}, {1174, 609, 316, 164}, {773, 401, 208, 108}}. Since we start off with zero heads in a row, we only care about the first row of the resulting matrix and so the answer is the sum of the first row.