Введение к работе
Актуальность темы, В настоящее время, в связи с интенсивным развитием компьютерных и информационных технологий, растет число комбинаторных задач и их разнообразие. К решению таких задач прямо или косвенно приводят многие вопросы теоретического и практического характера, связанные с существованием и подсчетом числа комбинаторных конфигураций из элементов некоторого множества, построенных в соответствии с определенными правилами. Характерная общность и высокая степень абстракции постановок задач дает возможность получения различных интерпретаций комбинаторных объектов и широту их применения.
По мере развития комбинаторных методов дискретной математики возникают вопросы классификации и представления материала, что, в свою очередь, вызывает необходимость создания единого подхода для получения и изучения комбинаторных объектов. Наряду с классическими подходами Мак-Магона и Редфилда-Пойа возникают и новые, в частности, Рота, Платонова, Сачкова. В последние десятилетия расширился круг исследователей, как, пожалуй, самой известной и изящной численной схемы, носящей название треугольник Паскаля, так и его плоских и пространственных аналогов и обобщений. Идеи построения арифметических треугольников комбинаторного происхождения и их приложений высказывались многими авторами (С. Гамберг, Т. Грин, Д. Кнут, Д. Прист, Дж. Риордан, Д. Рождерс, С. Смит, Р. Стенли, В. Хоггат, Л. Шапиро, Б.А. Бондаренко, О.В. Кузьмин, М.Л. Платонов, В.А. Успенский, В.Н. Докин, Т.Г. Тюрнева и др.), причем в некоторых работах, естественно, полученные результаты повторяются. Первые попытки классификации комбинаторных объектов на основе построения соответствующих пирамид Паскаля были предприняты в 80-х годах прошлого столетия Б.А.Бондаренко, а достаточно общую схему, названную обобщенной пирамидой Паскаля, предложил в конце 90-х годов XX века О.В. Кузьмин.
Треугольник Паскаля прост, но в то же время таит в себе неисчерпаемые возможности и связывает воедино различные разделы математики, не имеющие на первый взгляд между собой ничего общего. Эти обстоятельства побуждают искать всевозможные обобщения биномиальных коэффициентов. Некоторые из возможных обобщений -элементы обобщенного треугольника Паскаля, триномиальные коэффициенты и их обобщения, каждые из которых, в свою очередь, могут служить математическими моделями разнообразных дискретных процессов.
Обобщенным треугольником Паскаля называем треугольную таблицу, элементы которой для целых неотрицательных п, к, I удовлетворяют рекуррентным соотношениям:
^(и.*) = а.^(и-1.*-1) + А^(«-1.*)
с граничными условиями
V(0,0) = Vo,V(n,k) = O,ecimmm(n,k,n-k)<0 илии^М0.
( Обозначая триномиальные коэффициенты символом
;, и полагая к,1 j
п к,\
л и!
k\l\{n-k-iy записываем разложение тринома (х0 + х1+х2)" в форме
(1)
(x0 + x, + x2)" = ^
уЫ> i=o\k>lj
хкх'х"'к''
Применяемое представление (1) упорядочивает расположение триномиальных коэффициентов в пирамиде Паскаля и ее сечениях, подобно тому, как расположены биномиальные коэффициенты в треугольнике Паскаля.
Обобщенной пирамидой Паскаля (V -пирамидой) называем трехгранный пирамидальный массив, элементы которого для целых неотрицательных п, к, I удовлетворяют рекуррентным соотношениям:
V{nXl) = an^/{n-\,k-V) + PnkJj{n-\Xl-\)+Yn,/(n-\,k,l){2) с граничными условиями
К(0,0,0) = К0, К(и,М) = 0,если тіп(п,к,1,п-к-і)<0шт neN0. Настоящая диссертационная работа принадлежит области комбинаторного анализа и посвящена развитию теории обобщенных пирамид Паскаля, позволяющей изучать свойства комбинаторных чисел при помощи выявления связей между элементами сечений обобщенной пирамиды Паскаля.
Разумеется, без геометрического представления результатов, изучаемые в диссертации объекты, которые возникали в разное время и из разных по своей природе задач, создавали впечатление разрозненности. Геометрический метод представления комбинаторных объектов в качестве элементов обобщенных пирамид Паскаля позволяет единым образом выявлять новые свойства и интерпретации этих объектов. Так, например, рассмотрение элементов, расположенных на плоских сечениях обычной и обобщенной пирамид Паскаля, позволяет получать новые рекуррентные соотношения и производящие функции для ряда хорошо известных комбинаторных чисел и их некоторых обобщений. Изучение сечений и частей обобщенной пирамиды Паскаля позволяет устанавливать новые соотношения между известными объектами, переносить свойства одних объектов на другие, а также получать новые объекты, ранее не изученные.
Основная цель работы состоит в разработке методов исследования частей обобщенных пирамид Паскаля, порождающих объекты комбинаторного происхождения, систематизации известных и получении новых соотношений для этих объектов.
Методы исследований. В работе используются методы комбинаторного анализа, линейной алгебры и геометрии, компьютерного моделирования.
Научная новизна. Продолжена разработка теории обобщенных пирамид Паскаля как единого инструмента получения, систематизации и изучения многих известных семейств комбинаторных чисел. Введены и изучены
суммы элементов плоских сечений обобщенных пирамид Паскаля и суммы элементов пирамид, названных верхними отсечениями обобщенных пирамид Паскаля, являющиеся обобщениями известных комбинаторных объектов.
Основные результаты, выносимые на защиту.
-
Разработан метод получения, систематизации и исследования семейств комбинаторных чисел, основанный на применении сечений обобщенных пирамид Паскаля.
-
Исследованы комбинаторные свойства плоских сечений и верхних отсечений обобщенных пирамид Паскаля.
-
Получены перечислительные интерпретации ряда известных и новых комбинаторных объектов.
Личный вклад автора состоит в развитии теории построения комбинаторных конфигураций и чисел на основе обобщенной пирамиды Паскаля, а также получении различных соотношений для известных и введенных автором комбинаторных объектов.
Все результаты, включенные в диссертацию, получены автором лично.
Теоретическая и практическая значимость. Полученные в диссертации результаты имеют значение для развития общей теории комбинаторного анализа и могут быть использованы в практических приложениях, связанных с изучением моделей дискретных иерархических систем.
Апробация работы. Результаты работы были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 2008), X Международном научном семинаре «Дискретная математика и ее приложения» (Москва, 2010), XI Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Иркутск, 2010), XI Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2010), XXII международной научно-методической конференции «Математика в ВУЗе»
(Петрозаводск, 2010), а также докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2008 - 2010), на семинарах кафедры высшей математики и прикладной информатики Забайкальского института железнодорожного транспорта (2006 - 2010).
Публикации. По теме диссертации опубликовано 10 работ. Основные результаты диссертации опубликованы в работах [1-9]. В число указанных работ входят 3 статьи [1-3] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ (редакция 2010 г.)», 4 статьи [6-9] в научных сборниках, 1 полный текст доклада [4] в материалах международного семинара. Работы [1-4] выполнены в нераздельном соавторстве с научным руководителем.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, содержащего 94 наименования, и одного приложения. Общий объем диссертации - 110 страниц, включая 24 рисунка и 5 таблиц.
