Электронные таблицы и треугольник Паскаля

1.1. Создание треугольника и основные его свойства

Треугольник Паскаля — это бесконечная таблица из чисел, которая имеет треугольную форму. Главный принцип этого треугольника состоит в том, что по его бокам находятся единицы, а каждое число внутри этого треугольника равно сумме тех двух чисел, что расположены над этим самым числом. На рисунке 1.1 покажем пример одного из треугольников Паскаля.

Рисунок 1.1.

Уточним, как обычно выглядит треугольник Паскаля:

— каждая вершина треугольника Паскаля (верхняя, нижняя левая и нижняя правая) — это единица;

— если показывать треугольник Паскаля в виде равностороннего треугольника, тогда левая боковая сторона и правая боковая сторона будут состоять из единиц;

— внутри треугольника Паскаля каждая цифра равна сумме тех двух цифр, которые находятся над этой самой цифрой — это и есть самое главное правило создания треугольника Паскаля;

— треугольник Паскаля бесконечен. Это значит, что можно его продлять вниз бесконечное число раз.

У треугольника Паскаля есть несколько интересных свойств. Например, можно добавить нумерацию строк в треугольник Паскаля, при этом начать нумерацию не с единицы, а с нуля, тогда верхняя строка будет считаться строкой номер ноль, следующая строка — строкой номер один, и так далее. Теперь можно получить одно из интересных свойств этого треугольника: сумма цифр каждой строки этого треугольника будет равна двойке в степени n, где n — это и есть номер строки (с учетом того, что верхняя строка будет иметь номер ноль). Это можно проверить, если использовать те цифры, что показаны на рисунке 1.1.

Суммы строк покажем на рисунке 1.2.

Рисунок 1.2.

Еще одно интересное свойство треугольника: если взять какое-то одно число и найти произведение всех шести чисел, что находятся вокруг этого числа, то мы получим полный квадрат (квадрат натурального числа).

На рисунке 1.3 мы покажем пример нескольких ячеек (чисел), вокруг которых образован полный квадрат.

Рисунок 1.3.

На рисунке 1.3 четко видно, что произведение всех чисел вокруг тройки — это число 144 (144=2×1×3×1×6×4). Число 144 — это 12 в квадрате.

А если перемножить 6 чисел вокруг четверки, то мы получим 900 (1×3×1×6×5×10=900). Число 900 — это квадрат числа 30.

Аналогичную ситуацию можно наблюдать для каждого числа, если в его окружении имеется ровно 6 других чисел. Произведение этих шести чисел всегда будет составлять полный квадрат.

По диагоналям треугольника Паскаля расположены разные последовательности чисел. Если начинать нумерацию диагоналей не с нуля, а с цифры 1, тогда на первой диагонали будут только единицы, на второй диагонали будут расположены все натуральные числа, на третьей диагонали находятся треугольные числа (это те числа, которые показывают, сколько касающихся кружков можно расположить в виде треугольника; например, начальная расстановка шаров в бильярде — это и есть тот самый треугольник). А на четвёртой диагонали мы уже видим тетраэдральные числа (это такие числа, которые показывают, сколько шаров может быть уложено в виде треугольной пирамиды, то есть тетраэдра). На рисунке 1.4 мы построили диагонали справа налево (если начинать с верхней части диагонали и идти вниз), однако если поменять направление, то последовательности чисел не исчезнут. Условимся, что все эти диагонали, которые начинаются на правой стороне треугольника и идут вниз и влево, будем называть «юго-западными» диагоналями, поскольку юго-запад обычно тоже находится в левом нижнем углу географической карты.

Рисунок 1.4.

Треугольник Паскаля симметричен относительно вертикальной оси. Если провести вертикальную линию в самом центре этого треугольника, то справа и слева от этой линии будут расположены одинаковые числа.

Покажем эту вертикальную ось симметрии на рисунке 1.5.

Рисунок 1.5.

Следующее интересное свойство этого треугольника: сумма чисел диагонали равна числу в следующей строке на противоположной диагонали.

Мы можем привести несколько примеров, ведь мы уже несколько раз показывали сам треугольник Паскаля.

Например, 1+2+3+4=10, а 1+4 = 5. Покажем это на рисунке 1.6.

