bulgakov

20. Пути длины n и ломаные из h звеньев

Если у пути заранее не задан конец, то каждый путь из nn шагов — это просто слово длины nn из нулей и единиц, и всего таких путей 2n2^n. Если же потребовать, чтобы путь был ломаной из ровно hh звеньев, то слово разбивается на hh блоков одинаковых букв, и таких путей 2(n−1h−1)2\dbinom{n-1}{h-1}.

Что пригодится из прошлого: пути по решётке — запись пути словом из нулей и единиц; двоичные коды — число слов длины nn равно 2n2^n; сочетания и их свойства. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача 2: все пути длины nn

Задача. В решётке размера n×nn\times n найти число путей длины nn с началом в точке O(0,0)O(0,0). (Это вторая задача серии про решётку; первая — число путей с заданным концом — разобрана в прошлой главе.) Путь из nn шагов не может выйти за квадрат n×nn\times n: ни по горизонтали, ни по вертикали он не уйдёт дальше чем на nn.

Теперь конец пути не задан: нужно просто сделать nn шагов, каждый вправо или вверх. Выпишем все пути длины 33:

·─·─·─·    ·─·─·─·    ·─·─·─·
│ │ │ │    │ │ │ │    │ │ │ │
·─·─·─·    ·─·─·─·    ·─·─·─·
│ │ │ │    │ │ │ │    │ │ │ │
·─·─·─·    ·─·─●─·    ·─●━●─·
│ │ │ │    │ │ ┃ │    │ ┃ │ │
●━●━●━●    ●━●━●─·    ●━●─·─·
  000        001        010

·─·─·─·    ·─·─·─·    ·─·─·─·
│ │ │ │    │ │ │ │    │ │ │ │
·─●─·─·    ·─·─·─·    ·─●─·─·
│ ┃ │ │    │ │ │ │    │ ┃ │ │
·─●─·─·    ●━●━●─·    ●━●─·─·
│ ┃ │ │    ┃ │ │ │    ┃ │ │ │
●━●─·─·    ●─·─·─·    ●─·─·─·
  011        100        101

·─·─·─·    ●─·─·─·
│ │ │ │    ┃ │ │ │
●━●─·─·    ●─·─·─·
┃ │ │ │    ┃ │ │ │
●─·─·─·    ●─·─·─·
┃ │ │ │    ┃ │ │ │
●─·─·─·    ●─·─·─·
  110        111

Здесь снова «00 — вправо, 11 — вверх». Любой путь из nn шагов — это слово длины nn из нулей и единиц, и любое такое слово задаёт путь (читаем шаг за шагом). Разным словам отвечают разные пути. Нулей и единиц может быть сколько угодно: ограничений на число шагов каждого вида нет. Значит, путей столько же, сколько слов длины nn в алфавите {0,1}\{0,1\}:

2n.\boxed{2^n}.

Для n=3n=3: 23=82^3=8 — как на рисунке. Это ровно подсчёт двоичных кодов из первой главы: на каждом шаге два варианта.

Звенья ломаной

Путь на рисунке — ломаная линия. Звено — это самый длинный отрезок пути, на котором все шаги идут в одну сторону. В слове звену отвечает блок подряд идущих одинаковых букв.

Пример. Слово 00110100011010 разбивается на блоки 00 ∣ 11 ∣ 0 ∣ 1 ∣ 000\,|\,11\,|\,0\,|\,1\,|\,0: пять блоков — пять звеньев. Значит, путь — ломаная из h=5h=5 звеньев и h−1=4h-1=4 поворотов.

 3 ·───·───·───●━━━●
   │   │   │   ┃   │
 2 ·───·───●━━━●───·
   │   │   ┃   │   │
 1 ·───·───●───·───·
   │   │   ┃   │   │
 0 ●━━━●━━━●───·───·
   0   1   2   3   4

Отметим, где в слове меняется буква:

Схема
буквы:      0  0  1  1  0  1  0
промежутки:   1  2  3  4  5  6
смена буквы:     ↑     ↑  ↑  ↑

Между 77 буквами 66 промежутков. Буква меняется в промежутках 2,4,5,62,4,5,6 — четыре смены, то есть h−1=4h-1=4 поворота.

Задача 3: ломаные из hh звеньев

Задача. В решётке размера n×nn\times n найти число путей длины nn с началом O(0,0)O(0,0), которые образуют ломаную из hh звеньев.

Путь отвечает слову, которое состоит из hh блоков:

αα…α⏟1 , α‾α‾…α‾⏟2 , αα…α⏟3 , α‾α‾…α‾⏟4 , … , …⏟h,\underbrace{\alpha\alpha\ldots\alpha}_{1}\ ,\ \underbrace{\overline\alpha\overline\alpha\ldots\overline\alpha}_{2}\ ,\ \underbrace{\alpha\alpha\ldots\alpha}_{3}\ ,\ \underbrace{\overline\alpha\overline\alpha\ldots\overline\alpha}_{4}\ ,\ \ldots\ ,\ \underbrace{\ldots}_{h},

