Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Counting pathways

  1. #1
    Junior Member
    Joined
    Aug 2006
    Posts
    29

    Counting pathways

    Hello

    I need to count the number of ways,from start to end,without passing through the red spots.
    you can move one step at a time:forward or to the right.

    thanks.
    Attached Thumbnails Attached Thumbnails Counting pathways-untitled.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    There are 49 paths.

    The numbers in each box of the excel spreadsheet in the attachments shows how many paths can go through each point. Do you see how it was made? Or would you like an explanation.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    I would appreciate it if you could give me an explanation,in a combinatorial way i.e n choose k

    thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by parallel View Post
    I would appreciate it if you could give me an explanation,in a combinatorial way i.e n choose k

    thanks
    You're going to have to ask someone else
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Say p(x,\ y) is the number of paths to a specific square. For the bottom left square, x = 0 and y = 0, and for the upper right square, x = 4 and y = 4. Then

    p(x,\ y)\ =\ \left\{\begin{array}{l}<br />
    0,\text{ if square } (x,\ y) \text{ cannot be entered}\\<br />
    1,\text{ if } (x,\ y) \text{ is the start square}\\<br />
    \text{else }p(x\!-\!1,\ y) + p(x,\ y\!-\!1)<br />
\end{array}\right.

    You can get to a square from only two other squares. The sum of the number of paths to dose squares is the number of paths to that square.

    Then, if you turn it all 135^\circ clockwise, you will se it's starting to look like Pascal's triangle. And if it hadn't been for those two blocked squares p(x,\ y) would have been = {{x+y}\choose{y}}. Cause {x+y}\choose{y} has almost the same properties as p(x,\ y) has in this case. You do know that {{x}\choose{y}}\ =\ {{x-1}\choose{y-1}}\ +\ {{x-1}\choose{y}}? Let's say that if (x, y) is outside the triangle, {x\choose{y}}\ =\ 0. I don't know if I'm the best to explain why, but in this case

    p(x,\ y)\ =\ {{x+y}\choose{y}}\ -\ {{1+3}\choose{3}}\cdot{{(x-1) + (y-3)}\choose{y-3}}\ -\ {{4+1}\choose{1}}\cdot{{(x-4) + (y-1)}\choose{y-1}}\ =.

    =\ {{x+y}\choose{y}}\ -\ {4\choose{3}}\cdot{{x+y-4}\choose{y-3}}\ -\ {5\choose{1}}\cdot{{x+y-5}\choose{y-1}}\ =

    =\ {{x+y}\choose{y}}\ -\ 4\cdot{{x+y-4}\choose{y-3}}\ -\ 5\cdot{{x+y-5}\choose{y-1}}

    Since x=4 and y=4 in the top right square,

    p(x,\ y)\ =\ {8\choose{4}}\ -\ 4\cdot{{8-4}\choose{4-3}}\ -\ 5\cdot{{8-5}\choose{4-1}}\ =
    =\ 70\ -\ 4\cdot{4\choose{1}}\ -\ 5\cdot{3\choose{3}}\ =
    =\ 70\ -\ 4\cdot 4\ -\ 5\cdot 1\ =
    =\ 49

    Now i got it right, I forgot to use zero indexing.
    Last edited by TriKri; December 5th 2006 at 12:40 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    i'm sorry but it's getting too complicated for me,we just started with this.

    the first question was to solve this without any limitation on the squares.
    so the way I did it was like that:
    I can go RRRRRUUUUU from the start to the end.
    (R-right, U-up)
    so now I just computed the number of ways to arrange the letters.

    could you try and explain it to me,with this kind of thinking(sorry for the trouble)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Quote Originally Posted by parallel View Post
    i'm sorry but it's getting too complicated for me,we just started with this.

    the first question was to solve this without any limitation on the squares.
    so the way I did it was like that:
    I can go RRRRRUUUUU from the start to the end.
    (R-right, U-up)
    so now I just computed the number of ways to arrange the letters.

    could you try and explain it to me,with this kind of thinking(sorry for the trouble)
    Take a look at Quick's excel diagram. What it does is that it simulates the number of paths by calculating the number square by square. If you wan't to use a mathematical non-iterating formula, you will have to use the combination function as I just did in my last post.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    I will have to get back on this one. I don't seem to get the formula right.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Aug 2006
    Posts
    29
    I dont blame ya
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    I believe this is a graph theory related question (but because I am barely familar with it I cannot help you).

    Basically you want to find all the possible paths (that is how Graph theorist call them). And not walks (going over the same edge).

    So you set up a graph with 25 vertices. And you draw an edge between any two which you are allowed to move. (That means the pink dots are isolated from the rest of the graph). And there is a special techinque of how to solve this problem.*)


    *)One way is the adjancey matrix but it gets huge.
    **)Another way, there are certain algorithms related to graphs that enable to find the solution. (Again not familar with them).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    I hate to be a pain, but there are an infinite number of paths. The problem doesn't specify a maximum path length, nor that you can't, for example, take a backward step. I'm assuming either one or both of the two previous thoughts are correct, but the problem statement should have a mention of some kind of limitation of this kind.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    I think he did:

    Quote Originally Posted by parallel View Post
    you can move one step at a time:forward or to the right.


    Forward in this case I believe means "upp".
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,845
    Thanks
    320
    Awards
    1
    Quote Originally Posted by TriKri View Post
    I think he did:




    Forward in this case I believe means "upp".
    No, it was a joke. Really. (Ahem! I'm going to curl up in a little ball in this corner over here for a while, if nobody minds...)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    There are 70 ways to arrange 4-Rís & 4-Uís. That is the total number of paths from start to finish without regard to the forbidden squares.

    There are 4 ways to go from start to the left most forbidden square and 4 ways to go from that square to finish. Thus, there are 16 ways to go from start to finish passing through the first forbidden square.

    Now likewise, there are 5 ways to go from start to finish passing through the right most forbidden square.

    Now note that 70-(16+5)=49. That take the forbidden paths from the total.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    357
    Thanks
    1
    Quote Originally Posted by topsquark View Post
    No, it was a joke. Really. (Ahem! I'm going to curl up in a little ball in this corner over here for a while, if nobody minds...)
    Oh, haha. hehe. I know, I'm can be quite seriously commited to things sometimes.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. counting 1
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 8th 2011, 08:01 AM
  2. Counting AUB
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 27th 2011, 09:13 AM
  3. Counting
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: May 18th 2010, 05:45 AM
  4. help on Counting
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 08:51 AM
  5. Counting
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 10th 2009, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum