# Finding all possible paths from one corner to the other on a grid, without backtracking

Me again "new to maths guy". Please tell me if the substance of my questions are not a good fit for the site.

I'm now onto Question 15 of Project Euler and it seems like there's some mathematical path finding technique I should use.

Looking around I've found graph and tree traversal, djikstras shortest path and some others but none are quite appropriate.

I would be grateful If you would be so kind as to link me to documentation in this regard.

thanks

-
No graph algorithm is necessary. – user3533 May 13 '12 at 8:54
How many steps do you have in each such route? How many of which are down and how many are right? – user3533 May 13 '12 at 8:55
Oh, I may have misread the question, I thought only right and down moves are allowed. – user3533 May 13 '12 at 8:57
Do you have the distances between every 2 nodes in the grid? If so , then you can try using Floyd Algorithm en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm – Bhargav May 13 '12 at 9:11
We have been asked by the Project Euler people not to discuss their problems here. – Gerry Myerson May 13 '12 at 12:39

Minor hint:
You can encode any path uniquely by a sequence of 20 zeros and ones, with 10 zeros and 10 ones. 0 representing down, 1 representing right. And every such sequence determines a valid path.

Level 2 hint:
We are looking for the number of ways to choose 10 elements from a 20 element set. Not too hard to derive the general formula.

Solution:
Use the binomial formula to calculate the number of ways to choose k elements from a set of n,

$$\binom{n}{k}:= \frac{n!}{k!(n-k)!}$$

-
There may be something to this but I must need to think about it some more. Cheers. – gyaresu May 13 '12 at 9:26
It might be hard to figure out if you havent had combinatorics before, but we are looking for the number of ways to choose 10 elements from a 20 element set. – TROLLKILLER May 13 '12 at 9:27
Those brackets are just a way to label the function, instead of writing f(n,k), because its a commonly used function. And that colon means the left side is defined as the right side. – TROLLKILLER May 13 '12 at 10:03
Well, this crap-easy problem is common knowledge and part of math-currilicum and cant really be attributed to project euler. – TROLLKILLER May 13 '12 at 13:11
@MaoYiyi There is a button next to the answer with the same function as your comment. ;-) – TROLLKILLER May 13 '12 at 17:18