Counting pathways

**parallel** · December 5th 2006, 08:11 AM

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.

**Quick** · December 5th 2006, 11:05 AM

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.

**parallel** · December 5th 2006, 11:17 AM

I would appreciate it if you could give me an explanation,in a combinatorial way i.e n choose k

thanks

**Quick** · December 5th 2006, 11:21 AM

Originally Posted by parallel

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

**TriKri** · December 5th 2006, 11:29 AM

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.

**parallel** · December 5th 2006, 11:46 AM

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)

**TriKri** · December 5th 2006, 11:53 AM

Originally Posted by parallel

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.

**TriKri** · December 5th 2006, 12:12 PM

I will have to get back on this one. I don't seem to get the formula right.

**parallel** · December 5th 2006, 12:17 PM

I dont blame ya

**ThePerfectHacker** · December 5th 2006, 12:39 PM

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).

**topsquark** · December 5th 2006, 01:53 PM

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

**TriKri** · December 5th 2006, 01:58 PM

I think he did:

Originally Posted by parallel

you can move one step at a time:forward or to the right.

Forward in this case I believe means "upp".

**topsquark** · December 5th 2006, 02:03 PM

Originally Posted by TriKri

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

**Plato** · December 5th 2006, 02:07 PM

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.

**TriKri** · December 5th 2006, 02:42 PM

Originally Posted by topsquark

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.

Thread: Counting pathways

LinkBack

Thread Tools

Display

Counting pathways

Similar Math Help Forum Discussions

counting 1

Counting AUB

Counting

help on Counting

Counting

Search Tags