Caminhos monótonos em grade em uma malha a×b

Este contador de caminhos em grade devolve quantas rotas monótonas viajam da origem (0, 0) até o ponto de grade (a, b), usando apenas passos para a direita e passos para cima. Essa contagem clássica de combinatória é igual ao coeficiente binomial C(a + b, a), que é o mesmo que C(a + b, b), porque todo caminho é uma sequência de exatamente a movimentos para leste, e b movimentos para norte. Verificações familiares incluem um quadrado dois por dois, com seis caminhos, um retângulo dois por três, com dez caminhos, e um corredor degenerado, de largura zero, em que a única rota é uma única subida vertical. O mecanismo avalia o binomial com um produto determinístico em BigInt, então grades grandes mantêm cada dígito, em vez de deslizar para ruído de ponto flutuante. Não há chamadas de rede, nenhuma amostra de Monte Carlo, e nenhum atalho baseado em data.

O que significam os caminhos monótonos em grade e o que a resposta contém

Um caminho monótono em grade, na malha inteira do plano, é um passeio que começa em (0, 0), e termina em (a, b), tomando apenas passos unitários para a direita (1, 0), e passos unitários para cima (0, 1). Como você nunca se move para a esquerda ou para baixo, todo caminho válido é simplesmente um ordenamento de a movimentos para a direita, e b movimentos para cima, e o número de ordenamentos distintos é o coeficiente binomial C(a + b, a).

Essa identidade é a espinha dorsal de inúmeros exercícios de matemática discreta: estudantes primeiro a encontram ao contar rotas por uma malha de quarteirões da cidade, depois quando relacionam coeficientes binomiais a passeios aleatórios que só avançam para leste e para norte, e novamente quando comparam caminhos monótonos irrestritos com caminhos restritos por Catalan, que permanecem abaixo de uma diagonal.

Esta calculadora devolve os a e b solicitados, a contagem exata de caminhos como uma string decimal, a soma a + b, uma pequena etiqueta de fórmula, como C(5, 2), e os máximos publicados, para que os clientes validem antes de enviar um lote. Dimensões negativas não têm significado para uma contagem de caminho monótono em grade, então falham rapidamente, com uma mensagem específica de campo, em vez de devolver zero silenciosamente.

Onde as contagens de caminhos em grade se encaixam nos estudos, no código e na modelagem

Estudantes encontram caminhos monótonos em grade quando um livro didático pergunta quantas rotas mais curtas cruzam uma malha de cidade a por b, quando um exercício de coeficiente binomial precisa de uma história geométrica, ou quando precisam comparar contagens de caminhos irrestritos com números de Catalan, que proíbem caminhos acima da diagonal principal. Professores podem pré-gerar gabaritos para a e b modestos, sem confiar em aplicativos de calculadora opacos, que arredondam inteiros grandes, ou trocam silenciosamente para notação científica.

Desenvolvedores chamam o mesmo contrato a partir de scripts para gerar vetores de teste determinísticos, dimensionar modelos de navegação em grade, ou atender enunciados de desafios de programação que exigem o valor exato de C(a + b, a), em vez de uma aproximação em espaço logarítmico. A prática de competições costuma precisar de uma fonte rápida e offline de ordens de grade, para que as soluções possam ser conferidas sem baixar tabelas da OEIS sob pressão de tempo.

Analistas de produto e de pesquisa usam a contagem ao estimar quantas sequências monótonas de decisões, a leste e b norte, existem, o que aparece em laboratórios de sequenciamento, demonstrações introdutórias de probabilidade, e listas de exercícios de combinatória enumerativa.