Проблема с программой Java, которая подсчитывает количество несамопересекающихся путей между верхним левым и нижним прав ⇐ JAVA

[Anonymous]

Хорошо известно, что когда разрешено движение только вправо и вниз, количество путей между верхней левой ячейкой и нижней правой ячейкой прямоугольной сетки с длинами сторон n,m представляет собой биномиальный коэффициент n+m от n. Я пытался поразмышлять сначала математически, о количестве таких путей, по которым можно еще и двигаться влево и вверх; очевидно, что единственный способ дать осмысленный ответ на такой вопрос - это подсчитать несамопересекающиеся пути, которые не выходят за пределы прямоугольника (без этих ограничений количество путей бесконечно)
Поскольку я понятия не имел, как подсчитывать количество таких путей комбинаторно, я написал программу на Java, которая подсчитывает такие пути и печатает пути, которые я ограничил квадратными массивами. Однако уже в массиве размером 3х3 программа печатает всего 9 путей, при этом проверка количества таких путей вручную дала 12 путей. Вот программа:

Код: Выделить всё

public class pathCalculator {

public static int pathsCalculator(boolean[][] arr) {

return pathsCalculator(arr, 0, 0, "");
}

public static int pathsCalculator(boolean[][] arr, int i, int j, String s) {
if (i < 0 || i > arr.length - 1 || j < 0 || j > arr[0].length - 1) {
return 0;

} else if (arr[i][j] == false) {
return 0;
}
if (i == arr.length - 1 && j == arr[0].length - 1) {
s = s + "[" + (arr.length - 1) + "," + (arr.length - 1) + "]";
System.out.println(s);
return 1;
} else {
arr[i][j] = false;
s = s + "[" + i + "," + j + "]";
boolean[][] arr1 = new boolean[arr.length][arr.length];
for (int n = 0; n