Великий треугольник

Пример 16

Ну, Заяц, погоди!

Всем известный Заяц, спасаясь от всем известного Волка, прибежал в город Морковкин-бург, план города, (напоминающий морковку) на рисунке. Сейчас заяц находится в точке А. Жирными линиями показаны дороги, передвигаться можно только по ним. Заяц интересуется, сколькими путями можно из точки А, где он находится, попасть на выбранный перекресток. Назад при движении в городе Зайцу возвращаться нельзя: Волк гонится по пятам!

(рис.9a)

Попробуем сориентироваться в городе.

Вы видите, что перекрестки располагаются «горизонтальными» рядами. Назовем «ряд», в котором находится единственный перекресток A, «нулевым» (n=0), дальше идет первый ряд (n=1), в нем два перекрестка, и т.д.

(рис.9б)

Перекрестки в каждом ряду будем нумеровать слева направо, также начиная с нуля. Тогда в n-м ряду будет n+1 перекресток – от нулевого до n-го. Номера перекрестков обозначены синим. Т.е. каждому перекрестку можно дать точный адрес: номер ряда n и номер места в ряду k (как в кинотеатре или на стадионе).

На любой из перекрестков, находящихся на окраинах города, можно попасть только одним путем – идя прямо. На любой же из внутренних перекрестков можно попасть или с северо-запада, или с северо-востока.

(рис.9в)

На плане города и справа от плана показаны (рис.9в):

зеленым цветом два пути, ведущих к перекрестку n=2 , k=1

лиловым цветом три пути, ведущих к перекрестку n=3 , k=1.

Теперь возле каждого перекрестка поставим (красным цветом) число всех возможных путей, ведущих к нему (рис.9г). Посчитайте их сами.

(рис.9г)

Как видите, красные цифры(число путей, ведущих из точки А на каждый перекресток), тоже образует треугольник. Изобразим этот числовой треугольник, он же треугольник Паскаля, отдельно:

(рис.9д)

Свойства треугольника Паскаля

1.Первое свойство бросается в глаза:каждая цифра равна сумме двух соседних цифр, расположенных над ней. У крайних цифр только по одному верхнему соседу, так что для них эта «сумма» состоит из одного слагаемого.

2. Мы видим, что число путей к перекрестку определяется его «адресом», т.е. рядом и местом в ряду. Интересно, можно ли, зная «адрес» перекрестка, выразить число возможных путей к нему формулой, не строя треугольник? Число путей к определенному перекрестку обозначим вот так:

Чтобы ответить на этот вопрос, посмотрим еще раз на чертеж . Чтобы попасть к перекрестку n=3, k=1 нужно пройти 3 квартала, при этом 1 квартал пройти в юго-восточном направлении. Причем все равно, какой это будет квартал. Т.е. из множества, состоящего из 3 кварталов, мы выбираем 1 квартал. Всего таких путей три.

Подсчитайте напрямую число путей еще для нескольких перекрестков. Тогда вы придете к такому выводу:

чтобы попасть на n-й ряд, нужно пройти n кварталов, а чтобы попасть на k-й перекресток n-го ряда, k кварталов из этих n нужно пройти на юго-восток (остальные n-k – на юго-запад). Сколькими способами можно выбрать из n кварталов те k кварталов, которые будут пройдены на юго-восток? По определению, это число сочетаний – Ckn. Т.е. у каждого перекрестка, оказывается, будет стоять число путей к нему Ckn, где n – номер ряда, а k – номер перекрестка в ряду:

(12).

Т.е. число треугольника Паскаля, стоящее в ряду n на месте k, равно числу сочетаний из n элементов по k.
Формула (12) и позволяет найти число путей к перекрестку по его адресу. Поскольку по формуле (8)

получаем из (12)

(13).