22. Метод отражения и числа Каталана
Каждый «плохой» путь — тот, что поднимается выше диагонали, — взаимно однозначно превращается в путь в другую точку : после первой точки на прямой (она на единицу выше диагонали) отражаем оставшуюся часть пути. Поэтому плохих путей , хороших (числа Каталана), а правильных очередей .
Что пригодится из прошлого: очередь и пути — где возникли , и диагональ; пути по решётке — число путей ; сочетания и их свойства. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Что осталось найти
Из прошлой главы известно:
где — число путей из в , которые не поднимаются выше диагонали , а — число путей, которые поднимаются. Найдём .
Прямая
Проведём прямую : . Она проходит через точки и и параллельна диагонали , лежа на единицу выше.
Плохой путь обязательно касается прямой — то есть проходит хотя бы через один узел решётки, лежащий на этой прямой. Следим за разностью . В начале она равна . Каждый шаг вправо уменьшает её на , каждый шаг вверх увеличивает на . Если путь где-то поднимается выше диагонали, то . Изменение происходит ровно на единицу за шаг, поэтому первый момент, когда , — это момент, когда , то есть точка лежит на прямой .
Отражение
Возьмём плохой путь. Отметим на нём первую точку прямой и назовём её (вдоль пути координаты не убывают, поэтому первая по ходу точка — одновременно точка с наименьшими координатами). Участок пути от до симметрично отразим относительно прямой . Начало пути (от до ) не трогаем. Точка переходит в симметричную ей точку . Формула отражения относительно прямой : . (Почему: сдвинем начало координат в точку прямой — координаты станут ; отражение относительно прямой под углом меняет координаты местами: ; вернём сдвиг: . Проверка: точка прямой остаётся на месте, а переходит в .)
Пример для . Слева — плохой путь с кодом ; значком ○ отмечены точки прямой , значком ◆ — первая точка пути на ней, . Справа — образ этого пути после отражения хвоста; точка — это .
5 ·───·───·───·───○
│ │ │ │ │
4 ·───·───·───○───A
│ │ │ │ ┃
3 ·───·───◆━━━●━━━●
│ │ ┃ │ │
2 ·───○───●───·───·
│ │ ┃ │ │
1 ○───·───●───·───·
│ │ ┃ │ │
0 ●━━━●━━━●───·───·
0 1 2 3 4
○ — точки прямой a
◆ — точка O′
A — конец пути
5 ·───·───●━━━B───○
│ │ ┃ │ │
4 ·───·───●───○───·
│ │ ┃ │ │
3 ·───·───◆───·───·
│ │ ┃ │ │
2 ·───○───●───·───·
│ │ ┃ │ │
1 ○───·───●───·───·
│ │ ┃ │ │
0 ●━━━●━━━●───·───·
0 1 2 3 4
○ — точки прямой a
◆ — точка O′
B — точка A′(n−1, n+1)
Хвост (вправо, вправо, вверх) после отражения стал (вверх, вверх, вправо): отражение относительно прямой под углом меняет местами «вправо» и «вверх». Новый код — ; в нём нуля и единиц, значит, путь приходит в точку .
Алгоритм отражения.
- Идём по коду слева направо и следим за числом «единиц минус нулей».
- В первый момент, когда оно стало равно , запоминаем точку .
- Начало кода до оставляем без изменений.
- В оставшейся части меняем каждый на и каждую на .
Почему соответствие взаимно однозначно
Мы получили правило: плохой путь превращается в путь . Покажем, что оно обратимо, то есть пути обоих видов стоят в парах «один к одному».
- Из плохого пути получаем путь в . Это построено выше.
- Из любого пути в получаем плохой путь в . Прямая задаётся равенством : по одну её сторону , по другую . Точка лежит по другую сторону от прямой , чем точка : для разность , для она равна . Поэтому любой путь где-то касается . Берём первую точку касания и отражаем хвост — получаем путь, который приходит в и по построению проходит через точку прямой , где , то есть поднимается выше диагонали.
- Операции отменяют друг друга. До точки путь не менялся и не касался, поэтому первая точка касания у пути и у его образа одна и та же — . Отражая хвост второй раз, мы возвращаем исходный путь.
Малые случаи легко проверить перебором. При плохих путей , и путей в точку тоже .
Подсчёт
Всякий путь в состоит из шагов вправо и шагов вверх. Их число , поэтому
Тогда число хороших путей
Как получилась дробь. Выразим второе число через первое:
Поэтому
Числа Каталана. Числа называются числами Каталана:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796 |
Ответ задачи
Правильных очередей
Проверка: — очередей (по четыре для слов и , см. прошлую главу); — ; — .
Частые ошибки
- Отражать начало, а не хвост. Начало пути до остаётся на месте.
- Брать последнюю точку касания. Отражение определено по первой точке касания: так обратная операция даёт ту же точку.
- Перепутать и . Точка имеет координаты : после отражения число шагов вправо уменьшилось, вверх увеличилось.
- Спутать прямую с диагональю. Плохой путь не просто касается диагонали, а поднимается выше неё; для этого он должен дойти до .
- Забыть про . считает слова, а правильных очередей больше.
Проверь себя
1. Найдите и .
Решение
, всех путей , поэтому .
2. Сколько существует путей из в , которые никогда не поднимаются выше диагонали?
Решение
(их мы выписали в прошлой главе).
3. Какой путь получится, если у пути с кодом () отразить хвост после первой точки прямой ? В какой точке путь окажется?
Решение
После трёх шагов () разность впервые стала равна : точка . Хвост заменяем на (каждый меняем на , каждую на ). Получается код . В нём нуля и единиц, путь приходит в точку при .
4. Сколько существует правильных очередей из шести различных людей (трое с 500 и трое с 1000 драмов)?
Решение
.
Итог
- Плохой путь касается прямой : . Первую точку касания оставляем, хвост отражаем.
- Так плохие пути в взаимно однозначно превращаются в пути в : .
- Хороших путей — числа Каталана.
- Правильных очередей .
