20 de noviembre de 2013

Lattice paths - Project Euler, problema 15

El problema es el siguiente:
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
Este es un problema sencillo de combinatoria. Solamente podemos hacer 2 tipos de movimientos: derecha (D) y abajo (A), de tal manera que las rutas posibles las podemos escribir como una cadena de 'D's y 'A's, en el ejemplo tenemos que contar las combinaciones de 2 D y 2 A, que no es otra cosa que:
$\frac{(2+2)!}{2!2!}=\frac{4!}{2!2!}=3!=6$
Dicho lo anterior, es fácil ver el patrón: si tenemos un cuadrado de lado k, tenemos $\frac {(2k)!}{k!k!}={2k \choose k}$
en particular para k=20
${40 \choose 20}$
Así, el código es el siguiente:
format long;%para que muestre el número completo
k=20;%lado
nchoosek(2*k,k)