20. Пути длины n и ломаные из h звеньев
Если у пути заранее не задан конец, то каждый путь из шагов — это просто слово длины из нулей и единиц, и всего таких путей . Если же потребовать, чтобы путь был ломаной из ровно звеньев, то слово разбивается на блоков одинаковых букв, и таких путей .
Что пригодится из прошлого: пути по решётке — запись пути словом из нулей и единиц; двоичные коды — число слов длины равно ; сочетания и их свойства. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача 2: все пути длины
Задача. В решётке размера найти число путей длины с началом в точке . (Это вторая задача серии про решётку; первая — число путей с заданным концом — разобрана в прошлой главе.) Путь из шагов не может выйти за квадрат : ни по горизонтали, ни по вертикали он не уйдёт дальше чем на .
Теперь конец пути не задан: нужно просто сделать шагов, каждый вправо или вверх. Выпишем все пути длины :
·─·─·─· ·─·─·─· ·─·─·─·
│ │ │ │ │ │ │ │ │ │ │ │
·─·─·─· ·─·─·─· ·─·─·─·
│ │ │ │ │ │ │ │ │ │ │ │
·─·─·─· ·─·─●─· ·─●━●─·
│ │ │ │ │ │ ┃ │ │ ┃ │ │
●━●━●━● ●━●━●─· ●━●─·─·
000 001 010
·─·─·─· ·─·─·─· ·─·─·─·
│ │ │ │ │ │ │ │ │ │ │ │
·─●─·─· ·─·─·─· ·─●─·─·
│ ┃ │ │ │ │ │ │ │ ┃ │ │
·─●─·─· ●━●━●─· ●━●─·─·
│ ┃ │ │ ┃ │ │ │ ┃ │ │ │
●━●─·─· ●─·─·─· ●─·─·─·
011 100 101
·─·─·─· ●─·─·─·
│ │ │ │ ┃ │ │ │
●━●─·─· ●─·─·─·
┃ │ │ │ ┃ │ │ │
●─·─·─· ●─·─·─·
┃ │ │ │ ┃ │ │ │
●─·─·─· ●─·─·─·
110 111
Здесь снова « — вправо, — вверх». Любой путь из шагов — это слово длины из нулей и единиц, и любое такое слово задаёт путь (читаем шаг за шагом). Разным словам отвечают разные пути. Нулей и единиц может быть сколько угодно: ограничений на число шагов каждого вида нет. Значит, путей столько же, сколько слов длины в алфавите :
Для : — как на рисунке. Это ровно подсчёт двоичных кодов из первой главы: на каждом шаге два варианта.
Звенья ломаной
Путь на рисунке — ломаная линия. Звено — это самый длинный отрезок пути, на котором все шаги идут в одну сторону. В слове звену отвечает блок подряд идущих одинаковых букв.
Пример. Слово разбивается на блоки : пять блоков — пять звеньев. Значит, путь — ломаная из звеньев и поворотов.
3 ·───·───·───●━━━●
│ │ │ ┃ │
2 ·───·───●━━━●───·
│ │ ┃ │ │
1 ·───·───●───·───·
│ │ ┃ │ │
0 ●━━━●━━━●───·───·
0 1 2 3 4
Отметим, где в слове меняется буква:
буквы: 0 0 1 1 0 1 0
промежутки: 1 2 3 4 5 6
смена буквы: ↑ ↑ ↑ ↑
Между буквами промежутков. Буква меняется в промежутках — четыре смены, то есть поворота.
Задача 3: ломаные из звеньев
Задача. В решётке размера найти число путей длины с началом , которые образуют ломаную из звеньев.
Путь отвечает слову, которое состоит из блоков:
где , а : блоки чередуются, и каждый непуст.
Теорема. Число таких путей равно
Доказательство. Слово полностью определяется двумя вещами:
- В каких промежутках меняется буква. Между буквами промежуток; нужно выбрать из них (места перехода от к либо обратно) — способов.
- С какой буквы слово начинается: или — способа.
Выбор в обоих пунктах независим, и по ним слово восстанавливается однозначно: первая буква известна, после каждого отмеченного промежутка буква меняется. Значит, по правилу произведения слов .
Проверим на . Выпишем все слов, сгруппировав по числу звеньев:
- : 0000, 1111 — всего 2; по формуле
- : 0001, 0011, 0111, 1000, 1100, 1110 — всего 6; по формуле
- : 0010, 0100, 0110, 1001, 1011, 1101 — всего 6; по формуле
- : 0101, 1010 — всего 2; по формуле
Всего слов: 16.
Число слов для каждого совпало с формулой. Сумма по всем равна : слова из задачи 2 разбились на группы по числу звеньев. Это не случайность:
Мы использовали равенство из главы про свойства сочетаний.
Примеры
1. Путь длины — ломаная из звеньев: .
2. Путь длины — ломаная из звеньев: .
3. Звено одно (): — путь идёт только вправо или только вверх.
Частые ошибки
- Забыть множитель . Путь может начинаться и вправо, и вверх.
- Взять . Промежутков между буквами на единицу меньше, чем букв: .
- Спутать звенья и повороты. звеньев — это поворотов.
- Считать, что путь заканчивается в . В этих задачах конец свободен: путь длины заканчивается в любой точке .
Проверь себя
1. Сколько существует путей длины из ?
Решение
.
2. Сколько существует путей длины , образующих ломаную из звеньев?
Решение
.
3. Сколько существует путей длины ровно с пятью поворотами?
Решение
Пять поворотов — это звеньев. .
4. Сколько существует путей длины , которые состоят не более чем из двух звеньев?
Решение
Складываем непересекающиеся случаи. Одно звено: . Два звена: . Всего .
Итог
- Путь из шагов с неопределённым концом — слово длины из ; путей .
- Звено — блок одинаковых букв; звеньев — смена буквы.
- Число путей-ломаных из звеньев: (выбор промежутков из и первой буквы).
- Сумма по даёт : это ещё раз .
