Results 1 to 4 of 4

Math Help - Enumeration and Coordinate System

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    18

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1
    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 \frac{40!}{(10!)^4}.

    Another: four ups & downs with sixteen rights & lefts. That count is \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    You can find the answer here, namely {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 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 \sum_{j,k=0}^n{n\choose j}^2{n\choose k}^2, which is equal to {2n\choose n}^2.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,803
    Thanks
    1692
    Awards
    1
    Quote Originally Posted by Opalg View Post
    You can find the answer here, namely {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,  \sum\limits_{k = 0}^{20} {\frac{{40!}}<br />
{{\left( {k!} \right)^2 \left[ {\left( {20 - k} \right)!} \right]^2 }}} .
    That is exactly \binom{40}{20}^2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Rectangular coordinate system
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: October 28th 2009, 06:18 PM
  2. Another Coordinate system!
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 25th 2008, 08:12 AM
  3. Coordinate system help
    Posted in the Calculus Forum
    Replies: 7
    Last Post: March 25th 2008, 12:27 AM
  4. coordinate system
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 22nd 2007, 10:39 AM
  5. coordinate system
    Posted in the Geometry Forum
    Replies: 5
    Last Post: May 3rd 2007, 09:40 AM

Search Tags


/mathhelpforum @mathhelpforum