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



Скачать 185.74 Kb.
страница1/3
Дата09.07.2014
Размер185.74 Kb.
ТипАвтореферат
  1   2   3


На правах рукописи

Серёгина Марина Валерьевна

КОМБИНАТОРНЫЕ СВОЙСТВА СЕЧЕНИЙ

ОБОБЩЕННЫХ ПИРАМИД ПАСКАЛЯ
01.01.09 – дискретная математика и

математическая кибернетика
АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата физико-математических наук

Иркутск – 2011

Работа выполнена в ГОУ ВПО «Иркутский государственный университет путей сообщения»

Научный руководитель: доктор физико-математических наук,

профессор

Кузьмин Олег Викторович
Официальные оппоненты: доктор физико-математических наук,

профессор

Забудский Геннадий Григорьевич
кандидат технических наук, доцент

Семёнов Александр Анатольевич
Ведущая организация: Институт прикладных математических исследований Карельского научного центра РАН
Защита состоится 18 марта 2011 года в 14:00 на заседании диссертационного совета Д 212.074.01 при Иркутском государственном университете по адресу: 664003, г. Иркутск, ул. К.Маркса, 1, Институт математики, экономики и информатики ИГУ.
С диссертацией можно ознакомиться в научной библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).
Автореферат разослан 14 февраля 2011 г.


Ученый секретарь

диссертационного совета,

канд. физ.-мат. наук, доцент
Антоник В. Г.


Общая характеристика работы

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

По мере развития комбинаторных методов дискретной математики возникают вопросы классификации и представления материала, что, в свою очередь, вызывает необходимость создания единого подхода для получения и изучения комбинаторных объектов. Наряду с классическими подходами Мак-Магона и Редфилда-Пойа возникают и новые, в частности, Рота, Платонова, Сачкова. В последние десятилетия расширился круг исследователей, как, пожалуй, самой известной и изящной численной схемы, носящей название треугольник Паскаля, так и его плоских и пространственных аналогов и обобщений. Идеи построения арифметических треугольников комбинаторного происхождения и их приложений высказывались многими авторами (С. Гамберг, Т. Грин, Д. Кнут, Д. Прист, Дж. Риордан, Д.
Рождерс, С. Смит, Р. Стенли, В. Хоггат, Л. Шапиро, Б.А. Бондаренко, О.В. Кузьмин, М.Л. Платонов, В.А. Успенский, В.Н. Докин, Т.Г. Тюрнева и др.), причем в некоторых работах, естественно, полученные результаты повторяются. Первые попытки классификации комбинаторных объектов на основе построения соответствующих пирамид Паскаля были предприняты в 80-х годах прошлого столетия Б.А.Бондаренко, а достаточно общую схему, названную обобщенной пирамидой Паскаля, предложил в конце 90-х годов XX века О.В. Кузьмин.

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

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



с граничными условиями

, , если или .

Обозначая триномиальные коэффициенты символом , и полагая

, (1)

записываем разложение тринома в форме

.

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

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

(2)

с граничными условиями

, , если или .

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 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 таблиц.
Основное содержание работы

Во введении обосновывается актуальность темы диссертации, проводится обзор литературы и кратко характеризуется ее содержание.

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

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

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

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

. (3)

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

Пусть в уравнении (3) параметры , , , . Полагаем , тогда треугольник сечения конечен и уравнение (3) принимает вид

.

Обозначим:

.

Утверждение 1.1. Сумма элементов -го плоского сечения пирамиды Паскаля определяется по формуле

. (4)

Для частично упорядоченного множества символом будем обозначать его «средний» элемент, которому предшествует минимальный и следует максимальный элементы этого множества.

Обозначим:

,

,

.

Теорема 1.1. Последовательность сумм удовлетворяет рекуррентному соотношению

(5)

с начальными условиями

;

, , задаются соотношениями

, (6)

, , задаются соотношениями

. (7)
  1   2   3

Похожие:

Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconКомбинаторные свойства (0,1)-матриц и взвешенные пути на решетках 01. 01. 09 дискретная математика и математическая кибернетика

Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconПостроение оптимальных пространственных фигур методами нелинейного программирования 01. 01. 09 Дискретная математика и математическая кибернетика
...
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика icon01. 01. 09 Дискретная математика и математическая кибернетика Теория сложности алгоритмов и вычислений
Кодирование непрерывных сообщений. Эпсилон-энтропия источников непрерывных сообщений
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconНекоторые задачи перечисления помеченных связных графов 01. 01. 09 дискретная математика и математическая кибернетика
Работа выполнена в отделе математических проблем распознавания и методов комбинаторного анализа Вычислительного центра имени А. А....
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconНекоторые задачи перечисления помеченных связных графов 01. 01. 09 дискретная математика и математическая кибернетика
Работа выполнена в отделе математических проблем распознавания и методов комбинаторного анализа Вычислительного центра имени А. А....
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconРабочей программы дисциплины дискретная математика
Дискретная математика и математическая логика входят в цикл профессиональных дисциплин в базовой части. Для их успешного изучения...
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconПрограмма-минимум кандидатского экзамена по специальности 01. 01. 09 «Математическая кибернетика и дискретная математика» по физико-математическим наукам
Программа разработана экспертным советом Высшей аттестационной комиссии Министерства образования Российской Федерации по математике...
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconЖурнала «кибернетика и системный анализ» за 2001 год №1 кибернетика
Ляшко С. И., Семенов В. В. Об управляемости линейных распределенных систем в классах обобщенных воздействий
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconПрограмма наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Комбинаторные свойства сечений обобщенных пирамид паскаля 01. 01. 09 дискретная математика и математическая кибернетика iconПрограмма курса «Дискретная математика»
Понятие множества. Равенство и включение множеств. Пустое и универсальное множества. Булевы операции, их свойства. Упорядоченные...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org