Navigational Help combinations

Question

You take exactly 10 steps. You can move in one of three directions (North West East) with no desired target point (just 10 steps). You cannot follow a move East with a move West or vice versa. How many possible combinations of paths are there. I know it's 3^10 but am unsure as to how to limit the counter from the repetition of only two particular instances

Answer 1

We want to count the number of "words" of length $10$ made up of the letters N and/or W and/or E, with the rule that W cannot be immediately followed by E, and E cannot be immediately followed by W. Briefly, call a word in which W is not immediately followed by E, or the other way around, a good word.

Let $w_n$ be the number of good words of length $n$. It is easy to see that $w_1=3$. Careful listing shows that $w_2=7$. (One might want to start counting with the good words of length $0$. There is $1$ such word, the empty word, so $w_0=1$.)

Now let us look at $n\ge 3$. There are two types of good word of length $n$: (i) the ones that end in NN and (ii) the ones that don't.

(i): There are $w_{n-2}$ good words of length $n$ that end in NN, for to get such a word we just append NN to any good word of length $n-2$.

(ii) There are $2w_{n-1}$ good words of length $n$ that don't end in NN. For take any good word of length $n-1$. If it ends in N, it can be completed in $2$ ways into a word that doesn't end in NN (append W or E). If it ends in W, again it can be completed in $2$ ways (append N or W). Also, it it ends in E it can be completed in $2$ ways. We have reached the recurrence formula $$w_{n}=2w_{n-1}+w_{n-2}.\tag{1}$$

Now we can start computing. Since $w_2=7$ and $w_1=3$, by (1) we get $w_3=2\cdot 7+2=17$. But then, applying (1) again, we get $w_4=41$. But then applying (1) again, we get $w_5=99$. It is not hard to continue and find $w_{10}$.

Remark: The recurrence (1) can be used to find a closed form explicit formula for $w_n$. I believe you are not being asked to do that, so will omit the derivation of a general formula.