Can this be solved using a formula?

Question

I've attempted this problem by drawing several possible paths from S to E given the above conditions - a process that is very tedious. I suspect that there is an easier way. Any advice/suggestions will be greatly appreciated.

Answer 1

As other solutions show, it is easier to do this with a bit of forethought (and some combinatorics) rather than rely on a formula, but just in case you were truly looking for a direct formula, it can be done with generating functions. The answer will be the coefficient of $x^3 y^3$ in the Maclaurin series expansion of

$$f(x,y) = \frac{1}{1 - y^2 - x - xy}.$$

The exponents on $x$ and $y$ represent the relative displacements in the horizontal and vertical directions: $x^3 y^3$ represents the steps needed to get from S to E, $y^2$ represents move A, etc.

We can extract this coefficient mechanically by taking the mixed partial derivative $\partial^6 f \over \partial x^3 \partial y^3$, evaluating at $(0,0)$, and dividing out by $36 = 3! \cdot 3!$ (which is the same mixed partial applied to $x^3 y^3$). This single-line formula

$$\frac{1}{3!3!}\frac{\partial^6}{ \partial x^3 \partial y^3}\left(\frac{1}{1 - y^2 - x - xy} \right)\bigg|_{x=0,y=0}$$

ultimately yields 13, after a great amount of tedium to compute it :).

Answer 2

Hint. Consider two cases.

i) The number of $A$ moves is $0$. Then there is only one way, that is $CCC$.

ii) The number of $A$ moves is $1$. Then, in some order, we use $A$, $C$, $B$ and $B$.

Answer 3

convert to algebra! Let the coordinate of $S$ be $(0,0)$ and $E$ as $(3,3)$.

$A=(2,0)$, $B=(0,1)$, $C=(1,1)$. Looking for $a,b,c$ where $$ aA+bB+cC=(3,3) \\ $$ which gives $$ 2a+c = 3 \\ b + c = 3 $$

$c$ should be odd. Let $c=1$ solve for $a,b$; and again for $c=3$. for $ a,b,c = 1,2,1$ you have $\frac{4!}{2!}$ permutations. For $c=3$ there is only one. Total 13.

Answer 4

One way to do this is to first write a $1$ in every square which can be reached from $S$. Then for each of those squares place a tally mark $2$ in each square you can reach on the second move. If there are two $2$s in a square you put two $3$s in each square you can reach from that square, because you can reach it on move $3$ in two ways (there may be other $3$s from other directions, and a square may contain a mixture of numbers). And similarly if there are more of the same number in a square.

Since all moves are up/left there will be no circuits, and all paths will eventually run off the edge. The numbers in square $E$ will tell you how many routes there are and also give you the distribution of route lengths in moves.