Em uma grade de 4 × 4, as rotas do canto inferior esquerdo ao superior direito que só sobem e vão para a direita somam 8!/(4!·4!) = 70 — a área de trabalho imprime isso no segundo link. A maioria acrescenta a regra “nunca passar acima da diagonal”, e então a contagem é 8!/(4!·5!) = 14. As duas fórmulas diferem por um fator n + 1 no denominador, que é toda a correção de Catalan.
Os 56 caminhos ilegais não estão espalhados: pelo argumento de reflexão, cruzar a diagonal os emparelha um a um com as rotas até uma extremidade deslocada, e essas somam 8!/(3!·5!) = 56. Então 70 − 56 = 14 e as duas telas coincidem. A mesma sequência 1, 2, 5, 14, 42 conta as maneiras de inserir parênteses em uma cadeia de fatores, as triangulações de um polígono convexo e as cadeias de parênteses legais; o terceiro link é C₅ = 10!/(5!·6!) = 42, o seguinte, que é o número de triangulações de um heptágono.
Resposta
14
Como ler
C₄ como 8!/(4!·5!) na área de trabalho. O segundo link é a contagem sem restrições 8!/(4!·4!) = 70, e o terceiro é o próximo número de Catalan, 42.
Fonte
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
Resolva na calculadora
Estes links abrem a calculadora adequada com os números deste problema já escritos. A linha de cima é o que a tela deveria mostrar: confira você mesmo.