Комбинаторные свойства сечений обобщенных пирамид Паскаля

Актуальность темы

В настоящее время, в связи с интенсивным развитием компьютерных и информационных технологий, растет число комбинаторных задач и их разнообразие. К решению таких задач прямо или косвенно приводят многие вопросы теоретического и практического характера, связанные с существованием и подсчетом числа комбинаторных конфигураций из элементов некоторого множества, построенных в соответствии с определенными правилами (см., напр., [10, 15, 17, 20, 33, 39, 81]). Характерная общность и высокая степень абстракции постановок задач дает возможность получения различных интерпретаций комбинаторных объектов и широту их применения (см., напр., [5, 21, 32, 45, 64]).

По мере развития комбинаторных методов дискретной математики возникают вопросы классификации и представления материала, что, в свою очередь, вызывает необходимость создания единого подхода для получения и изучения комбинаторных объектов. Наряду с классическими подходами Мак-Магона и Редфилда-Пойа возникают и новые, в частности, Рота, Платонова, Сачкова (см., напр., [25, 36−38, 45, 81, 87]). В последние десятилетия расширился круг исследователей, как, пожалуй, самой известной и изящной численной схемы, носящей название треугольник Паскаля (см., напр., [1−2, 6, 8, 9−11, 14, 24−26, 37, 40−41, 43, 52−58, 65−66, 68, 71, 75−76, 81, 85]), так и его плоских и пространственных аналогов и обобщений. Идеи построения арифметических треугольников комбинаторного происхождения и их приложений высказывались многими авторами (см., напр., [3, 7, 12−13, 16−18, 22−27, 34, 36−38, 41−42, 44, 55−57, 59−60, 62−63, 69−71, 74−79, 84, 87, 93] и др.), причем в некоторых работах, естественно, полученные результаты повторяются. Первые попытки классификации комбинаторных объектов на основе построения соответствующих пирамид Паскаля были предприняты в 80-х годах прошлого столетия Б. А. Бондаренко [7], а достаточно общую схему, названную обобщенной пирамидой Паскаля, предложил в конце 90-х годов XX века О. В. Кузьмин [25].

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

Числа Фибоначчи.

Рис. 0.1. Треугольник Паскаля.

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

Таблица 0.1. Треугольник Паскаля = 0 1 2 3 4 5 6 л = 0 1.

1 1 1.

2 1 2 1.

3 1 3 3 1.

4 1 4 6 4 1.

5 1 5 10 10 5 1.

6 1 6 15 20 15 6 1.

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

Вдоль диагоналей, параллельных сторонам треугольника (рис. 0.1) выстроены треугольные числа и их обобщения на случай пространств всех размерностей. Суммы чисел, стоящих вдоль восходящих диагоналей, образуют хорошо известную последовательность чисел Фибоначчи (см., напр., [6, 8, 9, 25, 40, 53, 54, 89, 92, 93]). Если, спускаясь по центральному столбцу, из каждого числа вычитать соседнее справа (или слева!), то возникает последовательность чисел Каталана (см., напр., [25, 92]). Числа, стоящие по горизонтальным строкам, являются биномиальными коэффициентами. Строка с номером п состоит из коэффициентов разложения бинома + Именно это фундаментальное свойство треугольника Паскаля связывает его не только с комбинаторикой и теорией вероятностей, но и с другими областями математики и ее приложений.

Биномиальные коэффициенты можно получить путем разложения производящей функции, являющейся степенью бинома: п /я ьо’с X.

0.1) где п.

0.2) к (п — к).

Коэффициенты разложения бинома удовлетворяют рекуррентному соотношению (правилу Паскаля) Л Г и Л ЛЛ.

0.3) и + Г| Г п л м к) с начальными условиями пЛ.

1,.

Vе У 0, если тт (п, к, п — к)<0 или п<£.

Биномиальные коэффициенты укудовлетворяют граничным условиям 1 и равенству (правилу симметрии) м (П).

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

II п к=о к у 2.

Биномиальные коэффициенты строятся из натуральных чисел при помощи арифметических операций п (п — 1).(п — к + 1) 1, к) к (к-1).2−1 п> 1, 1 <�к<�п.

