bulgakov

22. Метод отражения и числа Каталана

Каждый «плохой» путь — тот, что поднимается выше диагонали, — взаимно однозначно превращается в путь в другую точку A′(n−1,n+1)A'(n-1,n+1): после первой точки на прямой y=x+1y=x+1 (она на единицу выше диагонали) отражаем оставшуюся часть пути. Поэтому плохих путей (2nn−1)\dbinom{2n}{n-1}, хороших (2nn)−(2nn−1)=1n+1(2nn)\dbinom{2n}{n}-\dbinom{2n}{n-1}=\dfrac1{n+1}\dbinom{2n}{n} (числа Каталана), а правильных очередей (2n)!n+1\dfrac{(2n)!}{n+1}.

Что пригодится из прошлого: очередь и пути — где возникли yny_n, znz_n и диагональ; пути по решётке — число путей (m+nm)\dbinom{m+n}{m}; сочетания и их свойства. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Что осталось найти

Из прошлой главы известно:

yn+zn=(2nn),y_n+z_n=\binom{2n}{n},

где yny_n — число путей из O(0,0)O(0,0) в A(n,n)A(n,n), которые не поднимаются выше диагонали OAOA, а znz_n — число путей, которые поднимаются. Найдём znz_n.

Прямая aa

Проведём прямую aa: y=x+1y=x+1. Она проходит через точки (0,1)(0,1) и (n−1,n)(n-1,n) и параллельна диагонали OAOA, лежа на единицу выше.

Плохой путь обязательно касается прямой aa — то есть проходит хотя бы через один узел решётки, лежащий на этой прямой. Следим за разностью y−xy-x. В начале она равна 00. Каждый шаг вправо уменьшает её на 11, каждый шаг вверх увеличивает на 11. Если путь где-то поднимается выше диагонали, то y−x≥1y-x\ge1. Изменение происходит ровно на единицу за шаг, поэтому первый момент, когда y−x≥1y-x\ge1, — это момент, когда y−x=1y-x=1, то есть точка лежит на прямой aa.

Отражение

Возьмём плохой путь. Отметим на нём первую точку прямой aa и назовём её O′O' (вдоль пути координаты не убывают, поэтому первая по ходу точка — одновременно точка с наименьшими координатами). Участок пути от O′O' до AA симметрично отразим относительно прямой aa. Начало пути (от OO до O′O') не трогаем. Точка A(n,n)A(n,n) переходит в симметричную ей точку A′(n−1,n+1)A'(n-1,n+1). Формула отражения относительно прямой y=x+1y=x+1: (x,y)↦(y−1, x+1)(x,y)\mapsto(y-1,\,x+1). (Почему: сдвинем начало координат в точку (0,1)(0,1) прямой — координаты станут (x, y−1)(x,\,y-1); отражение относительно прямой под углом 45∘45^\circ меняет координаты местами: (y−1, x)(y-1,\,x); вернём сдвиг: (y−1, x+1)(y-1,\,x+1). Проверка: точка (0,1)(0,1) прямой остаётся на месте, а (n,n)(n,n) переходит в (n−1, n+1)(n-1,\,n+1).)

Пример для n=4n=4. Слева — плохой путь с кодом 0011100100111001; значком ○ отмечены точки прямой aa, значком ◆ — первая точка пути на ней, O′=(2,3)O'=(2,3). Справа — образ этого пути после отражения хвоста; точка BB — это A′A'.

 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)

Хвост 001001 (вправо, вправо, вверх) после отражения стал 110110 (вверх, вверх, вправо): отражение относительно прямой под углом 45∘45^\circ меняет местами «вправо» и «вверх». Новый код — 00111 11000111\,110; в нём 33 нуля и 55 единиц, значит, путь приходит в точку (3,5)=A′(n−1,n+1)(3,5)=A'(n-1,n+1).

Алгоритм отражения.

  1. Идём по коду слева направо и следим за числом «единиц минус нулей».
  2. В первый момент, когда оно стало равно 11, запоминаем точку O′O'.
  3. Начало кода до O′O' оставляем без изменений.
  4. В оставшейся части меняем каждый 00 на 11 и каждую 11 на 00.

Почему соответствие взаимно однозначно

Мы получили правило: плохой путь O→AO\to A превращается в путь O→A′O\to A'. Покажем, что оно обратимо, то есть пути обоих видов стоят в парах «один к одному».

  • Из плохого пути получаем путь в A′A'. Это построено выше.
  • Из любого пути в A′A' получаем плохой путь в AA. Прямая aa задаётся равенством y−x=1y-x=1: по одну её сторону y−x<1y-x<1, по другую y−x>1y-x>1. Точка A′(n−1,n+1)A'(n-1,n+1) лежит по другую сторону от прямой aa, чем точка OO: для A′A' разность y−x=2>1y-x=2>1, для OO она равна 0<10<1. Поэтому любой путь O→A′O\to A' где-то касается aa. Берём первую точку касания O′O' и отражаем хвост — получаем путь, который приходит в AA и по построению проходит через точку O′O' прямой aa, где y−x=1>0y-x=1>0, то есть поднимается выше диагонали.
  • Операции отменяют друг друга. До точки O′O' путь не менялся и aa не касался, поэтому первая точка касания у пути и у его образа одна и та же — O′O'. Отражая хвост второй раз, мы возвращаем исходный путь.

