В городе 4 дороги с запада на восток и 4 с севера на юг, образуя сетку. Человек идёт из северо-западного угла A в юго-восточный угол B, на каждом перекрёстке двигаясь только на восток или на юг. Сколько существует различных маршрутов?

Step-by-step solution

1. 1

   Подсчитаем количество ходов в каждом маршруте. Так как дорог по $4$ в каждом направлении, между углами по $3$ квартала в каждую сторону, значит, любой маршрут состоит ровно из

   $3\ \text{шага на восток}\quad\text{и}\quad 3\ \text{шага на юг}$

   Всего $6$ шагов — и это верно для любого маршрута, что делает задачу чисто комбинаторной.

2. 2

   Запишем маршрут как последовательность букв. Каждый маршрут полностью определяется порядком ходов, то есть строкой из $6$ букв: трёх E (восток) и трёх S (юг), например, $EESESS$. Разные строки соответствуют разным маршрутам, и наоборот, поэтому задача сводится к подсчёту таких строк.

3. 3

   Выберем позиции для шагов на восток. Если выбрать, на каких $3$ из $6$ позиций будет стоять E, остальные займут S. Число способов выбрать такие позиции:

   $\binom{6}{3}$

4. 4

   Вычислим биномиальный коэффициент.

   $\binom{6}{3}=\frac{6!}{3!\,3!}=\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}=20$

   $\boxed{20\ \text{маршрутов}}$

5. 5

   Проверим по треугольнику Паскаля на сетке. Если подписать на каждом перекрёстке число маршрутов из $A$, то верхний ряд и левый столбец будут состоять из одних $1$, а каждое внутреннее число — сумма числа сверху и слева. Получаются строки $1,1,1,1$ / $1,2,3,4$ / $1,3,6,10$ / $1,4,10,20$ — и в углу $B$ стоит $20$, что совпадает с биномиальным подсчётом.