Voici un petit résumé de l'énoncé du problème 15 "Lattice paths" du Project Euler (traduction complète en français ici) :

How many such routes are there through a 20x20 grid ? (voir énoncé complet)

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de routes différentes possibles pour aller du coin en haut à gauche au coin en bas à droite d'une grille 20x20 (voir énoncé complet) en se déplaçant vers le bas ou vers la droite. Une première remarque est que pour une grille \(n \times n\), il nous faudra aller \(n\) fois vers la droite et \(n\) fois vers le bas.

Essayons maintenant de voir le problème non plus comme le nombre de déplacement possible sur une grille, mais plutôt comme le nombre de combinaisons possibles pour tirer, de manière aléatoire, dans un sac contenant 1 boule rouge et 1 boule noire, \(n\) fois la boule rouge si l'on a \(2n\) tirages. Ainsi, cette 2ème façon de voir le problème nous permet de faire appel à la loi binomiale et de calculer le nombre de combinaison de \(n\) éléments par \(2n\), que l'on note aussi \({2n\choose n}\) et que l'on calcule grâce à la formule :

$${2n\choose n} =\frac{2n!}{n!(2n-n)!} = \frac{2n!}{(n!)^2}$$

Vérifions donc si cette formule donne le bon résultat pour une grille 2x2 par exemple. Nous avons donc :

$${4\choose 2} =\frac{4!}{(2!)^2} = 6$$

ce qui correspond bien au résultat attendu.

Maintenant que nous avons trouvé le raisonnement et surtout la formule à utiliser pour résoudre ce problème, nous pouvons passer au programme.

Le programme

Voici donc le programme Python que nous pouvons utiliser pour résoudre ce problème :

import math
n = 20
resultat = math.factorial(2*n)//(math.factorial(n)**2)
print(resultat)

Ce programme, qui n'est qu'une simple application de la formule, est relativement simple, d'autant plus que Python possède dans sa bibliothèque math, une fonction permettant déjà de calculer la factorielle d'un nombre.

Le résultat

La réponse à ce problème est 137846528820.