Quatre pas vers le haut et quatre vers la droite sans croiser la diagonale : 14 des 70 chemins

Le coefficient binomial central compte toutes les routes ; la formule de Catalan compte les légales.

Statistiques et données · Niveau: Résultat classique · Mis à jour le 2026-11-10

Sur une grille de 4 × 4, les routes du coin inférieur gauche au coin supérieur droit qui ne font que monter et aller à droite totalisent 8!/(4!·4!) = 70 — l'espace de travail affiche cela dans le deuxième lien. La plupart des énoncés ajoutent la règle « ne jamais passer au-dessus de la diagonale », et alors le compte est 8!/(4!·5!) = 14. Les deux formules diffèrent d'un facteur n + 1 au dénominateur, ce qui est toute la correction de Catalan.

Les 56 chemins illégaux ne sont pas éparpillés : par l'argument de réflexion, croiser la diagonale les apparie un à un avec les routes vers une extrémité décalée, et celles-là totalisent 8!/(3!·5!) = 56. Donc 70 − 56 = 14 et les deux écrans coïncident. La même suite 1, 2, 5, 14, 42 compte les façons d'insérer des parenthèses dans une chaîne de facteurs, les triangulations d'un polygone convexe et les chaînes de parenthèses légales ; le troisième lien est C₅ = 10!/(5!·6!) = 42, le suivant, qui est le nombre de triangulations d'un heptagone.

Réponse

14

Comment la lire

C₄ comme 8!/(4!·5!) sur l'espace de travail. Le deuxième lien est le compte sans contraintes 8!/(4!·4!) = 70, et le troisième est le nombre de Catalan suivant, 42.

Source

The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838

Résolvez-le dans la calculatrice

Ces liens ouvrent la calculatrice appropriée avec les nombres de ce problème déjà saisis. La ligne ci-dessus correspond à ce que l'écran devrait afficher : vérifiez par vous-même.

Ce site est un site d'outils indépendant édité par un tiers. Il n'est ni affilié à Casio, à Texas Instruments ou à leurs distributeurs, ni sponsorisé ou autorisé par eux. Les noms de modèles et de produits sont des marques commerciales de leurs détenteurs respectifs et n'apparaissent ici que pour identifier les appareils.

Les séquences de touches de ces manuels ont été rédigées à partir des propres données de disposition de ce site — les mêmes que celles qu'affiche la calculatrice en ligne — ainsi que d'informations produit accessibles au public. Les spécifications et les configurations régionales sont vérifiées sur l'appareil physique et à partir de la documentation la plus récente du fabricant.