Euler problem 15

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?


Solution:

Wanneer we het grid 20x20 met het eindpunt omhoog vastpakken, krijgen we 
onderstaande driehoek:

                 1
               1   1
             1   2   1
           1   3   3   1
rij 4-> 1   4   6   4   1     
       1   5  10   10  5   1
     1   6  15   20  15  6   1
   1   7   21  35  35  21  7   1
 1   8   28  56  70  56  28  8   1


 De getallen in de driehoek geven het aantal wegen aan vanaf dat getal naar de top.
 Zo zijn vanuit het getal 2 precies twee wegen naar de top.
 Omdat er steeds 2 keuzes zijn om van een getal de weg naar de top te vervolgen is
 een getal gelijk aan som van beide bovenliggende getallen.
 Het "toeval" wil dat bovenstaande eigenschap overeen komt met de driehoek van Pascal!

 De getallen in de driehoek kunnen we met de binominaal formule berekenen.

 B(n/k) = n!/(k!*(n-k)!)

 Hierin is rij n de macht en k de plaats v/d coefficienten in een n'e graads vergelijking.
 Voor een 4e graads vergelijking (a+b)^4 krijgen we de coefficienten: 1 4 6 4 1

 Het beginpunt voor een grid 2 x 2 is n=4 en k=2 -> aantal wegen is B(n/k)=4!/2!*2! = 6.
 Het beginpunt voor een grid 3 x 3 is n=6 en k=3 -> aantal wegen is B(n/k)=6!/3!*3! = 20.

Het antwoord op de gestelde vraag is dus:
Het beginpunt voor een grid 20 x 20 is n=40 en k=20 -> aantal wegen is B(n/k)=40!/20!*20! =

Problem15 =137846528820 elapsed time:    0 ms. Test Passed.