Énumération des chemins dans une grande grille⚓︎

Dans une grande grille de taille $n×m$, on souhaite compter tous les chemins allant du coin inférieur gauche (au Sud-Ouest) vers le coin supérieur droit (au Nord-Est).

Dans cet exercice, on pourra avoir $0\leqslant n \leqslant 1000$ et $0\leqslant m \leqslant 1000$.

Les seuls mouvements autorisés sont :

↑ Aller au Nord d'une unité.
→ Aller à l'Est d'une unité.

Les chemins pour aller de $(0, 0)$ à $(4, 3)$

Il y en a 35.

Écrire une fonction telle que nb_chemins(n, m) renvoie le nombre de chemins allant de $(0, 0)$ jusqu'à $(n, m)$.

Pour ce faire, on admettra que nb_chemins(n, m) est égal à $\binom{n}{n+m}$.

\[\binom{n}{n+m} = \dfrac{(n+m)!}{n!m!}\]

Où :

$n! = 1×2×3×\cdots×(n-1)×n$
$m! = 1×2×3×\cdots×(m-1)×m$
$(n+m)! = 1×2×3×\cdots×(n+m-1)×(n+m)$

Utilisation pour nb_chemins(4, 3)

$4! = 1×2×3×4$
$3! = 1×2×3$
$(4+3)! = 1×2×3×4×5×6×7$

\[\binom{4}{4+3} = \dfrac{1×2×3×4×5×6×7}{1×2×3×4~×~1×2×3}\]

\[\binom{4}{4+3} = \dfrac{5×6×7}{1×2×3} = 35\]

Utilisation pour nb_chemins(n, m)

$n! = 1×2×3×\cdots×n$
$m! = 1×2×3×\cdots×m$
$(n+m)! = 1×2×3×\cdots×(n+m) = 1×2×3×\cdots×n×(n+1)×\cdots×(n+m)$

\[\binom{n}{n+m} = \dfrac{1×2×3×\cdots×(n+m)}{1×2×3×\cdots×n~×~1×2×3\cdots×m}\]

\[\binom{n}{n+m} = \dfrac{\xcancel{(1×2×3×\cdots×n)}~×~(n+1)×\cdots×(n+m)}{\xcancel{1×2×3×\cdots×n}~×~1×2×3×\cdots×m}\]

En conclusion

On déduit la formule simple, à utiliser ici :

nb_chemins(n, m) est égal à $\dfrac{(n+1)×(n+2)×(n+3)×\cdots×(n+m)}{1×2×3×\cdots×m}$

Pour calculer nb_chemins(n, m),
- on fera une boucle pour calculer le numérateur
- et une autre boucle pour calculer le dénominateur
- on terminera par la division entière.
Il sera interdit d'utiliser le module math

Exemples

🐍 Console Python

>>> nb_chemins(3, 3)
20
>>> nb_chemins(4, 2)
15
>>> nb_chemins(4, 3)
35

Contraintes : Ici, $0\leqslant n \leqslant 1000$ et $0\leqslant m \leqslant 1000$.

###

∞/∞

def nbpy-undchemins(n, m):bksl-nl numerateur = ...bksl-nl for i in range(...):bksl-nl numerateur = ...bksl-nl denominateur = ...bksl-nl for i in range(...):bksl-nl denominateur = ...bksl-nl return numerateur ... denominateurbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undchemins(3, 3) == 20bksl-nlassert nbpy-undchemins(4, 2) == 15bksl-nlassert nbpy-undchemins(4, 3) == 35bksl-nlbksl-nldef nbpy-undchemins(n, m):bksl-nl numerateur = 1bksl-nl for i in range(n + 1, n + m + 1):bksl-nl numerateur py-str= ibksl-nl denominateur = 1bksl-nl for i in range(1, m + 1):bksl-nl denominateur py-str= ibksl-nl return numerateur // denominateurbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undchemins(3, 3) == 20bksl-nlassert nbpy-undchemins(4, 2) == 15bksl-nlassert nbpy-undchemins(4, 3) == 35bksl-nlbksl-nl

Pour calculer un produit, on initialise le produit à 1, et non à 0.

Une somme vide est égale à 0.
Un produit vide est égal à 1.

Pour la boucle, on peut écrire resultat *= facteur à la place de resultat = resultat * facteur. De la même manière qu'on peut écrire resultat += terme à la place de resultat = resultat + terme

Il existe aussi les raccourcis

-=, pour la soustraction
//=, pour la division entière
%=, pour le modulo
/=, pour la division continuée
**=, pour la puissance
<<= pour le décalage de bits à gauche
>>= pour le décalage de bits à droite

Formule à justifier ; maths⚓︎

Justifions la formule : nb_chemins(n, m) est égal à $\binom{n}{n+m}$.

\[\binom{n}{n+m} = \dfrac{(n+m)!}{n!m!}\]

On rappelle que pour compter le nombre de façons de choisir $k$ éléments parmi $n$, on utilise le coefficient binomial $\binom{k}{n}`.

Un chemin allant de $(0, 0)$ jusqu'à $(n, m)$ peut être décrit par une suite de E et de N ; E pour aller à l'Est, N pour aller au Nord. Il doit y avoir $n$ fois la présence de E, et $m$ fois la présence de N.

Il y a autant de chemins allant de $(0, 0)$ jusqu'à $(n, m)$ que de mots de $n+m$ lettres composés de $n$ E et $m$ N. Pour compter ces mots, il suffit de compter le nombre de façons de choisir $n$ positions parmi les $n+m$ pour placer les E. On remarquera que $\binom{n}{n+m} = \binom{m}{n+m}$, et choisir les N impose les E tout autant. Ce qui justifie la formule donnée.