Euler 015

Publié le 22/12/16

Soit {N} un entier positif. Si on part du coin en haut à gauche d’une grille de {N\times N} points, et si les seuls déplacements autorisés sont d’un point vers la droite ou vers le bas, combien y a-t-il de routes possibles jusqu’au coin en bas à droite?
Dans l’énoncé initial du « Project Euler », on a {N=20}, et la réponse est {137846528820}.
  1. Première solution

    Il faut effectuer 2N déplacements, dont {N} vers la droite et {N} vers le bas.
    Le nombre de routes possibles est {r_{n}=\displaystyle\binom{2n}{n}=\dfrac{(2n)!}{(n!)^{2}}}.
    Plutôt que d’utiliser des factorielles, on note que
    {r_{0}=1} et {r_{n+1}=\dfrac{(2n+2)(2n+1)}{(n+1)^{2}}r_{n}=\dfrac{2(2n+1)}{n+1}r_{n}} pour tout {n}.

  2. Deuxième solution

    Voici une solution moins glorieuse, en important la fonction factorial du package math