Counting Question for a Cartesian Coordinate Consider a person who starts at the origin in the Cartesian plane (i.e., in the (x, y) plane). He takes four steps, each of length 1. Each step is left, right, up, or down. So there are 4 x 4 x 4 x 4 = 256 outcomes, corresponding to the 256 paths that he might choose to take. How many outcomes (i.e., 4-step-paths) will put him back at the origin, after the four steps are done?
The answer key says that there are 4 choose 2 (i.e., two left's and two right's) + 4 choose 2 (i.e., two up's and two down's) + 4! total paths. Why wouldn't we consider the case of three up's and one down's, for example?
 A: If the man starts at the origin and ends at the origin, then his total displacement must be $0$.
This means the $x$ and $y$ displacement must both be $0$, which implies the number of left moves equals the number of right moves and the number of up moves equals the number of down moves.
Paths such as $3$ ups and $1$ down lead to the man ending up on $(0,2)$. Since the man is not ending up on the origin, we do not count this path.
If $L$ is the number of left moves, and define $R,U,D$ with similar, intuitive definitions, then we have
$$L=R$$
$$U=D$$
$$L+R+U+D=4$$
We can make substitutions of the first 2 equations into the last equation to get
$$L+L+U+U=4$$
$$2L+2U=4$$
$$L+U=2$$
Since $L,U,R,D$ are nonnegative integers, we can see that the only solutions are
$$L=0,U=2$$
$$L=1,U=1$$
$$L=2,U=0$$
We can now do casework on all these solutions
Case 1: $L=0,U=2$
Then $R=0$ and $D=2$. There are $\binom{4}{2}$ ways to arrange the $U$'s and $D$'s
Case 2: $L=1,U=1$
Then $R=1$ and $D=1$. There are $\binom{4}{1,1,1,1}=4!$ ways to arrange these moves
Case 3: $L=2,U=0$
Then $R=2$ and $D=0$. There are $\binom{4}{2}$ ways to arrange the $L$'s and $R$'s
The total is then $\binom{4}{2}+4!+\binom{4}{2}=\boxed{36}$.
