A person X standing at a point P on a flat plane starts walking. At each step, he walks exactly 1 foot in one of the directions North, South, East, or West. Suppose that after $6$ steps X comes to the original position P. Then the number of distinct paths that X can take is?
I'm ending up getting confused whenever I think about this. Let X start from $(0,0)$. A step consists of any 1 of the following moves: $1. (0,1), 2.(1,0), 3.(-1,0), 4.(0,-1)$. Assume he takes move $1$ $a$ times, move $2$ $b$ times, move $3$ $c$ times and move $4$ $d$ times. Now we have the following equations: $b-c=0, a-d=0$. Therefore $b=c$ and $a=d$. I don't know how to proceed from here. Please help.
Best Answer
You might find it easier to label the moves $N,E,S,W$, so a path might look like $NNESWS$. You're effectively counting the number of six-letter strings where the number of $N$s is the same as the number of $S$s, and same for $E/W$.
To do this systematically: what if the movement is only North/South? In other words, how many ways can we arrange the letters $NNNSSS$?
The next case would be four North/South moves and two East/West: $NNSSEW$.
The next cases will have the same counts as above, by symmetry. (Swap all $N/S$ with $E/W$.)