Они широко используются как в самой математике, так и в ее приложениях. Эти обстоятельства побуждают искать всевозможные обобщения биномиальных коэффициентов. Некоторые из возможных обобщенийэлементы обобщенного треугольника Паскаля V (п, к) (см., напр., [7, 24, 25, 27,.

60, 63, 77]), триномиальные коэффициенты г п к, IJ см., напр., [7, 13, 24, 25, 65,.

73, 82, 86, 89, 91, 94]) и их обобщения (см., напр., [4, 7, 19, 24, 25, 27, 78, 82, 83]), каждые из которых, в свою очередь, могут служить математическими моделями разнообразных дискретных процессов (см., напр., [12, 25, 27]).

Следуя [25], обобщенным треугольником Паскаля (Vтреугольником) называем треугольную таблицу, элементы которой для целых неотрицательных п, к, / удовлетворяют рекуррентным соотношениям:

V (п, к) = ап<�ку (л — 1Д -1) + ДаУ (я — 1Д) (0.4) с граничными условиями.

У (0,0) = У0, У (п, к) = 0, если хтп (п, к, п-к) <0 или ле? М0.

Многие известные комбинаторные числа являются частными случаями элементов обобщенного треугольника Паскаля. Так, например, если в соотношении (0.4) при У0 = 1 положить апк — /Зпк = 1, п> 1, 0<�к<�п, тогда.

V (п, к) = т. е. имеем обычный треугольник Паскаля.

