HMMT 2006 T1

For this problem, our lawn consists of a row of $n$ clumps of grass. This row runs in an east-west direction. In our formation, each mobot may be oriented toward the north, south, east, or west. One example of an allowable formation if $n=6$ is symbolized below:

$$\cdot \longleftarrow \uparrow^{\downarrow}$$

(The mobot on the third clump will move westward, mowing the first three clumps. Each of the last three clumps is mowed by a different mobot.) Here's another allowable formation for $n=6$, considered different from the first:

Compute the number of different allowable formations for any given $n$.