0

I am attempting to solve Project Euler prob. 204 by hand, and I decided that this method should help a lot.

I have the following grid:

enter image description here

The numbers indicate the total number of paths from a node at the base to all the nodes on the top. Conditions below apply.

The width and height can go up to infinity. A node can only connect to one that is above its row, and that is either directly above or anywhere to the right of the node (If it was not understood by the first restriction, a node cannot connect to one that is directly to the right. Must be 1 above.).

Is there a formula that can show the number of paths through the grid above, with any given width and height? If so, please explain.

user3373311
  • 3

1 Answers1

2

Hint. Suppose you want to get from a starting node to a node at most $n$ steps to the right and $m$ steps above. You will have to visit exactly one node at each level above the start; say the node visited at level $k$ is $a_k$ steps to the right of the start. Then we have $$0\le a_1\le a_2\le\cdots\le a_{m-1}\le a_m\le n\ ,\tag{$*$}$$ and conversely, each $m$-tuple $(a_1,\ldots,a_m)$ will give a possible path. So, you need to count the number of $m$-tuples satisfying $(*)$.

One way to do this: let $b_k=a_k+k$ for each $k$. Then we need $$0<b_1<b_2<\cdots<b_{m-1}<b_m\le n+m\ .$$

Can you take it from here?

David
  • 82,662
  • Yup, that's the good place to start ; +1, that was a good hint. – Patrick Da Silva May 06 '14 at 01:32
  • May by a silly question, but what does the (*) represent? I'm a bit confused on what exactly a (m-1)-tuple should satisfy. – user3373311 May 06 '14 at 01:50
  • E.g, if $m=4$, $n=6$, $a_1=3$, $a_2=3$, $a_3=4$ it represents the path $$(0,0)\to(1,3)\to(2,3)\to(3,4)\to(4,6)\ .$$ – David May 06 '14 at 01:56
  • It finally got to me that the $(*)$ stands for the condition you listed. Truly, I knew that this condition applied when I was searching for a pattern. Unless I'm missing what I'm looking for, this doesn't seem to answer the question. My question is how to get the number of tuples satisfying the condition. – user3373311 May 06 '14 at 02:13
  • @user3373311 : Count! This answer gives you a hint as to how to count it. If you want a full answer, then ask for it. – Patrick Da Silva May 06 '14 at 02:53
  • 1
    user3373311, see slight revision and additional hint. @PatrickDaSilva FYI ;-) – David May 06 '14 at 03:35
  • Thank you for your patience with this question. While I have not used your hint entirely in my solution, your answer has got me to illustrate some further examples, and realize that the number of paths is associated with Pascal's triangle. Once again, thanks for the help. I have marked this as answered. – user3373311 May 06 '14 at 03:44