bulgakov

19. Пути по решётке из O(0,0) в A(m,n)

Путь по клетчатой решётке, в котором разрешены только шаги вправо и вверх, записывается словом из нулей (вправо) и единиц (вверх). Чтобы попасть из O(0,0)O(0,0) в A(m,n)A(m,n), нужно сделать mm шагов вправо и nn вверх. Поэтому путей столько же, сколько слов с mm нулями и nn единицами: (m+nm)\dbinom{m+n}{m}.

Что пригодится из прошлого: сочетания — выбор мест для нулей; перестановки с повторяющимися элементами — слова из нулей и единиц; правило Паскаля — оно окажется внутри картинки решётки. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Что такое решётка и путь

Рассмотрим на плоскости точки с целыми координатами: это пары целых чисел, то есть декартово произведение Z×Z\mathbb Z\times\mathbb Z.

Целочисленная решётка размера m×nm\times n — это прямоугольник на координатной плоскости с вершинами O(0,0)O(0,0) и A(m,n)A(m,n). Вершинами (узлами) решётки называют точки этого прямоугольника с целыми координатами. Ребро — отрезок между двумя соседними вершинами на одной горизонтали или одной вертикали.

Двигаться по решётке разрешено только в двух направлениях: вправо или вверх. Путь — это цепочка таких единичных шагов. Вот решётка 3×23\times2 и один путь по ней:

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

Путь выделен жирными линиями: вправо, вверх, вправо, вправо, вверх.

Маленький пример: все пути в решётке 2×22\times2

Выпишем все пути из O(0,0)O(0,0) в A(2,2)A(2,2). Под каждым рисунком — его запись: единица — шаг вверх, ноль — шаг вправо.

·──·──●    ·──·──●    ·──●━━●
│  │  ┃    │  │  ┃    │  ┃  │
·──·──●    ·──●━━●    ·──●──·
│  │  ┃    │  ┃  │    │  ┃  │
●━━●━━●    ●━━●──·    ●━━●──·
  0011       0101       0110

·──·──●    ·──●━━●    ●━━●━━●
│  │  ┃    │  ┃  │    ┃  │  │
●━━●━━●    ●━━●──·    ●──·──·
┃  │  │    ┃  │  │    ┃  │  │
●──·──·    ●──·──·    ●──·──·
  1001       1010       1100

Путей шесть. У каждого кода ровно два нуля и две единицы: два шага вправо и два шага вверх. Это не случайно.

Код пути

Единичный шаг вверх кодируем символом «11», шаг вправо — символом «00». Каждому пути из O(0,0)O(0,0) в A(m,n)A(m,n) сопоставим код

α1α2…αm+n,αi∈{0,1}.\alpha_1\alpha_2\ldots\alpha_{m+n},\qquad \alpha_i\in\{0,1\}.

Чтобы дойти до A(m,n)A(m,n), нужно mm раз сместиться вправо и nn раз вверх: в коде ровно mm нулей и nn единиц, всего m+nm+n символов.

Пример на решётке 7×67\times6. Код 01001101001010100110100101 читается слева направо: вправо, вверх, вправо, вправо, вверх, вверх, вправо, вверх, вправо, вправо, вверх, вправо, вверх. Нулей 77, единиц 66 — как раз нужное число.

 6 ·───·───·───·───·───·───·───●
   │   │   │   │   │   │   │   ┃
 5 ·───·───·───·───·───·───●━━━●
   │   │   │   │   │   │   ┃   │
 4 ·───·───·───·───●━━━●━━━●───·
   │   │   │   │   ┃   │   │   │
 3 ·───·───·───●━━━●───·───·───·
   │   │   │   ┃   │   │   │   │
 2 ·───·───·───●───·───·───·───·
   │   │   │   ┃   │   │   │   │
 1 ·───●━━━●━━━●───·───·───·───·
   │   ┃   │   │   │   │   │   │
 0 ●━━━●───·───·───·───·───·───·
   0   1   2   3   4   5   6   7

Теорема (задача 1)

Теорема. Число путей из O(0,0)O(0,0) в A(m,n)A(m,n) по решётке равно

(m+nm)=(m+nn).\boxed{\binom{m+n}{m}=\binom{m+n}{n}}.

Доказательство. Проверим, что пути и коды стоят в соответствии «один к одному».

  • Каждому пути отвечает код с mm нулями и nn единицами — это построено выше.
  • Каждый такой код задаёт некоторый путь: читаем символы по очереди и делаем соответствующий шаг. Нулей mm, единиц nn, поэтому путь заканчивается в точке (m,n)(m,n).
  • Разным кодам отвечают разные пути: коды различаются на каком-то месте, и на этом шаге один путь идёт вправо, а другой вверх.

