Метод координат. Подсчет числа путей

Рассмотрим координатную сетку – двигаясь по ней помечаем каждый “перекресток” – производим суммирование числа возможных путей, ведущих на каждый перекресток

Получаем известный треугольник Паскаля

1 1

1 2 1

1 3 3 1

1 4 6 4 1

... … … … ….......

(здесь, например, 3=2+1, 6=3+3)

Поскольку на перекресток k на уровне n (считая сверху и принимая верхний уровень за нулевой) ведет

путей (число способов выбрать k движений направо вниз из общего числа n движений вниз), то свойство суммирования путей на перекрестке можно записать как

.