Aller au contenu

Énumération des chemins de Schröder⚓︎

Dans une grille, on souhaite compter tous les chemins allant de \((0, 0)\) à \((2n, 0)\), en restant au-dessus ou sur l'axe des abscisses, et avec les mouvements possibles suivants :

  • Nord-Est (↗), donc suivi plus tard d'un Sud-Est (↘)
  • Sud-Est (↘), qui est donc précédé d'un Nord-Est (↗) correspondant
  • Deux fois de suite à l'Est (→→)

Chaque paire (↗, ↘) est associée à un déplacement de deux unités vers l'Est. Ainsi, un chemin de Schröder fait globalement un déplacement horizontal d'un nombre pair d'unités, que l'on note \(2n\).

Objectif : Écrire une fonction telle que schroder(n) renvoie le nombre de chemins de Schröder allant de \((0, 0)\) à \((2n, 0)\).

Chemins de Schröder de longueur \(2×2\)

Il y en a 6.

Chemins de Schröder de longueur \(2×3\)

Il y en a 22.

Formule

On admettra qu'une relation pour calculer ces nombres \(S_n\) est :

  • \(S_0 = 1\), \(S_1 = 2\)
  • \((n+1)S_n = (6n-3)S_{n-1} - (n-2)S_{n-2}\), pour \(n>1\).
Exemples
🐍 Console Python
>>> schroder(2)
6
>>> schroder(3)
22
>>> schroder(4)
90

Compléter le code :

⚠ La fonction doit renvoyer un nombre entier.

###
# testsbksl-nlbksl-nlassert schroder(2) == 6bksl-nlassert schroder(3) == 22bksl-nlassert schroder(4) == 90bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlA006318 = [bksl-nl 1,bksl-nl 2,bksl-nl 6,bksl-nl 22,bksl-nl 90,bksl-nl 394,bksl-nl 1806,bksl-nl 8558,bksl-nl 41586,bksl-nl 206098,bksl-nl 1037718,bksl-nl 5293446,bksl-nl 27297738,bksl-nl 142078746,bksl-nl 745387038,bksl-nl 3937603038,bksl-nl 20927156706,bksl-nl 111818026018,bksl-nl 600318853926,bksl-nl 3236724317174,bksl-nl 17518619320890,bksl-nl 95149655201962,bksl-nl 518431875418926,bksl-nl 2832923350929742,bksl-nl 15521467648875090,bksl-nl]bksl-nlbksl-nlfor n, attendu in enumerate(A006318):bksl-nl resultat = schroder(n)bksl-nl assert isinstance(resultat, int), "Erreur, le résultat doit être entier"bksl-nl assert attendu == resultat, f"Erreur avec n = {n}"bksl-nlbksl-nl 5/5

schroderpy-undmem = [...]bksl-nlbksl-nlbksl-nldef schroder(n):bksl-nl if n >= len(schroderpy-undmem):bksl-nl resultat = ... # ... schroder(n - 1) ...bksl-nl # ici schroderpy-undmem est de longueur au moins n, garantibksl-nl schroderpy-undmem.append(...)bksl-nl return schroderpy-undmem[...]bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert schroder(2) == 6bksl-nlassert schroder(3) == 22bksl-nlassert schroder(4) == 90bksl-nlbksl-nlschroderpy-undmem = [1, 2]bksl-nlbksl-nlbksl-nldef schroder(n):bksl-nl if n >= len(schroderpy-undmem):bksl-nl resultat = ((6 py-str n - 3) py-str schroder(n - 1) - (n - 2) py-str schroder(n - 2)) // (bksl-nl n + 1bksl-nl )bksl-nl # ici schroderpy-undmem est de longueur n garantibksl-nl schroderpy-undmem.append(resultat)bksl-nl return schroderpy-undmem[n]bksl-nlbksl-nl

A

Z