En una cuadrícula de 4 × 4, las rutas de la esquina inferior izquierda a la superior derecha que solo suben y van a la derecha suman 8!/(4!·4!) = 70 —el banco de trabajo lo imprime en el segundo enlace—. La mayoría añade la regla «no pasar nunca por encima de la diagonal», y entonces el recuento es 8!/(4!·5!) = 14. Las dos fórmulas difieren en un factor n + 1 en el denominador, que es toda la corrección de Catalan.
Los 56 caminos ilegales no están dispersos: por el argumento de reflexión, cruzar la diagonal los empareja uno a uno con las rutas hacia un extremo desplazado, y esas suman 8!/(3!·5!) = 56. Así que 70 − 56 = 14 y las dos pantallas coinciden. La misma sucesión 1, 2, 5, 14, 42 cuenta las maneras de insertar paréntesis en una cadena de factores, las triangulaciones de un polígono convexo y las cadenas de paréntesis legales; el tercer enlace es C₅ = 10!/(5!·6!) = 42, el siguiente, que es el número de triangulaciones de un heptágono.
Respuesta
14
Cómo leerla
C₄ como 8!/(4!·5!) en el banco de trabajo. El segundo enlace es el recuento sin restricciones 8!/(4!·4!) = 70, y el tercero es el siguiente número de Catalan, 42.
Fuente
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
Resuélvelo en la calculadora
Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.