Введение к работе
Актуальность темы Со второй половины XX века наблюдается интенсивное развитие комбинаторики - одной из основных частей современной дискретной математики Важная, но не единственная, роль в этом принадлежит изменению статуса дискретной математики в связи с развитием информационных технологий и возрастанием возможностей дискретных методов исследования Внутренние причины изменений в комбинаторике связаны с объединением и согласованием ее разделов и проникновением идей комбинаторного анализа в смежные разделы математики и другие области науки Одно из перспективных направлений исследований - комбинаторика на частично упорядоченных множествах
Настоящая диссертационная работа, принадлежащая области комбинаторного анализа, посвящена построению и изучению комбинаторных чисел и полиномов, описываемых обобщенной пирамиды Паскаля
Комбинаторные числа и различные способы их классификации известны давно Наряду с общими подходами к построению комбинаторных чисел, берущих свое начало в работах Р А Мак-Магона и А Кэли, можно отметить теорию перечисления Дж Пойа и Дж Г Редфилда М Л Платонов предложил и разработал общую схему построения комбинаторных чисел класса отображений , по построению близкую к схеме Пойа Достаточно общий подход к изучению и построению комбинаторных объектов, основанный на анализе свойств обобщенной пирамиды Паскаля, был разработан О В Кузьминым сравнительно недавно2
Классическими методами комбинаторного анализа являются, в частности, методы производящих функций и рекуррентных соотношений, геометрические и асимптотические методы Можно указать две причины, по которым применение методов теории частично упорядоченных множеств позволяет исследовать комбинаторные объекты «изнутри» Во-первых, при данном подходе комбинаторное число рассматривается как вес множества перестановок особого вида - таким образом, мы у истока задач перечисления Во-вторых, обращение Мебиуса проясня-
1 Платонов М Л Комбинаторные числа класса отображений и их приложения /МЛ Платонов М Наука, 1979
152 с
2 Кузьмин О В Обобщенные пирамиды Паскаля и их приложения / О В Кузьмин Новосибирск Наука. Сибирская
издательская фирма РАН, 2000 294 с
ет строение объектов, поскольку большинство семейств дискретных структур, которые часто лишены каких-то алгебраических законов композиции, тем не менее, обычно снабжены естественным частичным порядком Это обусловливает актуальность темы исследований
Изучение решеток и частично упорядоченных множеств имеет свое начало в работах Г Буля, Ч С Пирса, Е Шредера и Р Дедекинда Развитие этой теории началось в 1930-х годах с работ Г Биркгофа Идея алгебр инцидентности восходит к Р Дедекинду и Е Т Беллу В общем виде формула обращения Мебиуса была впервые получена независимо друг от друга Л Вайснером и Ф Холлом Дж -К Рота показал важность теории обращения функций Мебиуса в современной комбинаторной математике в статье3, которая положила начало целому циклу работ, объединенных общим названием «Об основах комбинаторной теории» и состоящему из работ как самого Рота, так и его учеников и сотрудников
Частично упорядоченные множества обобщенных треугольников Паскаля изучались в частности Р Стенли Появление комбинаторного доказательства принципа включения-исключения позволило рассматривать задачи связанные с выражением комбинаторных чисел через определители, построенные из биномиальных коэффициентов Эти определители позволяют обращать комбинаторные числа, а также представлять комбинаторное число как вес множества перестановок особого вида В статье И Гессель и Г Вьенно4 опубликована первая явная формулировка теоремы, позволяющей, в частности, строить такие определители Но описанные выше построения частично упорядоченных множеств и определителей не возможны без геометрических интерпретаций Поэтому актуальной является проблема построения геометрических интерпретаций обобщенного треугольника Паскаля
Обращение Мебиуса является фундаментальным принципом перечисления и позволяет решать задачу обращения ряда комбинаторных сумм Вопросы обра-
3RotaG-C On the foundations of combinatorial theory I Theory of Mobius functions / G-C Rota//Z Wahrscheinlich-keitstheone and Verw Gebiete 1964 Vol 2 P 340-368
4 Gessel I, Viennot G Binomial determinants, paths, and hock length formulae 11 Gessel, G Viennot II Advances m Math. 1985 Vol 58 P 300-321
щения линейных выражений играют важную роль во многих разделах математики Множество пар обратимых соотношений с заданными матрицами коэффициентов в явном и неявном виде содержатся в работах X В Гульда, П Дубиле, Дж -К Рота и Р Стенли, Г П Егорычева, О В Кузьмина, А Нишиямы, М Л Платонова и В Н. Докина, Дж Риордана, С Таубера и др Это обуславливает актуальность проблемы построения и изучения новых пар обратимых соотношений с трехмерными матрицами коэффициентов
Некоторые пары обратимых соотношений проясняют структуру комбинаторных полиномов Понятие «полином разбиения» — полином от нескольких переменных, определяемый с помощью сумм по раличным разбиениям его индекса - введено Э Беллом М Л Платонов ввел В-полиномы, являющиеся обратными в аналитическом и алгебраическом смысле однородным полиномам Белла Комбинаторные полиномы и их обобщения изучаются в работах X В Гульда, В Д Жукова, О В Кузьмина, О В Леоновой, М Л Платонова, Б И Селиванова, Дж Тушара, М А Хомякова и др Комбинаторные В-полиномы могут быть связаны с разбиением множеств и перечислением помеченных корневых деревьев Подобные задачи рассматривали, в частности, X Гупт, Р Гримсон, Л Комтет, О В Кузьмин, Ю Л Павлов, М Л Платонов, Р Стенли, Т Г Тюрнева, Е Шредер, Ф Ховард Р Стенли5 привел решения четырех задач Шредера Ответ на четвертую задачу (число произвольных расстановок скобок в множестве) дает известное соотношение, которому удовлетворяет производящая функция чисел Шредера Sn Актуальным является нахождение перечислительной интерпретации В-полиномов и прямого комбинаторного решения четвертой задачи Шредера и ее обобщения
Комбинаторные полиномы широко применяются при моделировании дискретных вероятностных распределений и некоторых структур и процессов техники и естествознания Они могут быть применены при создании модели оценки и контроля уровня риска
3 Стенли Р Перечислительная комбинаторика Деревья, производящие функции и симметрические функции / Р Стенли М Мир, 2005 767 с
Основная цель работы состоит в исследовании комбинаторных чисел и полиномов, описываемых обобщенными пирамидами Паскаля, нахождения для них новых соотношений и перечислительных интерпретаций, в построении и изучении новых комбинаторных объектов
Методы исследований В диссертации используются методы комбинаторного анализа, теории вероятностей и компьютерного моделирования
Научная новизна Введены и изучены новые комбинаторные объекты, впервые рассмотрены вопросы обращения обобщенных пирамид Паскаля и построена комбинаторная интерпретация В-полиномов.
Основные результаты, выносимые на защиту
-
Построены частично упорядоченные множества и пары соответствующих обратимых соотношений, содержащих в качестве коэффициентов комбинаторные числа, описываемые обобщенной пирамидой Паскаля
-
Получен алгоритм построения геометрических интерпретаций широкого класса объектов, описываемых обобщенным треугольником Паскаля, что позволяет строить соответствующие им частично упорядоченные множества и выражать исследуемые комбинаторные числа через определители, построенные из биномиальных коэффициентов
-
Введены трехмерные обобщения ряда известных комбинаторных объектов, для них получены новые соотношения и перечислительные интерпретации
-
Предложен комбинаторный подход к решению четвертой задачи Шредера и ее обобщения, в результате чего найдена комбинаторная интерпретация В-полиномов
Личный вклад автора состоит в развитии теории комбинаторных чисел и полиномов, построении новых комбинаторных объектов и нахождении соотношений для ряда известных Все основные результаты, включенные в диссертацию, получены лично автором
Теоретическая и практическая значимость. Результаты, полученные в диссертации, могут использоваться в приложениях теории вероятностей при моделировании дискретных вероятностных распределений, а также для дальнейших ис-
следований комбинаторных полиномов разбиений и композиций и решения задач обращения комбинаторных объектов описываемых обобщенной пирамидой Паскаля Исследования, проводимые по теме диссертации, были поддержаны грантом Рособразования «Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов» (2005 г) Отдельные разделы диссертации используются в учебном процессе кафедры теории вероятностей и дискретной математики Иркутского государственного университета (чтение спецкурсов по комбинаторному анализу и комбинаторным методам в теории вероятностей)
Апробация работы Результаты работы были представлены на всероссийском научно-практическом молодежном симпозиуме «Экология Байкала и Прибайкалья» (Иркутск, ИГУ, 1999), ежегодных научно-теоретических конференциях молодых ученых (Иркутск, ИГУ, 2001, 2002), второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, ИГПУ, 2003), научно-практической конференции молодых ученых, посвященной 85-летию ИГУ (Иркутск, ИГУ, 2003), III и V международных научно-практических конференциях «Математическое моделирование в образовании, науке и производстве» (Тирасполь, ПриднГУ, 2003, 2007), VIII школе-семинаре молодых ученых «Математическое моделирование и информационные технологии» (Иркутск, ИДСТУ СО РАН, 2006), II Всероссийской конференции с международным участием «Информокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, БурГУ, 2006), Седьмом Всероссийском симпозиуме по прикладной и промышленной математике (Йошкар-Ола, 2006), IX международном семинаре «Дискретная математика и ее приложения», посвященном 75-летию со дня рождения академика О Б Лупанова (Москва, МГУ, 2007)
Кроме того, материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2002 - 2008)
Публикации По теме диссертации опубликовано 13 работ Основное содержание опубликовано в работах [1-9] В число указанных работ входит 1 статья
[1] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2007 г », 1 статья [2] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001-2006 гг», 2 статьи [3, 7] в научных сборниках, 5 полных текстов докладов [4-6, 8-9] в материалах международных и всероссийских конференций Публикации [1-7] выполнены в нераздельном соавторстве с научным руководителем
Структура и объем работы Диссертационная работа состоит из введения, трех глав, заключения и списка литературы из 112 наименований Общий объем диссертации - 110 страниц, включая 17 рисунков, 4 таблицы, 2 приложения
