Количество способов прохождения матрицы N * N с использованием перестановок и комбинаций

Question

Идея состоит в том, чтобы перемещаться из верхнего левого угла в нижний правый угол матрицы N * N, где допускается только движение вниз или вправо. Обратное отслеживание не допускается. Это просто при использовании динамического программирования, как показано в следующей ссылке geeks for geeks . Я пытался понять, как этого можно достичь с помощью простых перестановок и комбинаций. Я наткнулся на следующую BetterExplained ссылку. Несомненно, есть несоответствие в проблеме, которую они решают. Есть ли способ найти решение, используя перестановку и комбинацию? Указатель, который может помочь мне лучше понять решение?

Редактировать 1:

Ниже приведен пример матрицы 3X3 , когда мы используем динамическое программирование, оно показывает 6 способов добраться от крайней левой точки до самой нижней правой точки, что возможно только при использовании формулы 2(N-1)!/ (N-1)!(N-1)!. но я перечислил 20 способов добраться от пункта отправления до пункта назначения внизу, что составляет 2N!/N!*N!, или возможно, что я неправильно понял вопрос, это то, что мы уже находимся в самой верхней левой ячейке и переходим к правой нижней самой ячейке, в этом случае ответ будет 6

Answer 1

Есть (n-1) among 2(n-1) способ пройти матрицу n*n с правилами, которые вы дали.

Простое объяснение: поскольку допускаются только движения downward или rightward, длина пути должна быть точно 2(n-1).
Более того, на этом пути будут n-1 ходы downward и n-1 ходы rightward (это единственный возможный способ достичь нижнего правого угла из верхнего левого угла).
Таким образом, (n-1) among 2(n-1) исходит из всех возможных способов подгонки ходов n-1 вниз в пределах ходов 2(n-1), которые нужно выполнить.

Answer 2

Если матрица квадратная (N x N), я считаю, что число путей можно рассчитать следующим образом, где n = N - 1:

from math import factorial

def number_of_paths(n):
    return int(factorial(2 * n) / (factorial(n) ** 2))

А почему ... это немного сложнее. Прежде всего, вместо того, чтобы думать о движении вниз и вправо, давайте повернем матрицу на 45 градусов, чтобы мы всегда шли вниз, но выбираем влево или вправо.

Наша матрица теперь представляет собой алмаз, стоящий на его конце и образующий центр треугольника Паскаля . Это означает, что мы можем посмотреть на биномиальный коэффициент в центре нижнего ряда треугольника Паскаля, который в два раза больше нашей матрицы - 1.

Мы используем биномиальный коэффициент, потому что одна из его интерпретаций - это количество путей, которые мы можем выбрать, чтобы туда добраться.

Например, в случае 3 x 3, 2 * 3 - 1 = 5:

       [1]                          C(0,0)
     [1   1]                    C(1,0), C(1,1)
   [1   2   1]              C(2,0), C(2,1), C(2,2)
  1  [3   3]   1        C(3,0), C(3,1), C(3,1), C(3,1)
1   4 [!6!]  4   1  C(4,0), C(4,1), C(4,2), C(4,3), C(4,4)

   Answer is 6!              Answer is C(4, 2)!

Ответ оказывается (2n)! / n! ** 2 (вывод ниже), который мы можем вычислить напрямую.

Вы также можете обобщить на неквадратные матрицы, перемещая элемент в нижнем ряду, который вас интересует, и в этот момент вы в итоге просто набираете C(n, k). Надеюсь, понятно почему.

Только математика!

Из приведенной выше диаграммы видно, что первые три значения для N:

N | Value
- + -------
1 | C(0, 0)
2 | C(2, 1)
3 | C(4, 2)

Таким образом, мы видим, что ответ:

= C(2(N - 1), N - 1)

let n = N-1
Given C(a, b) = a! / b!(a - b)!

= C(2n, n)
= (2n)! / n!(2n - n)!
= (2n)! / n! ** 2

Геометрическая интерпретация длины пути

Представьте себе матрицу 4x4, чтобы попытаться понять, почему длина составляет 2(N-1). Сначала несколько замечаний:

• Все длины пути идентичны
• Поэтому мы можем рассмотреть любой конкретный путь для проверки длины для всех
• Поэтому давайте рассмотрим путь от:
  • Сверху слева на верх справа (все идет направо)
  • Затем сверху справа внизу справа (все вниз)

Для начала мы начнем с левого верхнего угла, где не было сделано никаких шагов, и продвигаемся вдоль верхней стороны:

0 - - -     0 1 - -     0 1 2 -     0 1 2 3
- - - -  >  - - - -  >  - - - -  >  - - - -  
- - - -     - - - -     - - - -     - - - - 
- - - -     - - - -     - - - -     - - - -

После 3 ходов мы пересекли длину 4 стороны. Таким образом, для стороны длины N требуется N-1 перемещения для перемещения. То же самое верно для вертикали, нам понадобится еще N-1 ходов для перемещения сверху вниз:

0 1 2 3     0 1 2 3     0 1 2 3     0 1 2 3
- - - -  >  - - - 4  >  - - - 4  >  - - - 4  
- - - -     - - - -     - - - 5     - - - 5 
- - - -     - - - -     - - - -     - - - 6

Следовательно, общая длина пути составляет 2(N-1)