Рисунок 1.6.

Мы здесь привели только самые интересные свойства, которые можно наблюдать у треугольника Паскаля.

Но у треугольника Паскаля есть и другие свойства, далее приведем еще несколько этих свойств.

Если из центрального числа строки с чётным порядковым номером вычесть соседнее число той же строки, то мы получим число Каталана.

Напомним первые несколько чисел Каталана:

1, 1, 2, 5, 14, 42, 132, 432, 1430.

На рисунке 1.7 покажем несколько первых чисел Каталана, которые можно получить непосредственно из треугольника Паскаля.

Рисунок 1.7.

Поскольку верхняя строка — это строка номер ноль, а эта строка содержит всего один элемент, да и с увеличением номера строки на единицу количество элементов в строке тоже увеличивается на единицу, то можно смело сказать следующее: все четные строки — это все те строки треугольника Паскаля, которые содержат нечетное количество элементов.

Кроме того, любое число треугольника Паскаля равно количеству вариантов, какими можно добраться от вершины треугольника до этого самого числа.

Единственное число, которое можно встретить в треугольнике Паскаля только один раз, — это число 2.

1.2. Применение треугольника Паскаля в математике

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

Где обычно применяют цифры Каталана?

Ответ на этот вопрос такой: для решения некоторых задач комбинаторики. Приведем несколько примеров:

Задача 1. Сколькими способами можно выпуклый n+2-угольник разрезать на треугольники непересекающимися диагоналями?

Когда число n достаточно мало, можно нарисовать все возможные варианты. Так, например, при n=0 многоугольник построить вообще нельзя, при n=1 мы строим треугольник, и для треугольника количество тех самых способов, о которых спрашивается в задаче, равно 1.

Для n=2 фигура, которая будет n+2-угольником, будет квадратом. А способов разрезать на треугольники будет всего два. В первом случае мы получим одну диагональ квадрата, во втором случае — вторую.

Покажем все варианты решения задачи для треугольника и квадрата и на рисунке 1.8.

Рисунок 1.8.

Как было показано на рисунке 1.7, единицу можно получить из строки 2 треугольника Паскаля, а двойку — из строки 4 (нумерация строк начинается с нуля).

Если пойти еще ниже по треугольнику Паскаля, то для n=3 мы получим пятиугольник (5=n+2), а количество разрезаний на треугольники будет равно 5. Это число 5 можно получить из строки 6 треугольника Паскаля.

Таким образом, для любого n для расчета из последовательности Каталана можно взять строку треугольника Паскаля с номером 2n, и из центрального числа этой строки вычесть то число, которое находится в той же строке по соседству с ним.

Еще одна важная реализация чисел Каталана связана с путями Дика на плоскости. Напомним, что путем Дика называется непрерывная ломаная в верхней полуплоскости, составленная из векторов (1, 1) и (1, -1). Эта ломаная обычно начинается в начале координат и заканчивается на оси абсцисс. Число путей Дика из 2n звеньев равно n-му числу Каталана. На рисунке 1.9 покажем все варианты путей Дика для n=1, 2 и 3.

Рисунок 1.9.

Также числа Каталана применяются для вычисления количества правильных скобочных последовательностей длины 2n.

Что характерно для правильных скобочных последовательностей?

— для каждой открывающей скобки есть закрывающая из той же пары;

— скобки закрываются в правильном порядке, то есть не может быть так, что сначала идет закрывающая, а потом открывающая из той же пары.

Задача о построении правильной скобочной последовательности отдаленно напоминает задачу о создании вложенных циклов For...Next в программировании. Там тоже нужно открывать и закрывать циклы в правильном порядке. И количество правильных вариантов расположения циклов будет равно количеству правильных скобочных последовательностей.

На рисунке 1.10 покажем все варианты правильных скобочных последовательностей для первых нескольких n.

Рисунок 1.10.

Итак, мы четко видим, что количество вариантов — это числа 1, 2 и 5. Это и есть несколько подряд чисел в ряду Каталана, их же можно получить из треугольника Паскаля.

Еще одно применение треугольника Паскаля связано с комбинаторикой.

