Шашка на доске NxN: число путей вправо и вниз

Условие

Перед вами шахматная доска размером N × N. В верхнем левом углу находится шашка. Шашка может двигаться только вправо или вниз (вверх или влево двигаться нельзя). Сколькими различными путями шашка может прийти в нижний правый угол?

Решение

Шаг 1. Формализуем переходы

Доска N × N — это сетка из N строк и N столбцов клеток. Чтобы из верхнего левого угла попасть в нижний правый, шашке нужно сделать ровно:

• N − 1 ходов вниз (D),
• N − 1 ходов вправо (R).

Всего 2(N − 1) ходов. Каждый путь — это последовательность из N − 1 буквы D и N − 1 буквы R в произвольном порядке.

Шаг 2. Считаем размещения

Число различных путей = число способов выбрать, в каких из 2(N − 1) позиций будут стоять, скажем, ходы вниз:

C(2(N − 1), N − 1) = (2(N − 1))! / ((N − 1)! · (N − 1)!)

Шаг 3. Малые значения для проверки

Для классической шахматной доски 8 × 8 ответ — 3432 пути.

Шаг 4. Альтернативный вывод через DP

Можно посчитать рекурсивно: paths(i, j) = paths(i − 1, j) + paths(i, j − 1), где paths(0, j) = paths(i, 0) = 1. Это треугольник Паскаля, повёрнутый на 45° — значение в клетке (N − 1, N − 1) равно C(2(N − 1), N − 1).

from math import comb
 
def paths(N):
    return comb(2 * (N - 1), N - 1)
 
# DP-проверка
def paths_dp(N):
    dp = [[1] * N for _ in range(N)]
    for i in range(1, N):
        for j in range(1, N):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[N-1][N-1]
 
for N in [1, 2, 3, 4, 5, 8]:
    print(N, paths(N), paths_dp(N))
# 1 1 1
# 2 2 2
# 3 6 6
# 4 20 20
# 5 70 70
# 8 3432 3432

Шаг 5. Сложность

• Через формулу: O(N) на одно вычисление факториала / биномиального коэффициента.
• Через DP: O(N²) времени и O(N) памяти (если хранить только текущую строку).

Подводные камни

1. Путаница «доска N×N» — это N клеток или N линий? Если N — число клеток, то ходов всего 2(N − 1). Если в задаче было бы «сетка N × N узлов», то ходов было бы 2N. Здесь — клетки.
2. Сторона N ≠ число «сделанных ходов». Частая ошибка — записать C(2N, N). Это неверно для доски N × N клеток, потому что внутри N клеток только N − 1 границ между ними.
3. Перепутать C(2(N-1), N-1) и C(2(N-1), 2). Биномиальный коэффициент — про выбор позиций для одного из двух типов ходов.
4. При больших N ответ растёт примерно как 4^N / √(πN) (формула Стирлинга для центрального биномиального коэффициента). Для N = 8 уже 3432; для N = 20 — порядка 10^10.

Эталонный ответ

C(2(N − 1), N − 1) = (2N − 2)! / ((N − 1)!)².

Для N = 8: 3432.