Значит, путей столько же, сколько слов длины m+nm+n с mm нулями и nn единицами. Чтобы задать такое слово, выберем mm мест для нулей среди m+nm+n позиций (остальные займут единицы) — (m+nm)\dbinom{m+n}{m} способов. Можно выбрать nn мест для единиц: (m+nn)\dbinom{m+n}{n}. Числа равны по симметрии. □\square

Для решётки 2×22\times2: (42)=6\dbinom42=6 — совпало с рисунками. Для решётки 7×67\times6: (136)=1716\dbinom{13}{6}=1716.

Шаги в каждой точке: Паскаль внутри решётки

Подпишем у каждой вершины число путей из OO в эту вершину:

 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

В любую вершину (x,y)(x,y) можно попасть либо слева (последний шаг вправо), либо снизу (последний шаг вверх), и других вариантов нет. По правилу суммы число путей в вершину — сумма чисел для двух соседей. Например, 10=4+610=4+6 или 35=15+2035=15+20. В вершину (x,y)(x,y) ведёт (x+yx)\dbinom{x+y}{x} путей, и записанное равенство

(x+yx)=(x+y−1x−1)+(x+y−1x)\binom{x+y}{x}=\binom{x+y-1}{x-1}+\binom{x+y-1}{x}

— в точности правило Паскаля. Числа на одной «косой» линии x+y=constx+y=\text{const} (она идёт от нижнего края вверх и влево) — это строки треугольника Паскаля: 11, 1  11\;1, 1  2  11\;2\;1, 1  3  3  11\;3\;3\;1, … Например, на линии x+y=3x+y=3 стоят числа 1,3,3,11,3,3,1.

Примеры

1. Кварталы города. Нужно пройти пять кварталов на восток и три на север, не возвращаясь назад: (83)=56\dbinom{8}{3}=56 маршрутов.

2. Через заданную точку. Сколько путей из O(0,0)O(0,0) в A(4,3)A(4,3) проходят через точку (2,1)(2,1)? Разобьём путь на два участка и затем перемножим. Путь O→(2,1)O\to(2,1): (31)=3\dbinom{3}{1}=3. Путь (2,1)→A(2,1)\to A: нужно 22 шага вправо и 22 вверх, (42)=6\dbinom42=6. Всего 3⋅6=183\cdot6=18.

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

  • Считать шаги: m⋅nm\cdot n вместо m+nm+n. Длина любого пути равна m+nm+n, число путей — (m+nm)\dbinom{m+n}{m}.
  • Брать (m+nm+n)\dbinom{m+n}{m+n} или (mn)\dbinom mn. Верхнее число — все шаги m+nm+n, нижнее — число шагов одного вида.
  • Разрешать шаги влево и вниз. В этой задаче такие шаги запрещены.
  • Путать размер решётки и число клеток. Решётка m×nm\times n имеет mm клеток по горизонтали и nn по вертикали, а узлов (m+1)(n+1)(m+1)(n+1).

Проверь себя

1. Сколько существует путей из O(0,0)O(0,0) в A(4,3)A(4,3)?

Решение

m=4m=4, n=3n=3: (73)=35\dbinom73=35.

2. Сколько существует путей из точки (1,1)(1,1) в точку (5,4)(5,4)?

Решение

Нужно 5−1=45-1=4 шага вправо и 4−1=34-1=3 шага вверх: нулей 44, единиц 33. Как для решётки 4×34\times3: (73)=35\dbinom73=35.

3. Какой путь отвечает коду 11010011101001? В какой точке он заканчивается?

Решение

Нулей 33, единиц 44, значит, конец в точке A(3,4)A(3,4). Шаги: вверх, вверх, вправо, вверх, вправо, вправо, вверх.

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

4. Сколько существует путей из O(0,0)O(0,0) в A(5,4)A(5,4), проходящих через точку (3,2)(3,2)?

Решение

До точки (3,2)(3,2): (52)=10\dbinom52=10 путей. От неё до A(5,4)A(5,4): нужно 22 шага вправо и 22 вверх, (42)=6\dbinom42=6. Всего 10⋅6=6010\cdot6=60.

Итог

  • Путь вправо/вверх из O(0,0)O(0,0) в A(m,n)A(m,n) записывается кодом из mm нулей (вправо) и nn единиц (вверх).
  • Число путей — число способов выбрать места для нулей: (m+nm)=(m+nn)\dbinom{m+n}{m}=\dbinom{m+n}{n}.
  • Число путей в узел (x,y)(x,y) равно сумме чисел для левого и нижнего соседей; это правило Паскаля.
  • Путь через точку: перемножаем числа путей «до» и «после».
ПрактикаЗагружаем тест…