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, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446,bksl-nl 27297738, 142078746, 745387038, 3937603038, 20927156706, 111818026018,bksl-nl 600318853926, 3236724317174, 17518619320890, 95149655201962,bksl-nl 518431875418926, 2832923350929742, 15521467648875090bksl-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-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-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert schroder(2) == 6bksl-nlassert schroder(3) == 22bksl-nlassert schroder(4) == 90bksl-nlbksl-nlschroderpy-undmem = [1, 2]bksl-nlbksl-nldef schroder(n):bksl-nl if n >= len(schroderpy-undmem):bksl-nl resultat = (bksl-nl (6py-strn - 3) py-str schroder(n - 1)bksl-nl - (n - 2) py-str schroder(n - 2)bksl-nl ) // (n + 1)bksl-nl # ici schroderpy-undmem est de longueur n garantibksl-nl schroderpy-undmem.append(resultat)bksl-nl return schroderpy-undmem[n]bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert schroder(2) == 6bksl-nlassert schroder(3) == 22bksl-nlassert schroder(4) == 90bksl-nlbksl-nl

A

Z