Количество сочетаний из n по k обозначают и вычисляют так, как это показано на рисунке 1.11:

Рисунок 1.11.

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

Например, рассмотрим задачу. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?

Если решать эту задачу с помощью факториалов, то надо будет вычислять три факториала: факториал семи (7!), который равен 5040; факториал пяти (5!), который равен 120, и факториал двух (2!), который равен 2. Тогда результат задачи — это 5040 / (120×2) =21.

Но можно получить тот же результат, если не рассчитывать факториалы, а использовать треугольник Паскаля. Наше число — это пересечение строки 7 и диагонали 2, причем нумерация строк и диагоналей начинается с нуля.

Покажем это на рисунке 1.12.

Рисунок 1.12.

Итак, пересечение строки 7 и диагонали 2 — это число 21. И не надо вычислять никакие факториалы!

Есть и еще одно применение треугольника Паскаля. Треугольник Паскаля часто также называют таблицей биномиальных коэффициентов. Это значит, что при возведении суммы чисел в какую-то степень можно использовать треугольник Паскаля.

Многие помнят еще со школьных времен формулу квадрата суммы. Покажем эту формулу на рисунке 1.13.

Рисунок 1.13.

Что можно сказать по этой формуле, которая приведена на рисунке 1.13?

— здесь изображен квадрат суммы, то есть вторая степень суммы;

— количество слагаемых, сумма которых возводится в квадрат, равно двум (одно слагаемое — это число a, второе слагаемое — это число b);

— квадрат суммы двух чисел состоит из суммы трех разных элементов, причем цифровые коэффициенты при этих элементах такие: 1, 2 и 1.

Но если мы посмотрим на строку №2 треугольника Паскаля, то мы там увидим точно такие же коэффициенты (то есть 1, 2 и 1). Покажем их на рисунке 1.14.

Рисунок 1.14.

Аналогичным образом можно получить формулу для возведения в любую другую степень такую сумму, которая будет состоять из двух слагаемых. Так, например, рассмотрим строку 6 треугольника Паскаля.

Покажем это на рисунке 1.15.

Рисунок 1.15.

Как применить эту строчку треугольника Паскаля, если надо получить коэффициенты для возведения в 6-ю степень суммы двух чисел (a+b)?

Можно сразу же показать формулу, которая быстро получается из шестой строки треугольника Паскаля. Покажем эту формулу на рисунке 1.16.

Рисунок 1.16.

А теперь расскажем подробно. Первое число в шестой строке треугольника Паскаля — это единица (в данном случае уже можно начинать нумерацию не с нуля, а именно с единицы). Это значит, что при возведении числа (a+b) в шестую степень первым элементом будет первое слагаемое, то есть просто число а, но в шестой степени. Как и в случае с квадратом суммы, первым элементом будет максимальная степень первого слагаемого. А максимальная степень — это та самая степень, в которую необходимо возвести всю сумму двух слагаемых.

Следующее число шестой строки — это число 6. Это и есть следующий коэффициент. После числа 6 будет первое число (то есть а), но уже не в шестой, а в пятой степени. Если всю строку рассмотреть как отрезок, то у этого отрезка будут две основные точки: левая и правая. В левой точке у нас была первая переменная в максимальной степени (в степени 6). Хотя в этой левой точке у нас нет второго слагаемого (b), можно считать, что в этой же точке у нас есть переменная b, но она просто возведена в минимальную степень (то есть в нулевую степень). Известно, что любое положительное число в нулевой степени — это единица, поэтому a6b0=a6.

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

Если надо найти шестую степень не суммы, а разности, то формула будет похожей, разница только в знаках тех элементов, что стоят на четных местах. Покажем эту формулу на рисунке 1.17.

Рисунок 1.17.

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

Кстати, еще одно применение треугольника Паскаля заключается в получении чисел Фибоначчи. Напомним первые несколько первых чисел этого ряда:

0, 1, 1, 2, 3, 5, 8, 13, 21.

Если в треугольнике Паскаля построить не обычные диагонали, а диагонали, которые проходят через противоположные стороны самых маленьких ромбов, которые можно образовать с помощью ячеек треугольника Паскаля, то мы получим числа Фибоначчи.

Покажем это на рисунке 1.18.

