Калькулятор счётчика решётчатых путей

Введите ширину и высоту сетки, чтобы подсчитать монотонные решётчатые пути.

Как пользоваться

  1. Введите нужные значения в поля.
  2. Нажмите «Рассчитать», чтобы увидеть результат.
  3. Скопируйте или поделитесь результатом с помощью кнопки «Поделиться».

Об этом калькуляторе

Монотонный путь по решётке на сетке m × n — это маршрут из одного угла в противоположный, при котором по линиям сетки можно двигаться только вправо или вверх (никогда влево или вниз). Число таких путей — классический результат комбинаторики: поскольку любой путь состоит ровно из m шагов вправо и n шагов вверх в некотором порядке, общее число равно биномиальному коэффициенту C(m+n, m) — числу способов выбрать, какие m из m+n шагов будут шагами «вправо».

Это один из первых нетривиальных результатов, которые изучают в курсах комбинаторики и дискретной математики, и он напрямую связан с треугольником Паскаля, биномиальными коэффициентами и принципом отражения, который применяют для более сложных задач подсчёта, например путей, не пересекающих диагональ (на этом основаны числа Каталана). Студенты-программисты встречают ту же структуру в задачах динамического программирования на сетках, где подсчёт путей по решётке — стандартная разминка перед задачами с подсчётом взвешенных путей или путей с обходом препятствий.

Была ли эта страница полезной?

Можно выбрать до 3 реакций.

Комментарии

  • Оставьте первый комментарий.

Популярные калькуляторы

Все калькуляторы