In the picture shown below the man standing at P may move in any direction 
Suppose a man is standing at the origin of a plane. He can move one square along either axis in each move. How many different paths are there such that the man makes six moves and returns to the origin at the end of the sixth move?

My approach: If the man moves up he has to move down as well.  So as I can see after drawing that the paths are coming to be a rectangle and at every direction 5 rectangles are formed. So total 20 ways. However, the answer was given to me to be 400 ways. Where do the others come from?
 A: If there are no moves up and down, then to count the possible paths with L-R only, just choose the locations of the L's, in $\binom{6}{3} = 20$ ways.
If there is one up-down pair and two left-right pairs, choose a location for the U and one for the D ($6\cdot 5=30$ ways), then choose locations for the two L's ($\binom{4}{2}$ ways), for a total of $30\cdot\binom{4}{2} = 180$.
One left-right pair and two up-down pairs is exactly the same, giving another $180$.
Finally, all up-down pairs is the same counting problem as all left-right pairs, for another $20$.
The total is $20 + 180+ 180+ 20 = 400$.
A: The generalized solution for $2n$ moves allowed, to be broken into N/S or E/W pairs, is as follows.
You will pick $n$ pairs ($2n$ moves) broken into either pairs of N/S or E/W, so you will pick $2n$ moves of which $2i$ will be from the N/S pool, where $i$ is from ${0,1,...,n}$.
Then having picked $2i$ from the N/S pool in pairs of N and S, you can arrange them by $2i$ pick $i$ possible unique ways. Same for the $n-i$ pairs of E/W. Sum it all together over $i$.
$$
    \sum _{i=0}^n \binom{2 n}{2 i} \binom{2 i}{i} \binom{2 n-2 i}{n-i}
$$
After doing some simplification this resolves as the square of the Central Binomial Coefficient...
$$
    \binom{2 n}{n}^2
$$
For the problem at hand with $n$=3, 
$$
    \binom{6}{3}^2=20^2=400
$$
This is Sloane sequence http://oeis.org/A002894
A: The path need not be a rectangle. For example, you could move three times up and then three times down, or twice up, then right, then left, then twice down.
As you noticed, the number of moves up must equal the number of moves down.
It follows that the number of moves up must be in the set $\{0,1,2,3\}.$
Suppose there are $0$ moves up. Then we have three right and three left in some sequence; the number of different sequences is the number of ways we can choose where to put the $3$ rightward moves in the sequence of $6$ moves,
that is, $\binom 63 = 20$ ways.
Suppose there is $1$ move up. Then there is also one move down, two left, and two right. The number of ways these moves can be sequenced is the number of ways we can place two objects of one type (right), two of a second type (left), and one each of two other types (up and down) in a sequence of $6$ objects; this is also known as a multinomial coefficient,
$$
\binom{6}{2\ 2\ 1\ 1} = \frac{6!}{2!2!1!1!} = 180.
$$

By symmetry, the number of ways to have exactly $2$ moves up
is the same as the number of ways to have exactly $1$ move up:
just change every up, down, right, or left move to right, left, up, or down, respectively.
For the same reason, the number of ways to have exactly $3$ moves up is the same as the number of ways to have $0$ moves up.
So we can take the number of ways to do $0$ moves up or $1$ move up
and double the number (to account for $2$ moves up and $3$ moves up),
for a total of
$$ 2(20 + 180) = 400. $$
A: However many N steps he takes he must make the same number of S steps (and vice versa).  Likewise however many W steps he must take the same number of E step (and vice versa).
So must take 3 pairs of opposing steps.
Not worrying about the order of steps he can take:
1) 3 pairs of N/S steps.
2) 2 pairs of N/S steps and 1 pair of W/E steps
3) 1 pair of N/S steps and 2 pairs of W/E steps.
4) 3 pairs of W/E steps.
Now what order can he take the steps in?
In Case 1) 3 of has steps can be N.  The rest must be S.  Out of $6$ steps $3$ of them can be N.  There are, almost by definition, $6\choose 3$ ways of choosing which are N.  The rest are S.
So there are ${6\choose 3} = \frac {6*5*4}{3*2*1} = 20$ ways to do this.
(To be clear, we are talking about what order of $N/S$ steps he takes.  $N-N-N-S-S-S$ or $N-N-S-N-S-S$ or $N-S-N-N-S-S$ or $S-N-N-N-S-S$ etc.)
In Case 4) it is the exact same thing.  Three out of six steps can be W and the rest must be E.  So there are ${6\choose 3} = 20$ ways to do that.
In Case 2) two of the six steps must be $N$.  There are ${6 \choose 2 }= \frac {6*5}{2*1} = 15$ ways to do that.  Two of the remaining four steps must be  $S$.  There are ${4 \choose 2} = \frac {4*3}{2*1} = 6$ ways to do that.  Of the two remaining steps, one must be W.  There is ${2 \choose 1} = 2$ ways to choose that.  The last remaining step must be E.  So there are ${6\choose 2}{4\choose 2}{2 \choose 1} = 15*6*2 = 180$ ways to do that.
To clarify. Of the six x-x-x-x-x-x steps, we first figure out where we can place the $2$ N steps to get something like x-N-x-x-N-x.  There are $6$ places to put the first $N$ and $5$ places to put the second bu it doesn't matter which order we choose the Ns so there are $6*5/2 = 15$ ways to choose the Ns.  Then we want to choose how to place the Ss to something like S-N-x-S-N-x.  There are four places for the first S and three for the second and order doesn't matter so there $4*3/2 = 6$ ways.  Then we place the one W so get something like S-N-x-S-N-W.  There are $2$ choices to put it.  The last remaining step must be E to have S-N-E-S-N-W.  (which you'll notice is not a rectangle.)
Step 3 can be done the exact same way but I'll show it can be done another way.  First choose which of the $6$ steps can by the one $N$ step.  THere are ${6 \choose 1 }= 6$ choices.  Then choose which of the remaining $5$ steps can be the $2$ W steps.  There are ${5 \choose 2} = \frac {5*4}{2*1} =10$ ways of choosing those.  Then choose which of the remaining $3$ steps can be the on S step.  There are ${3 \choose 1} = 3$ ways to choose those.  The last two steps must be the two E steps.  So there are ${6\choose 1}{5\choose 2}{3\choose 1} = 6*10*3 = 180$ ways to do this.
We could have chosen the steps in any order and gotten the same number of ways to do it.  I'll leave it to you do verify ${6\choose 2}{4\choose 2}{2\choose 1} ={6\choose 2}{4\choose 1}{3 \choose 2} = {6\choose 2}{4 \choose 1}{3 \choose 1}={6\choose 1}{5 \choose 2}{3\choose 2}= {6\choose 1}{5\choose 2}{3\choose 1}= {6\choose 1}{5\choose 1}{4 \choose 2}=180$.
So
1) 3 pairs of N/S steps. There are $20$ ways to do this
2) 2 pairs of N/S steps and 1 pair of W/E steps. There are $180$ ways to do this
3) 1 pair of N/S steps and 2 pairs of W/E steps. There are $180$ ways to do this
4) 3 pairs of W/E steps. There are $20$ ways to do this
So there are $20 + 180+ 180 + 20=400$ ways to return to the origin after 6 steps.