Малые случаи легко проверить перебором. При n=3n=3 плохих путей 1515, и путей в точку A′(2,4)A'(2,4) тоже (62)=15\dbinom62=15.

Подсчёт

Всякий путь в A′(n−1,n+1)A'(n-1,n+1) состоит из n−1n-1 шагов вправо и n+1n+1 шагов вверх. Их число ((n−1)+(n+1)n−1)\dbinom{(n-1)+(n+1)}{n-1}, поэтому

zn=(2nn−1).\boxed{z_n=\binom{2n}{n-1}}.

Тогда число хороших путей

yn=(2nn)−(2nn−1)=1n+1(2nn).y_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac1{n+1}\binom{2n}{n}.

Как получилась дробь. Выразим второе число через первое:

(2nn−1)=(2n)!(n−1)! (n+1)!=(2n)!n! n!⋅n! n!(n−1)! (n+1)!=(2nn)⋅nn+1.\binom{2n}{n-1}=\frac{(2n)!}{(n-1)!\,(n+1)!}=\frac{(2n)!}{n!\,n!}\cdot\frac{n!\,n!}{(n-1)!\,(n+1)!}=\binom{2n}{n}\cdot\frac{n}{n+1}.

Поэтому

(2nn)−(2nn)⋅nn+1=(2nn)⋅1n+1.\binom{2n}{n}-\binom{2n}{n}\cdot\frac n{n+1}=\binom{2n}{n}\cdot\frac1{n+1}.

Числа Каталана. Числа yn=1n+1(2nn)y_n=\dfrac{1}{n+1}\dbinom{2n}{n} называются числами Каталана:

nn 0 1 2 3 4 5 6 7 8 9 10
yny_n 1 1 2 5 14 42 132 429 1430 4862 16796

Ответ задачи

Правильных очередей

xn=n!⋅n!⋅yn=n!⋅n!⋅1n+1⋅(2n)!n! n!=(2n)!n+1.x_n=n!\cdot n!\cdot y_n=n!\cdot n!\cdot\frac1{n+1}\cdot\frac{(2n)!}{n!\,n!}=\boxed{\frac{(2n)!}{n+1}}.

Проверка: n=2n=2 — 4!3=8\dfrac{4!}{3}=8 очередей (по четыре для слов 00110011 и 01010101, см. прошлую главу); n=3n=3 — 6!4=180\dfrac{6!}{4}=180; n=4n=4 — 8!5=8064\dfrac{8!}{5}=8064.

Частые ошибки

  • Отражать начало, а не хвост. Начало пути до O′O' остаётся на месте.
  • Брать последнюю точку касания. Отражение определено по первой точке касания: так обратная операция даёт ту же точку.
  • Перепутать n−1n-1 и n+1n+1. Точка A′A' имеет координаты (n−1,n+1)(n-1,n+1): после отражения число шагов вправо уменьшилось, вверх увеличилось.
  • Спутать прямую aa с диагональю. Плохой путь не просто касается диагонали, а поднимается выше неё; для этого он должен дойти до aa.
  • Забыть про n!⋅n!n!\cdot n!. yny_n считает слова, а правильных очередей больше.

Проверь себя

1. Найдите z4z_4 и y4y_4.

Решение

z4=(83)=56z_4=\dbinom{8}{3}=56, всех путей (84)=70\dbinom84=70, поэтому y4=70−56=14y_4=70-56=14.

2. Сколько существует путей из O(0,0)O(0,0) в A(3,3)A(3,3), которые никогда не поднимаются выше диагонали?

Решение

y3=14(63)=204=5y_3=\dfrac14\dbinom63=\dfrac{20}{4}=5 (их мы выписали в прошлой главе).

3. Какой путь получится, если у пути с кодом 0110110001101100 (n=4n=4) отразить хвост после первой точки прямой aa? В какой точке путь окажется?

Решение

После трёх шагов (011011) разность y−xy-x впервые стала равна 11: точка O′=(1,2)O'=(1,2). Хвост 0110001100 заменяем на 1001110011 (каждый 00 меняем на 11, каждую 11 на 00). Получается код 0111001101110011. В нём 33 нуля и 55 единиц, путь приходит в точку (3,5)=A′(n−1,n+1)(3,5)=A'(n-1,n+1) при n=4n=4.

4. Сколько существует правильных очередей из шести различных людей (трое с 500 и трое с 1000 драмов)?

Решение

x3=6!4=180x_3=\dfrac{6!}{4}=180.

Итог

  • Плохой путь касается прямой aa: y=x+1y=x+1. Первую точку касания O′O' оставляем, хвост отражаем.
  • Так плохие пути в A(n,n)A(n,n) взаимно однозначно превращаются в пути в A′(n−1,n+1)A'(n-1,n+1): zn=(2nn−1)z_n=\dbinom{2n}{n-1}.
  • Хороших путей yn=(2nn)−(2nn−1)=1n+1(2nn)y_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}=\dfrac1{n+1}\dbinom{2n}{n} — числа Каталана.
  • Правильных очередей xn=n!⋅n!⋅yn=(2n)!n+1x_n=n!\cdot n!\cdot y_n=\dfrac{(2n)!}{n+1}.
ПрактикаЗагружаем тест…