Если считать У0 = 1, то при ап к = 1, Да = ц, пх, лг > 1, 0 <�к<�п, имеем V (п, к) = Вк и из соотношения (0.4) следует рекуррентная формула в:=впк:[ + Мп{в: — (о.5) определяющая обобщенные числа Стирлинга первого рода (см., напр., [25]).

При апк = 1, /Зпк = /4, и> 1, 0<�к<�п, имеем V (п, к) = Ак и рекуррентную формулу.

Апк=А?:1+МкА?-1, (0.6) определяющую обобщенные числа Стирлинга второго рода (см., напр., [25]).

Треугольники, составленные из чисел Вк и Ак, называются Ви А-треугольниками соответственно.

Другим известным обобщением элементов треугольника Паскаля являются пЛ триномиальные коэффициенты и их обобщения, которые также обладают к, 1 у широкой приложимостью. Разнообразные семейства дискретных распределений — теоретические модели и природные популяции — способны формироваться по описываемой пирамидальной схеме (см., напр., [25]).

Как указано в (0.1), биномиальные коэффициенты.

6Л получаются в результате разложения бинома (1 + *)" и выписываются в виде треугольника Паскаля в той или иной форме. Используя две переменные х0 и х{, это разложение можно записать в виде п к=о) хкх" ~к.

Обозначая триномиальные коэффициенты символом целые неотрицательные числа, и полагая пЛ ук, 1 где п, к, I п к, 1 п к1(п-к-1)' записываем разложение тринома (х0 + х1 + х2)" в форме п п-к х0+х1+х2)п.

1 п-к (А к=0 1=о к, IJ.

0.7).

Рис. 0.2. Пирамида Паскаля. 8.

Применяемое представление (0.7) упорядочивает расположение триномиальных коэффициентов в пирамиде Паскаля (см., напр., [7, 13, 24, 25,.

65, 73, 82, 86, 89, 91, 94]) и ее сечениях (рис. 0.2). Заметим, что в.

Г п^ ук, I у число п указывает номер горизонтального сечения пирамиды Паскаля, к — номер строки сечения (треугольника), а / — номер его столбца (диагонали).

Нетрудно убедиться, что для триномиальных коэффициентов (0.7) справедливо рекуррентное соотношение.

С и (п.

0.8) л + Л (п Л Г гс > (П 1 к, 1) — 1,^к, 1 к / 1 у.

01 (п Л.

— 1, к, 1 ^ с начальными условиями 0, если тт (п, к,1,п-к-1) <0 или п<£ М0.

Рекуррентное соотношение (0.8) позволяет сделать вывод о том, что любой внутренний элемент пирамиды Паскаля, стоящий в пм сечении, равен сумме трех элементов, расположенных в углах элементарного треугольника (п — 1) -го сечения пирамиды.

Аналогично биномиальным триномиальные коэффициенты удовлетворяют условиям П 1-(, 0, о/и 0, п 1^к, 1 ^ г пЛ (п ^ 0, п 1 и равенствам П ^ Г П Л [ П 1 (п л.

1 ^ > к —^гъ к /9 /у ^/С) ух 1с /^ подтверждающим наличие трех осей симметрии в пирамиде Паскаля. Приведем формулу суммирования п п—к, П.

Щк1 к=о /=0 Vе" 1 Л 3.

0.9) где, как указано выше, п к I у", I у 0, если гтп (п, к,1,п-к — 1)<0 или п<£ М0.

Пирамиду Паскаля можно строить в форме тетраэдра, а также пирамиды с различными значениями двухгранных углов, один из которых прямой. В п-м сечении (треугольнике) пирамиды (п = 0,1,2,.), параллельном основанию, располагаются коэффициенты.

Г п^ подобно тому, как расположены биномиальные коэффициенты в треугольнике Паскаля. По трем внешним ребрам пирамиды Паскаля (рис. 0.2) стоят единицы. Каждая из трех боковых граней представляет собой треугольник Паскаля.

Если сечение пирамиды Паскаля является правильным треугольником, то при любом допустимом значении п оно имеет три оси симметрии. На рис. 0.3, Л симметрии сечения при /1 = 4.

Непосредственно из формул (0.2) и (0.7) следует соотношение п взятом из [25], показано расположение элементов и указаны оси пЛ &bdquo-к, 1 V п п — к I наглядно иллюстрирующее наличие тесной связи между биномиальными и триномиальными коэффициентами. п-к-1 п.

4'.

3 2 1 0.

А ч1 2.

4 4.

VI /Л ЛГ^ 1 41/.

Г 4 5 4.

Рис. 0.3. Оси симметрии сечения пирамиды Паскаля.

Следуя [21], обобщенной пирамидой Паскаля (У-пирамидой) называем трехгранный пирамидальный массив, элементы которого для целых неотрицательных п, к, / удовлетворяют рекуррентным соотношениям: + + (0.10) с граничными условиями.

V (ОДО) = У0, V (п, к,1) = 0, если тт (п, к, 1, п-к-1)< 0 или п<£ М0.

Некоторые известные комбинаторные числа являются частными случаями элементов обобщенной пирамиды Паскаля. Так, например, если в соотношении (0.10) при У0 = 1 положить апЫ = /Зпк1 = упЛ1 =1, п> 1, 0 <к + 1<п, тогда ч Г И.

V (п, к,1) =, т. е. имеем обычную пирамиду Паскаля. ук, 1 ^.

Если считать У0=1, то при апХ1=ссп{, Рп, и=Рп.х, Гп, к,1=Гп-1> 0 <к + 1<п, имеем V (п, к,1) = Вк1, и из соотношения (0.10) следует рекуррентная формула впи = + рпхвпк^+, (0.11) определяющая обобщенные триномиальные коэффициенты первого рода (см., напр., [25]).

При апк1 = ак, Да,=Д, Гп, к,1 = П> 0<�к+1<�п, имеем V (п, к,1) = Апи, а из соотношения (0.10) имеем рекуррентную формулу.

Аи = ак-Л:1 +ЛЛ" —.+пЛ", Л (0.12) определяющую обобщенные триномиальные коэффициенты второго рода (см., напр., [25]).

Пирамиды, составленные из чисел В’и и Апк1, называются Ви Апирамидами соответственно.

При от = 1, 1 = 0 из (0.11) и (0.12) получаются рекуррентные соотношения.

0.5) и (0.6) для обобщенных чисел Стирлинга первого В" и второго А" рода соответственно.

Настоящая диссертационная работа принадлежит области комбинаторного.

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

Разумеется, без геометрического представления результатов, изучаемые в диссертации объекты, которые возникали в разное время и из разных по своей природе задач, создавали впечатление разрозненности. Геометрический^ метод представления комбинаторных объектов в качестве элементов обобщенных пирамид Паскаля позволяет единым образом выявлять новые свойства и интерпретации этих объектов. Так, например, рассмотрение элементов, расположенных на плоских сечениях обычной и обобщенной пирамид Паскаляпозволяет получать новые рекуррентные соотношения и производящие функции для ряда хорошо известных комбинаторных чисел и их некоторых обобщений. Изучение сечений и частей обобщенной пирамиды Паскаля позволяет устанавливать новые соотношения между известными объектами, переносить свойства одних объектов, надругие, а также получать новые объекты, ранее не изученные.

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

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

Научная*, новизна. Продолжена разработка теории обобщенных пирамид Паскаля как единого инструмента получения, систематизации и изучения многих известных семейств комбинаторных чисел. Введены и. изучены суммы элементов плоских сечений обобщенных пирамид Паскаля и суммы элементов пирамид, названных верхними отсечениями обобщенных пирамид Паскаля, являющиеся обобщениями известных комбинаторных объектов.

Основные результаты, выносимые на защиту.

1. Разработан метод получения, систематизации и исследования семейств комбинаторных чисел, основанный на применении сечений обобщенных пирамид Паскаля.

2. Исследованы комбинаторные свойства плоских сечений и верхних отсечений обобщенных пирамид Паскаля.

3. Получены перечислительные интерпретации ряда известных и новых комбинаторных объектов.

Личный вклад автора состоит в развитии теории построения комбинаторных конфигураций и чисел на основе обобщенной пирамиды Паскаля, а также получении различных соотношений для известных и введенных автором комбинаторных объектов.

Все результаты, включенные в диссертацию, получены автором лично.

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

Содержательная часть работы включает введение и три главы.

Первая глава диссертационной работы посвящена исследованию некоторых комбинаторных свойств-пирамиды Паскаля.

В параграфах 1.1 и 1.2 введены понятияплоских сечений и верхних отсечений пирамиды Паскаля соответственно. Найдены* значения сумм элементов плоских сечений и верхних отсечений пирамиды Паскаля, а также рекуррентные соотношения и производящие функции этих сумм.

В параграфе 1.3 получены известные и новые соотношения и производящие функции для чисел и сумм чисел Ъы, Якобсталя, Трибоначчи, Пелля и многих других.

Во второй главе исследуются" некоторые комбинаторные свойства обобщенных пирамид Паскаля.

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

В параграфе 2.3 получены известные и новые соотношения для обобщенных чисел Трибоначчи первого и второго рода и их сумм.

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

В параграфе 3.1 найдены интерпретации сумм плоских сечений пирамиды Паскаля в терминах полных покрытий отрезка. В частных случаях получены новые интерпретации чисел 3 м, Якобсталя, Трибоначчи, Пелля и других.

В/ параграфе' 3.2 найдены некоторые интерпретации сумм элементов верхних отсечений пирамиды Паскаля в терминах неполных покрытий отрезка. В частных случаях получены новые интерпретации сумм чисел З’у, Якобсталя, Трибоначчи, Пелля и других.

В параграфе 3.3 найдены интерпретации сумм элементов плоских сечений и верхних отсечений обобщенных пирамид Паскаля, в терминах развития популяции. В частном случае получены известная биологическая интерпретация элементов обобщенной пирамиды Паскаляа также интерпретации сумм элементов плоских сечений* и верхних отсечений пирамиды Паскаля в терминах полных и неполных покрытий отрезка соответственно.

Апробация работы. Результаты работы, были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 2008), X Международном научном семинаре «Дискретная математика и ее приложения» (Москва, 2010), XI Всероссийской, конференции молодых ученых по математическому моделированию и информационным технологиям (Иркутск, 2010), XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2010), XXII международной научно-методической конференции «Математика в ВУЗе» (Петрозаводск, 2010), а также докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2008 — 2010), на семинарах кафедры высшей математики и прикладной информатики Забайкальского института железнодорожного транспорта (2006 — 2010).

Публикации. По теме диссертации опубликовано 10 работ. Основные результаты диссертации опубликованы в работах [28−31, 46−51]. В число указанных работ входят 3 статьи [28−30] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ (редакция 2010 г.)», 4 статьи [46, 47, 50, 51] в научных сборниках, 1 полный текст доклада [31] в материалах международного семинара. Работы [28−31] выполнены в нераздельном соавторстве с научным руководителем.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, содержащего 94 наименования, и одного приложения. Общий объем диссертации — 110 страниц, включая 24 рисунка и 5 таблиц.

ЗАКЛЮЧЕНИЕ

.

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

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

Результаты, полученные в диссертации, использовались при чтении специальных курсов по перечислительной комбинаторике и комбинаторным методам теории вероятностей для студентов института математики, экономики и информатики ИГУ и могут быть использованы в курсе лекций по дискретной математике в ЗабИЖТ ИрГУПС.