Le moi dernier, Danny nous proposait dans le fort sympathique MPO93 de calculer la racine digitale d'un nombre de façon récursive.
Dans le même esprit, je vous propose aujourd'hui de composer un code aussi court ou performant que possible permettant de calculer sur nos calculettes et pockets préférés le nombre Mn correspondant au n-ième terme de la série des Nombres de Motzkin.
Le code attendu ne semble présenter aucune difficulté technique, on entre l'indice n et la calculette affiche (ou imprime) le nombre de Motzkin Mn correspondant. Il n'y a rien de compliqué.
Le nombre de Motzkin Mn d'indice n est le nombre de façons de choisir des cordes ne se coupant pas, parmi les cordes reliant n points disposés sur un cercle. Les nombres de Motzkin satisfont la relation de récurrence suivante :
avec et
Les nombres de Motzkin correspondent à la suite A001006 de l'OEIS et les premiers de ces nombres sont:
Code : Tout sélectionner
Nombres de Motzkin:
n │ 0│ 1│ 2│ 3│ 4│ 5│ 6│ 7│ 8│ 9│ 10│ ...
─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────
Mn │ 1│ 1│ 2│ 4│ 9│ 21│ 51│ 127│ 323│ 835│ 2188│ ...