Треугольник паскаля, его применение в программировании

Кочев Павел,

Филиал КГПУ им. В.П. Астафьева в г. Канске

Уничижительная формулировка "незаменимых людей нет", столь любимая бездарными управленцами, может и подошла бы, если бы речь шла о копании траншеи или уборке мусора. Всякий же вид деятельности, связанный с творчеством, наоборот, покажет незаменимость и уникальность каждого человека. А когда речь идет о гениях, то мы все должны благодарить судьбу за возможность пользоваться плодами их деятельности, за исходящий от них свет, освещающий пути развития человечества. На сайте журнала "Знание-сила" есть голосование по вопросу о том, кого вы считаете самым значительным ученым за прошедшие 2000 лет. И, естественно, среди самых популярных ученых мы по праву видим имя Блеза Паскаля (1623-1662).

Блез Паскаль вошел в историю как выдающийся математик, физик, философ и писатель. Его именем благодарными потомками названы единица давления (паскаль) и получивший чрезвычайно широкое распространение язык программирования. Особенно популярен был Турбо Паскаль 5.5 для ДОС, ныне - Борланд Паскаль 7.0 и его дальнейшее развитие в Delphi. Наверное самой известной математической работой Блеза Паскаля является трактат об "арифметическом треугольнике", образованном биномиальными коэффициентами (треугольник Паскаля), который имеет применение в теории вероятностей и обладает удивительными и занимательными свойствами.

На вершине треугольника стоит 1. Треугольник можно продолжать неограниченно. Он обладает симметрией относительно вертикальной оси, проходящей через его вершину. Вдоль диагоналей параллельных сторонам треугольника  выстроены треугольные числа и их обобщения на случай пространств всех размерностей. Треугольные числа в самом обычном и привычном нам виде показывают, сколько касающихся кружков можно расположить в виде треугольника - как классический пример начальная расстановка шаров в бильярде. К одной монетке можно прислонить еще две - итого три - к двум можно приладить еще три - итого шесть. Продолжая наращивать ряды с сохранением формы треугольника получим ряд 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66.... Этот замечательный ряд, каждый член которого равен сумме натурального ряда чисел (55=1+2+3+4+5+6+7+8+9+10), содержит также множество знакомцев, хорошо известных любителям математики: 6 и 28 - совершенные числа, 36 - квадратное число, 8 и 21 - числа Фибоначчи. Следующая линия покажет нам тетраэдральные числа - один шар мы можем положить на три - итого четыре, под три подложим шесть (напрягитесь и представьте!) - итого десять, и так далее. А следующая линия (1, 5, 15, 35,...) продемонстрирует попытку выкладывания гипертетраэдра в четырехмерном пространстве - один шар касается четырех, а те, в свою очередь, десяти... В нашем мире такое невозможно, только в четырехмерном, виртуальном. И тем более пятимерный тетраэдр, о котором свидетельствует следующая линия, он может существовать только в рассуждениях топологов. А о чем же говорит нам самая верхняя линия, на которой расположились числа натурального ряда? Это тоже треугольные числа, но одномерные, показывающие, сколько шаров можно выложить вдоль линии - сколько есть, столько и выложите. Если уж идти до конца, то самый верхний ряд из единиц - это тоже треугольные числа в нульмерном пространстве - сколько бы шаров мы не взяли - больше одного расположить не сможем, ибо просто негде - нет ни длины, ни ширины, ни высоты. Даже беглого взгляда, брошенного на треугольник Паскаля, достаточно, чтобы отметить следующие любопытные факты: 10 ядер можно сложить и в виде тетраэдра и в виде плоского треугольника. А 56 гиперядер, образующих тетраэдр в пятимерном пространстве, можно уложить в обычный привычный трехмерный тетраэдр, однако, если бы мы попытались выложить из 56 ядер треугольник, то одно ядро осталось бы лишним.

Хочу остановиться на числах, стоящих на горизонтальных строках треугольника Паскаля, - это биномиальные коэффициенты, то есть коэффициенты разложения (x+y)n по степеням x и y. Например, (x+y)2=x2+2xy+y2 и (x+y)3=x3+3x2y+3xy2+y3. Коэффициенты разложения 1, 2, 2 стоят во второй строке, а 1, 3, 3, 1 - в третьей строке треугольника. Чтобы найти коэффициенты разложения (x+y)n, достаточно взглянуть на n-ую строку треугольника. Именно это фундаментальное свойство треугольника Паскаля связывает его с комбинаторикой и теорией вероятности, превращая в удобное средство проведения вычислений. Предположим (пример от Мартина Гарднера), что некий шейх, следуя законам гостеприимства, решает отдать вам трех из семи своих жен. Сколько различных выборов вы можете сделать среди прекрасных обитательниц гарема? Для ответа на этот волнующий вопрос необходимо лишь найти число, стоящее на пересечении диагонали 3 и строки 7: оно оказывается равным 35. Если, охваченные радостным волнением, вы перепутаете номера диагонали и строки и будете искать число, стоящее на пересечении диагонали 7 со строкой 3, то обнаружите, что они не

пересекаются. То есть сам метод не дает вам ошибиться! В общем случае, число, показывающее, сколькими способами можно выбрать n элементов из множества, содержащего r различных элементов, стоит на пересечении n-ной диагонали и r-ой строки. И еще раз, для тех, кто хоть что-то понял. Число возможных сочетаний из n элементов по m определяется формулой Где n!=1*2*3*4*....*n так называемый факториал числа n. И тех же трех жен из семи можно выбрать столькими вариантами: C37 =7!/3!/4!=1*2*3*4*5*6*7/1*2*3/1*2*3*4=5040/6/24=35, что мы раньше и получили. А значения биномиальных коэффициентов определяются по формуле причем, они же и являются, как мы выяснили, строками треугольника Паскаля, связывая непостижимым образом этот треугольник с комбинаторикой и разложением двучлена по степеням. Кстати, из формулы сочетаний следует, что количество вариантов выбора трех из семи равно количеству вариантов выбора четырех из семи, или, число вариантов заполнения карточек Спортлото 5 из 36 равно количеству выбора 31 из 36, поразмышляйте об этом приятном предмете. Всех наш в школе заставляли запоминать формулы сокращенного умножения наизусть, непосредственно квадрат и куб. Но как быть если степень превышает значение 3? Итак, рассмотрев эту проблему, было решено спрограммировать задачу, которая раскладывает формулу в любой степени. Эта программа была написана на учебном языке программирования высокого уровня Turbo Pascal. Получившаяся программа не обладает должным интерфейсом, но все же выполняет свою задачу при расстановке коэффициентов. Данную программу можно использовать при проверке комбинаторных задач, а также она может облегчить жизнь любому школьнику.

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

Библиографический список:

В. А. Успенский Треугольник Паскаля Издание второе, дополнение Москва «Наука» 1979

https://combinatorica.narod.ru/third.html

https://www.pereplet.ru/obrazovanie/stsoros/1006.html