Quatro passos para cima e quatro para a direita sem cruzar a diagonal: 14 dos 70 caminhos

O coeficiente binomial central conta todas as rotas; a fórmula de Catalan conta as legais.

Estatística e dados · Nível: Resultado clássico · Atualizado em 2026-11-10

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.

Este é um site de ferramentas independente de terceiros. Não é afiliado à Casio, à Texas Instruments nem aos seus distribuidores, e não conta com patrocínio ou autorização deles. Os nomes de modelos e produtos são marcas comerciais de seus respectivos titulares e aparecem aqui apenas para identificar os dispositivos.

As sequências de teclas destes manuais foram redigidas a partir dos próprios dados de layout deste site — os mesmos que a calculadora online renderiza — junto com informações de produto disponíveis publicamente. As especificações e as configurações regionais são verificadas no dispositivo físico e no material mais recente do fabricante.