# Thread:

1. ## 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

2. 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
• PathWays.xls (13.5 KB, 75 views)

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

thanks

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

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

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

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

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

9. I dont blame ya

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

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

12. 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".

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

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

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

#### Search Tags

View Tag Cloud

Copyright © 2005-2013 Math Help Forum. All rights reserved.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 25, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.949786901473999, "perplexity_flag": "middle"}