3D path counting, but only allowed to move on the surface and no backtracking.

Question

A spider wants to crawl on a Rubik's cube starting at the bottom near left corner and finishing at the top far right corner traveling 9 units. In how many ways can he travel if he is only allowed to move on the surface?
I attempted the problem by doing the Pascal's triangle method, writing out all the ones and twos and etc. I'm stuck at the point where there starts to be three intersections. Do I add up the numbers from the three?

Answer 1

Denote a unit move in $x$-direction by $X$, and similarly for $y$ and $z$. We then have to count the number words of length $9$ over the alphabet $\{X,Y,Z\}$ containing each letter exactly three times, whereby the following extra rule is in force: The third letter may not appear before at least one of the two other letters has appeared three times.

Assume that $X$ is the letter that is the first to appear three times, like so: $$\underline{\ }\ X \ \underline{\ }\ X\ \underline{\ }\ X\quad\ldots.\tag{1} $$

If the word begins with $XXX$ then we can finish it off with $Y$s and $Z$s in ${6\choose 3}=20$ ways.

Assume that the letter $Y$ occurs once or twice before all three $X$s have occurred. If $Y$ occurs once in one of the three slots in $(1)$ we can finish off the word in ${5\choose2}$ ways. If two $Y$s occur in two of the three slots in $(1)$, or as $YY$ in one of the three slots then we can finish off the word in ${4\choose 1}$ ways. This leads to $$3\cdot{5\choose2}+6\cdot{4\choose1}=54$$ admissible words.

The total number $N$ of admissible words therefore is given by $$N=3\cdot\bigl(20+2\cdot 54\bigr)=384\ .\tag{2}$$ The extra factor $3$ in $(2)$ comes from the conditioning on $X$ in the first part, and the extra factor $2$ in $(2)$ comes from the conditioning on $Y$ in the second part.

Answer 2

Here's a template for calculating the number of paths a spider can take from one corner of a Rubik's cube to the opposite corner, assuming "one unit" means "one cubie", and that the spider walks only along the edges of cubies, taking nine steps total.

The left-hand diagram represents the "back" three faces of the cube, with the spider's initial location at the central vertex. The destination is the central vertex of the right-hand diagram. The eighteen vertices along the diagrams' edges correspond (i.e., represent the same vertices on the cube) in the obvious way.

And here's the spoiler, showing the total number of paths: