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.