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