где α∈{0,1}\alpha\in\{0,1\}, а α‾=1−α\overline\alpha=1-\alpha: блоки чередуются, и каждый непуст.

Теорема. Число таких путей равно

2(n−1h−1).\boxed{2\binom{n-1}{h-1}}.

Доказательство. Слово полностью определяется двумя вещами:

  1. В каких промежутках меняется буква. Между nn буквами n−1n-1 промежуток; нужно выбрать h−1h-1 из них (места перехода от α\alpha к α‾\overline\alpha либо обратно) — (n−1h−1)\dbinom{n-1}{h-1} способов.
  2. С какой буквы слово начинается: α=0\alpha=0 или α=1\alpha=1 — 22 способа.

Выбор в обоих пунктах независим, и по ним слово восстанавливается однозначно: первая буква известна, после каждого отмеченного промежутка буква меняется. Значит, по правилу произведения слов 2(n−1h−1)2\dbinom{n-1}{h-1}. □\square

Проверим на n=4n=4. Выпишем все 1616 слов, сгруппировав по числу звеньев:

  • h=1h=1: 0000, 1111 — всего 2; по формуле 2(3h−1)=22\binom{3}{h-1}=2
  • h=2h=2: 0001, 0011, 0111, 1000, 1100, 1110 — всего 6; по формуле 2(3h−1)=62\binom{3}{h-1}=6
  • h=3h=3: 0010, 0100, 0110, 1001, 1011, 1101 — всего 6; по формуле 2(3h−1)=62\binom{3}{h-1}=6
  • h=4h=4: 0101, 1010 — всего 2; по формуле 2(3h−1)=22\binom{3}{h-1}=2

Всего слов: 16.

Число слов для каждого hh совпало с формулой. Сумма по всем hh равна 16=2416=2^4: слова из задачи 2 разбились на группы по числу звеньев. Это не случайность:

∑h=1n2(n−1h−1)=2∑j=0n−1(n−1j)=2⋅2n−1=2n.\sum_{h=1}^{n}2\binom{n-1}{h-1}=2\sum_{j=0}^{n-1}\binom{n-1}{j}=2\cdot2^{n-1}=2^n.

Мы использовали равенство ∑j=0n−1(n−1j)=2n−1\sum_{j=0}^{n-1}\dbinom{n-1}{j}=2^{n-1} из главы про свойства сочетаний.

Примеры

1. Путь длины 66 — ломаная из 33 звеньев: 2(52)=2⋅10=202\dbinom52=2\cdot10=20.

2. Путь длины 1010 — ломаная из 44 звеньев: 2(93)=2⋅84=1682\dbinom93=2\cdot84=168.

3. Звено одно (h=1h=1): 2(n−10)=22\dbinom{n-1}{0}=2 — путь идёт только вправо или только вверх.

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

  • Забыть множитель 22. Путь может начинаться и вправо, и вверх.
  • Взять (nh−1)\dbinom{n}{h-1}. Промежутков между буквами на единицу меньше, чем букв: n−1n-1.
  • Спутать звенья и повороты. hh звеньев — это h−1h-1 поворотов.
  • Считать, что путь заканчивается в A(n,n)A(n,n). В этих задачах конец свободен: путь длины nn заканчивается в любой точке (k,n−k)(k,n-k).

Проверь себя

1. Сколько существует путей длины 88 из O(0,0)O(0,0)?

Решение

28=2562^8=256.

2. Сколько существует путей длины 66, образующих ломаную из 33 звеньев?

Решение

2(6−13−1)=2(52)=202\dbinom{6-1}{3-1}=2\dbinom52=20.

3. Сколько существует путей длины 88 ровно с пятью поворотами?

Решение

Пять поворотов — это h=6h=6 звеньев. 2(75)=2⋅21=422\dbinom{7}{5}=2\cdot21=42.

4. Сколько существует путей длины 55, которые состоят не более чем из двух звеньев?

Решение

Складываем непересекающиеся случаи. Одно звено: 2(40)=22\dbinom40=2. Два звена: 2(41)=82\dbinom41=8. Всего 2+8=102+8=10.

Итог

  • Путь из nn шагов с неопределённым концом — слово длины nn из {0,1}\{0,1\}; путей 2n2^n.
  • Звено — блок одинаковых букв; hh звеньев — h−1h-1 смена буквы.
  • Число путей-ломаных из hh звеньев: 2(n−1h−1)2\dbinom{n-1}{h-1} (выбор h−1h-1 промежутков из n−1n-1 и первой буквы).
  • Сумма по hh даёт 2n2^n: это ещё раз ∑(n−1j)=2n−1\sum\dbinom{n-1}{j}=2^{n-1}.
ПрактикаЗагружаем тест…