Помощь с решением и по возможности объяснение 15 задачи Эйлера?

Question

[d201]

Начиная в левом верхнем углу сетки 2×2 и имея возможность двигаться только вниз или вправо, существует ровно 6 маршрутов до правого нижнего угла сетки.

Сколько существует таких маршрутов в сетке 20×20?

Comments

[AVKor]

https://qna.habr.com/help/rules, п.5.12

Answer 1

[Molex20021]

1. Решение через рекурсию. Предположим, что мы находимся в точке (i,j). В эту точку мы могли попасть из точек (i-1,j) or (i, j-1). То есть, мы должны получить число таких маршрутов для обеих точек и сложить - получим число маршрутов для точки (i,j). Таким образом, осталось определить базу рекурсии - это случай точки (1,1) - если на вход функции подалась такая точка вернем 1.

2. Решение математическое(@alexbrofit)
Исходя из возможностей движения, нам достаточно определить точки по горизонтали, где нужно спуститься вниз - это будет одним маршрутом. Таким образом, нужно вычислить кол-во таких способов расставить места спусков(тут отсылаю к задаче о шариках и коробках - гугл в помощь. Тут коробки это вертикальные точки, а шарики - горизонтальные)

Answer 2

[alexbprofit]

from math import factorial
def nck(n,k):
	return factorial(n)/(factorial(k)*factorial(n-k))