# Thread: Enumeration and Coordinate System

1. ## Enumeration and Coordinate System

The Question:
Count the walks of length forty in the coordinate system such that we start at the origin, at each step we go one unit up, down, left, or right such that at the end of the walk we arrive back at the origin (hint: rotate the coordinate system 45 degrees)

My Solution Attempt:
For every step, there has to be an opposite step somewhere in the sequence so that you end up at the origin (ie. if you move up in a sequence, at another point you have to move down)

So for 40 steps, you can choose 4 options for 20 of the steps, and the other 20 steps have to be the opposite of those 20 choices. then, i tried seeing how many ways you can rearrange those possibilities.

However, I realized that depending on which steps you choose, the number of ways you can rearrange the possibilities is different because there is a different amount of repeating steps that you need to account for in order to prevent overcounting.

So I'm stuck trying to think about how rotating the coordinate system 45 degrees could help come up with a solution.

Any help for solving this problem would be greatly appreciated!

2. This is a difficult counting problem. The real difficultly will be sorting out the different cases.
Your analysis, as far as I understand it, is correct.
Example: Suppose we take ten each of up, right, down, & left. That count is $\displaystyle \frac{40!}{(10!)^4}$.

Another: four ups & downs with sixteen rights & lefts. That count is $\displaystyle \frac{40!}{(4!)^2(16!)^2}$.
I know that this may only confuse you. I do not know how to sort out the cases.
Nor do I know what the rotation hint has to do with the solution.

3. You can find the answer here, namely $\displaystyle {40\choose20}^2$, but I don't know how to justify that rigorously.

If you want to get a feel for how this works, try to work out how many routes there are for a smaller number of steps, say four steps or six steps, which should be easier than 40 steps. As an example, in the case of four steps there are nine lattice points that you can reach after two steps (including the origin itself, which you can reach in four ways). For each of these, write down how many ways there are of getting there in two steps. You should arrive at a picture like this:
Code:
    1
2 . 2
1 . 4 . 1
2 . 2
1
(The dots indicate points like (1,0) that you can't reach after two moves.) For each of these destinations, there is an equal number of ways of getting back to the origin after another two moves. So the total number of ways of getting back to the origin after four moves is $\displaystyle 4^2+ 4\times2^2 + 4\times1^2 = 36$. Notice that if you look along the diagonals (is that where the hint about the 45-degree rotation comes from?), you see the binomial coefficients 1,2,1 multiplied by 1,2,1. For a journey of 2n steps, that suggests that the total number of possible routes is $\displaystyle \sum_{j,k=0}^n{n\choose j}^2{n\choose k}^2$, which is equal to $\displaystyle {2n\choose n}^2$.

4. Originally Posted by Opalg
You can find the answer here, namely $\displaystyle {40\choose20}^2$, but I don't know how to justify that rigorously.
This interesting to know.
I had workout a summation to count them, $\displaystyle \sum\limits_{k = 0}^{20} {\frac{{40!}} {{\left( {k!} \right)^2 \left[ {\left( {20 - k} \right)!} \right]^2 }}}$.
That is exactly $\displaystyle \binom{40}{20}^2$