Рисунок 1.18.

На рисунке 1.18 мы видим несколько сумм диагоналей, составленных именно таким способом, про который говорилось ранее. Эти суммы: 1, 1, 2, 3, 5, 8. Но ведь это и есть несколько первых чисел Фибоначчи (кроме первого числа, то есть кроме ноля). Если мы будем продолжать находить суммы аналогичных диагоналей, то с каждой новой диагональю мы будем получать следующее число из ряда чисел Фибоначчи. Правда, в некоторых книгах, особенно в старых, тот первый член последовательности, который равен нулю, опускается, тогда последовательность начинается с двух единиц — точно так же, как и в диагоналях треугольника Паскаля.

Напомню, что числа Фибоначчи — это такой числовой ряд, при котором каждое число (кроме первого и второго) равно сумме двух предыдущих чисел этого ряда.

2.1. Когда слагаемых — ровно 2

В данной главе книги мы всегда будем возводить любую сумму чисел именно в четвертую степень. Основной показатель степени всегда будет равен четырем.

Начнем с самой простой ситуации, когда надо возвести в четвертую степень сумму двух слагаемых:

(a+b) 4

Здесь все достаточно просто.

Надо взять четвертую строку треугольника Паскаля.

Напомним, как выглядит эта строка. Покажем ее на рисунке 2.1. Нижняя строка этого рисунка — это и есть четвертая строка (нумерация строк начинается с нуля).

Рисунок 2.1.

Итак, всего слагаемых будет 5.

Нужные числа в нужной строке треугольника Паскаля: 1, 4, 6, 4, 1.

Готовая формула будет такой:

(a+b) 4=a4+4a3b+6a2b2+4ab3+b4

Мы просто используем все подряд числа нужной строки треугольника Паскаля — это и есть наши коэффициенты. Если в первом слагаемом мы встречаем первую переменную в максимальной степени, а вторую переменную в минимальной (то есть в нулевой) степени, то с каждым последующим слагаемым (в правой части, после знака равенства, в итоговом результате) степень при первой переменной будет понижаться, а степень при второй переменной — повышаться. Степень каждого одночлена, то есть сумма степеней всех переменных, всегда будет равна 4, потому что 4 — это и есть тот показатель степени, в который вы возводим всю сумму.

Итак, на рисунке 2.1 главные цифры — это те, что расположены в самой нижней строке. Они и показывают нужные коэффициенты. Что касается переменных и их степеней, можно условиться так: левый нижний угол треугольника будет символизировать переменную a в максимальной, то есть четвертой, степени, а правый нижний угол треугольника — переменную b (тоже в максимальной степени). Тогда будет справедливо утверждение: чем ближе любой элемент нижней строки этого треугольника к левому нижнему углу, тем больше будет показатель степени при переменной a, но меньше показатель степени при переменной b. С правым нижним углом треугольника ситуация похожая: чем ближе любой элемент нижней строки к правому нижнему углу треугольника, тем больше показатель степени при переменной b, но меньше показатель степени при переменной a. Хотя мы несколько раз употребляли слово «треугольник», но фактически у нас «главная фигура» — это не треугольник, а только отрезок, который представляет собой только нижнюю строчку от того треугольника, что изображен на рисунке 2.1. Поэтому было бы более правильно говорить так: «строка», «отрезок», «линия». Итак, можно сформулировать тенденцию так: когда есть всего две переменных, то их схематически можно представить в виде отрезка. В левом углу этого отрезка будет первая переменная в максимальной степени, а в правом углу — вторая переменная, тоже в максимальной степени. Чем ближе любой элемент отрезка к левому углу, тем больше будет показатель степени при первой переменной, но меньше — показатель степени при второй переменной.

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

2.2. Когда слагаемых — ровно 3

Итак, рассмотрим ситуацию, при которой сумму, состоящую из трех слагаемых, нужно возвести в какую-нибудь степень. Допустим, что это будет снова четвертая степень.

Выведем формулу:

(a+b+c) 4

Можно представить, что (a+b) — это одна часть формулы, тогда c — это будет вторая часть формулы.

И тогда формулу можно будет расписать по той же схеме, что мы недавно привели, когда слагаемых было 2, а не 3.