19. Пути по решётке из O(0,0) в A(m,n)
Путь по клетчатой решётке, в котором разрешены только шаги вправо и вверх, записывается словом из нулей (вправо) и единиц (вверх). Чтобы попасть из в , нужно сделать шагов вправо и вверх. Поэтому путей столько же, сколько слов с нулями и единицами: .
Что пригодится из прошлого: сочетания — выбор мест для нулей; перестановки с повторяющимися элементами — слова из нулей и единиц; правило Паскаля — оно окажется внутри картинки решётки. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Что такое решётка и путь
Рассмотрим на плоскости точки с целыми координатами: это пары целых чисел, то есть декартово произведение .
Целочисленная решётка размера — это прямоугольник на координатной плоскости с вершинами и . Вершинами (узлами) решётки называют точки этого прямоугольника с целыми координатами. Ребро — отрезок между двумя соседними вершинами на одной горизонтали или одной вертикали.
Двигаться по решётке разрешено только в двух направлениях: вправо или вверх. Путь — это цепочка таких единичных шагов. Вот решётка и один путь по ней:
2 ·───·───·───●
│ │ │ ┃
1 ·───●━━━●━━━●
│ ┃ │ │
0 ●━━━●───·───·
0 1 2 3
Путь выделен жирными линиями: вправо, вверх, вправо, вправо, вверх.
Маленький пример: все пути в решётке
Выпишем все пути из в . Под каждым рисунком — его запись: единица — шаг вверх, ноль — шаг вправо.
·──·──● ·──·──● ·──●━━●
│ │ ┃ │ │ ┃ │ ┃ │
·──·──● ·──●━━● ·──●──·
│ │ ┃ │ ┃ │ │ ┃ │
●━━●━━● ●━━●──· ●━━●──·
0011 0101 0110
·──·──● ·──●━━● ●━━●━━●
│ │ ┃ │ ┃ │ ┃ │ │
●━━●━━● ●━━●──· ●──·──·
┃ │ │ ┃ │ │ ┃ │ │
●──·──· ●──·──· ●──·──·
1001 1010 1100
Путей шесть. У каждого кода ровно два нуля и две единицы: два шага вправо и два шага вверх. Это не случайно.
Код пути
Единичный шаг вверх кодируем символом «», шаг вправо — символом «». Каждому пути из в сопоставим код
Чтобы дойти до , нужно раз сместиться вправо и раз вверх: в коде ровно нулей и единиц, всего символов.
Пример на решётке . Код читается слева направо: вправо, вверх, вправо, вправо, вверх, вверх, вправо, вверх, вправо, вправо, вверх, вправо, вверх. Нулей , единиц — как раз нужное число.
6 ·───·───·───·───·───·───·───●
│ │ │ │ │ │ │ ┃
5 ·───·───·───·───·───·───●━━━●
│ │ │ │ │ │ ┃ │
4 ·───·───·───·───●━━━●━━━●───·
│ │ │ │ ┃ │ │ │
3 ·───·───·───●━━━●───·───·───·
│ │ │ ┃ │ │ │ │
2 ·───·───·───●───·───·───·───·
│ │ │ ┃ │ │ │ │
1 ·───●━━━●━━━●───·───·───·───·
│ ┃ │ │ │ │ │ │
0 ●━━━●───·───·───·───·───·───·
0 1 2 3 4 5 6 7
Теорема (задача 1)
Теорема. Число путей из в по решётке равно
Доказательство. Проверим, что пути и коды стоят в соответствии «один к одному».
- Каждому пути отвечает код с нулями и единицами — это построено выше.
- Каждый такой код задаёт некоторый путь: читаем символы по очереди и делаем соответствующий шаг. Нулей , единиц , поэтому путь заканчивается в точке .
- Разным кодам отвечают разные пути: коды различаются на каком-то месте, и на этом шаге один путь идёт вправо, а другой вверх.
Значит, путей столько же, сколько слов длины с нулями и единицами. Чтобы задать такое слово, выберем мест для нулей среди позиций (остальные займут единицы) — способов. Можно выбрать мест для единиц: . Числа равны по симметрии.
Для решётки : — совпало с рисунками. Для решётки : .
Шаги в каждой точке: Паскаль внутри решётки
Подпишем у каждой вершины число путей из в эту вершину:
4 1─ 5─ 15─ 35─ 70─126
3 1─ 4─ 10─ 20─ 35─ 56
2 1─ 3─ 6─ 10─ 15─ 21
1 1─ 2─ 3─ 4─ 5─ 6
0 1─ 1─ 1─ 1─ 1─ 1
0 1 2 3 4 5
В любую вершину можно попасть либо слева (последний шаг вправо), либо снизу (последний шаг вверх), и других вариантов нет. По правилу суммы число путей в вершину — сумма чисел для двух соседей. Например, или . В вершину ведёт путей, и записанное равенство
— в точности правило Паскаля. Числа на одной «косой» линии (она идёт от нижнего края вверх и влево) — это строки треугольника Паскаля: , , , , … Например, на линии стоят числа .
Примеры
1. Кварталы города. Нужно пройти пять кварталов на восток и три на север, не возвращаясь назад: маршрутов.
2. Через заданную точку. Сколько путей из в проходят через точку ? Разобьём путь на два участка и затем перемножим. Путь : . Путь : нужно шага вправо и вверх, . Всего .
Частые ошибки
- Считать шаги: вместо . Длина любого пути равна , число путей — .
- Брать или . Верхнее число — все шаги , нижнее — число шагов одного вида.
- Разрешать шаги влево и вниз. В этой задаче такие шаги запрещены.
- Путать размер решётки и число клеток. Решётка имеет клеток по горизонтали и по вертикали, а узлов .
Проверь себя
1. Сколько существует путей из в ?
Решение
, : .
2. Сколько существует путей из точки в точку ?
Решение
Нужно шага вправо и шага вверх: нулей , единиц . Как для решётки : .
3. Какой путь отвечает коду ? В какой точке он заканчивается?
Решение
Нулей , единиц , значит, конец в точке . Шаги: вверх, вверх, вправо, вверх, вправо, вправо, вверх.
4 ·───·───·───●
│ │ │ ┃
3 ·───●━━━●━━━●
│ ┃ │ │
2 ●━━━●───·───·
┃ │ │ │
1 ●───·───·───·
┃ │ │ │
0 ●───·───·───·
0 1 2 3
4. Сколько существует путей из в , проходящих через точку ?
Решение
До точки : путей. От неё до : нужно шага вправо и вверх, . Всего .
Итог
- Путь вправо/вверх из в записывается кодом из нулей (вправо) и единиц (вверх).
- Число путей — число способов выбрать места для нулей: .
- Число путей в узел равно сумме чисел для левого и нижнего соседей; это правило Паскаля.
- Путь через точку: перемножаем числа путей «до» и «после».
