2
$\begingroup$

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

  • 0
    I refer you to the discussion at http://meta.math.stackexchange.com/questions/1090/re-project-euler-questions and the links given there.2012-05-14

1 Answers 1

2

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)!} $

  • 1
    @$M$aoYiyi There is a button next to the answer with the same function as your comment. ;-)2012-05-13