Обобщенные пирамиды Паскаля и комбинаторные формулы обращения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Балагура Анна Александровна

ОБОБЩЕННЫЕ ПИРАМИДЫ ПАСКАЛЯ И КОМБИНАТОРНЫЕ ФОРМУЛЫ ОБРАЩЕНИЯ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск - 2008

11111111111!

□ОЗ1В5Б23

- _J

Работа выполнена в Иркутском государственном университете

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

Кузьмин Олег Викторович

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

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

кандидат технических наук Семенов Александр Анатольевич

Ведущая организация: Институт прикладных математических

исследований Карельского научного центра РАН

Защита состоится 21 марта 2008 г. в 14-00 часов на заседании диссертационного совета Д.212.074.01 при Иркутском государственном университете по адресу: 664003, г. Иркутск, ул. К. Маркса, 1, ИМЭИ ИГУ.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).

Автореферат разослан 2Сфевраля 2008 года.

Ученый секретарь диссертационного совета, канд. физ.-мат. наук, доцент

В.Г. Антоник

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

Актуальность темы Со второй половины XX века наблюдается интенсивное развитие комбинаторики - одной из основных частей современной дискретной математики Важная, но не единственная, роль в этом принадлежит изменению статуса дискретной математики в связи с развитием информационных технологий и возрастанием возможностей дискретных методов исследования Внутренние причины изменений в комбинаторике связаны с объединением и согласованием ее разделов и проникновением идей комбинаторного анализа в смежные разделы математики и другие области науки Одно из перспективных направлений исследований - комбинаторика на частично упорядоченных множествах

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

Комбинаторные числа и различные способы их классификации известны давно Наряду с общими подходами к построению комбинаторных чисел, берущих свое начало в работах Р А Мак-Магона и А Кэли, можно отметить теорию перечисления Дж Пойа и Дж Г Редфилда М Л Платонов предложил и разработал общую схему построения комбинаторных чисел класса отображений1, по построению близкую к схеме Пойа Достаточно общий подход к изучению и построению комбинаторных объектов, основанный на анализе свойств обобщенной пирамиды Паскаля, был разработан О В Кузьминым сравнительно недавно2

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

1 Платонов М Л Комбинаторные числа класса отображений и их приложения /МЛ Платонов М Наука, 1979 152 с

2 Кузьмин О В Обобщенные пирамиды Паскаля и их приложения / О В Кузьмин Новосибирск Наука. Сибирская издательская фирма РАН, 2000 294 с

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

Изучение решеток и частично упорядоченных множеств имеет свое начало в работах Г Буля, Ч С Пирса, Е Шредера и Р Дедекинда Развитие этой теории началось в 1930-х годах с работ Г Биркгофа Идея алгебр инцидентности восходит к Р Дедекинду и Е Т Беллу В общем виде формула обращения Мебиуса была впервые получена независимо друг от друга JI Вайснером и Ф Холлом Дж -К Рота показал важность теории обращения функций Мебиуса в современной комбинаторной математике в статье3, которая положила начало целому циклу работ, объединенных общим названием «Об основах комбинаторной теории» и состоящему из работ как самого Рота, так и его учеников и сотрудников

Частично упорядоченные множества обобщенных треугольников Паскаля изучались в частности Р Стенли Появление комбинаторного доказательства принципа включения-исключения позволило рассматривать задачи связанные с выражением комбинаторных чисел через определители, построенные из биномиальных коэффициентов Эти определители позволяют обращать комбинаторные числа, а также представлять комбинаторное число как вес множества перестановок особого вида В статье И Гессель и Г Вьенно4 опубликована первая явная формулировка теоремы, позволяющей, в частности, строить такие определители Но описанные выше построения частично упорядоченных множеств и определителей не возможны без геометрических интерпретаций Поэтому актуальной является проблема построения геометрических интерпретаций обобщенного треугольника Паскаля

Обращение Мебиуса является фундаментальным принципом перечисления и позволяет решать задачу обращения ряда комбинаторных сумм Вопросы обра-

3RotaG-C On the foundations of combinatorial theory I Theory of Möbius functions/ G-C Rota//Z Wahrscheinlichkeitstheorie and Verw Gebiete 1964 Vol 2 P 340-368

4 Gessel I, Viennot G Binomial determinants, paths, and hock length formulae /1 Gessel, G Viennot // Advances m Math. 1985 Vol 58 P 300-321 4

щения линейных выражений играют важную роль во многих разделах математики Множество пар обратимых соотношений с заданными матрицами коэффициентов в явном и неявном виде содержатся в работах X В Гульда, П Дубиле, Дж -К Рота и Р Стенли, Г П Егорычева, О В Кузьмина, А Нишиямы, М Л Платонова и В Н. Докина, Дж Риордана, С Таубера и др Это обуславливает актуальность проблемы построения и изучения новых пар обратимых соотношений с трехмерными матрицами коэффициентов

Некоторые пары обратимых соотношений проясняют структуру комбинаторных полиномов Понятие «полином разбиения» — полином от нескольких переменных, определяемый с помощью сумм по раличным разбиениям его индекса - введено Э Беллом М Л Платонов ввел В-полиномы, являющиеся обратными в аналитическом и алгебраическом смысле однородным полиномам Белла Комбинаторные полиномы и их обобщения изучаются в работах X В Гульда, В Д Жукова, О В Кузьмина, О В Леоновой, М Л Платонова, Б И Селиванова, Дж Тушара, М А Хомякова и др Комбинаторные В-полиномы могут быть связаны с разбиением множеств и перечислением помеченных корневых деревьев Подобные задачи рассматривали, в частности, X Гупт, Р Гримсон, Л Комтет, О В Кузьмин, Ю Л Павлов, М Л Платонов, Р Стенли, Т Г Тюрнева, Е Шредер, Ф Ховард Р Стенли5 привел решения четырех задач Шредера Ответ на четвертую задачу (число произвольных расстановок скобок в множестве) дает известное соотношение, которому удовлетворяет производящая функция чисел Шредера 8п Актуальным является нахождение перечислительной интерпретации В-полиномов и прямого комбинаторного решения четвертой задачи Шредера и ее обобщения

Комбинаторные полиномы широко применяются при моделировании дискретных вероятностных распределений и некоторых структур и процессов техники и естествознания Они могут быть применены при создании модели оценки и контроля уровня риска

5 Стенли Р Перечислительная комбинаторика Деревья, производящие функции и симметрические функции / Р Стенли М Мир, 2005 767 с

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

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

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

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

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

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

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

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

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

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

следований комбинаторных полиномов разбиений и композиций и решения задач обращения комбинаторных объектов описываемых обобщенной пирамидой Паскаля Исследования, проводимые по теме диссертации, были поддержаны грантом Рособразования «Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов» (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 приложения

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

Основным результатом первой главы является алгоритмическая схема построения геометрических интерпретаций достаточно широкого класса объектов, описываемых обобщенным треугольником Паскаля, которая позволяет строить соответствующие им частично упорядоченные множества и выражать их через определители, построенные из биномиальных коэффициентов Такие построения проведены для чисел Фибоначчи, Каталана, Пелля и др В связи со спецификой и некоторой обособленностью теории частично упорядоченных множеств возникает необходимость привести определения и результаты, применяемые в настоящей работе Этому посвящен параграф 1 1 Остальные параграфы посвящены исследованию свойств ряда комбинаторных объектов, описываемых обобщенным треугольником Паскаля В параграфе 1 2 рассматривается перечисление решеточных путей с ограничениями на шаги Построены геометрические интерпретации изучаемых комбинаторных объектов

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

У(п,к) = апк_У(п-\,к-\) + p„j,V(n-\,k) (1 1)

с граничными условиями F(0,0) = Fo, V(n, К)= 0, если тт(п, к, п-к)<0

Конечным неотрицательным решеточным путем L в пространстве Е2 называют последовательность L = (v,, ,vt), где vt (x^yje N02, l<t<k, N„={0,1,2, }, g

v,+i-v, =(xl+i~x„yl+1-y,)e{(l,0), (0,-1)} Пусть a = {ai,a2),b = {bl,b2), тогда L называют решеточным путем типа [а, Ь\, если он проходит от а к Ъ

Следуя идее Р Стенли, рассматриваем не все возможные пути на решетке, а только те, которые не проходят через определенное множество «запрещенных» точек плоскости Пусть числа ipn определяются рекуррентной формулой

<Р„+г=К <Рп, (12)

где <г>,Д,Д2 eN

Определим операцию сдвига точки М(х, у) на вектор N(ax,ay) • M®N = (х+ах,у + ау) Сдвиг множества — сдвиг всех его точек

Обозначим \ап, 6J - тип решеточных путей ап = (О, FJ, Ьп = (Х„,0) X„=X(n,k1,k0,<p0,<pl), Yn = Y{n,k\,k,^(p,3,(p}), Z„ =Z(h, - множество запре-

щенных точек Путь, проходящий хотя бы через одну точку из множества 7-п, назовем запрещенным, все остальные — допустимыми

Пусть Л[а„, 6J - множество всех допустимых решеточных путей типа [ап, Ь„] при заданном Z„, А = А(п, <-/>„, q>t) - множество начальных точек, В = В(кх,к2),С = С(к,, к2), D = D(k,,к2), F = F(k,, к2) - множества основных точек, о- = (с-,, сг2), а-, = <у, (п, <р0, <z>,), i = 1,2 - вектор сдвига по начальным точкам, 8 = {8и82), б, =6,(kt,k2),i = 1,2- вектор сдвига основных точек, Н ={а1,а2,а„а4), а, = а, (я), г = 1,2,3,4 — множество коэффициентов сдвига основных точек Построено правило 1.1 нахождения А, В, С, D, F, Н, 5, <х

Алгоритм 1.1

Вход алгоритма соотношение (1 2) и начальные условия <рй, q>x Шаг 1 Строим А, В, С, D, F, Н, а, 8 по правилу 1 1 Шаг 2 Находим числа Xn,Yn по правилу 1 1

Шаг 3 Строим множество запрещенных точек Zn = {А, В®а®8, , В®сг®а18, С®<т®8, , С®<т®аг8, D®cr®8, , D®cr®a3S, F®cr®S, F®cr®a48 }

Выход алгоритма a„,bn, Z„

Теорема 1.5. Пусть п ¿2, \ап, Ьп] и 7.п построены в соответствии с алгоритмом 1 1, тогда |Л[а„,6„]| = <рп

В параграфе 1 3 при помощи геометрических интерпретаций полученных по алгоритму 1 1 построены выражения для ряда комбинаторных чисел через определители из биномиальных коэффициентов В параграфе 1 4 для исследования комбинаторных чисел используются свойства функции частично упорядоченного множества, определяющей число расширений частично упорядоченного множества до полной (линейной) упорядоченности Полученные в параграфе 1 2 геометрические интерпретации позволяют строить для исследуемых объектов частично упорядоченные множества Р„, такие, что число расширений до полной упорядоченности е{Рп) задается обобщенным треугольником Паскаля, а также находить С(Рп) - множество Жордана-Гельдера этих частично упорядоченных множеств Основные результаты главы опубликованы в работах [4, 6] Вторая глава посвящена изучению комбинаторных объектов, описываемыми обобщенными пирамидами Паскаля Рассматриваются вопросы обращения, строятся частично упорядоченные множества, соответствующие решаемой задаче, вводятся новые комбинаторные объекты Показывается их связь с характеристическим многочленом и рангово-производящей функцией

В параграфе 2 1 приводится общая схема построения комбинаторных объектов на основе обобщенной пирамиды Паскаля

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

У{п,кЛ) = апк_иУ{п-\,к-\,1) +р»к1_у{п-\,к,1-Х) + упк1у{п-\к,1), (2 1)

с граничными условиями К(0,0,0) = У0, У(п, к, /) = 0, если тт(п, к, I, п-к-1)<О

Рассматриваются важные частные случаи — А- и Ъ-пирамиды, образованные обобщенными триномиальными коэффициентами первого и второго рода

Пусть а={а: у%0, /?={Д }'10, у ={у, }"(| — базовые последовательности, или базы Положим У0 = 1 При ап , =«„_,, рпкм = /?„_,, У„к1=Г„-1, п>\, 0<к< п, О<1<,п-к имеем У(п, 4,1) = В", и из соотношения (2 1) следует рекуррентная 10

формула ВЦ, =аг„_, В"^, + +у„_1 ВЦ' , определяющая обобщенные триномиаль-

ные коэффициенты первого рода

При ая1_и =а1_1, Р„к= Рк, Г„,к1=П, «>1, 0<к <п, 0<1<п-к, имеем V(п, к, I) = А", , а из соотношения (2 1) следует рекуррентная формула Ак1 =ак-1Ак-и +РкАк~1-\ > определяющая обобщенные триномиальные коэф-

фициенты второго рода

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

Для фиксированного т>2 обозначим а' = а'(т) = {аа, ,ат_2), Р' = Р'(т) = {ро, / = /(гп) = {уа, ,/,„_,}, а" = а"(т) = {аХ„ /Г = /Г(/я) = {А}1,

У' Г"(т) = {уX,, а = а(т) = {а0, ,<*„_,}

Теорема 2.1. Для А£г и ВР9Г построенных на базах а,р,у, А?г - на базах а',

Р', у', В*г - на базах се, р', у', А?г и В?г- на базах а", р", у" верны

1 » _ —

соотношения А,Л"/--' гДе п,т> 2, к> О, 2<т + к <п,

1=0 }=т к I _ ^

0<1<п-т-к, Щ-п-! , где п,т>\, 0<к<т + п, 0<1 <п+т-к

В параграфе 2 2 рассматриваются взаимообратные соотношения, возникающие при обращении комбинаторных объектов, описываемых обобщенной пирамидой Паскаля

Пусть {^Хо, {/Х=о> №Х=о, о - последовательности Парой обратимых соотношений называют систему линейных соотношений

6 Платонов М Л Соотношения между обобщенными числами Стирлинга, построенными на разных базах / МЛ Платонов//Комбинаторный и асимптотический анализ Красноярск Краснояр ун-т, 1977 С 142-152

к л»

4 (2 2)

к

если матрицы коэффициентов Цо^Ц и - двусторонние взаимообратные Систему линейных соотношений

Ф„=2Х

к

к

называют союзной парой обратимых соотношений к паре (2 2)

я—1

Пусть С„ (а) = ]"[«,, аналогично определяются Са (р) и С „(у) Положим 1=0

Iп , базы 5, £, | определяются аналогично

Пусть Д, строятся на базах а, £, £, Д', - на базах р, Д", - на базах Г, £, ?, КЯо{£Х=о> - последовательности

Теорема 2.3 Система линейных выражений

^ л п~к

¿=0 /=0 I и 1 И-^

^=XЛ/ ^

ЦЛ°\) к=0 1=0

образует пару обратимых соотношений

Теорема 2.4 Система линейных выражений

С„(/?)£ь*=о

:£2Х х„

| п п-1

*"п\Р) '=0 *=0

образует пару обратимых соотношений

Теорема 2.5 Система линейных выражений

^ДЛ/ т=0 4=0

<-Д7'/»>=о *=о

образует пару обратимых соотношений 12

Построены союзные пары обратимых соотношений к системам в теоремах 2 3-2 5

В параграфе 2 3 введены новые комбинаторные объекты - трехмерные обобщенные числа Стерлинга, Уитни и Лаха

Числа, задаваемые рекуррентными соотношениями

К, = -Гп<J, Щ = +пЖ;\

и > 1, О<к<п, 0</<п-к, с начальными условиями w°0 = Щ"„ = 1, w"kJ = Wkl = 0, если п-к-1< 0, назовем обобщенными трехмерными числами Уитни первого wh и второго W", рода соответственно

Числа, задаваемые рекуррентными соотношениями

К, = CL-(и-iKi-(п-1К1\ s;, =s& +к8гь +kS"k-\

п> 1, 0<к<п, 0<1< п-к, с начальными условиями s("n = S£0 = 1, sk! = Sk, =0, если п-к-1<0, назовем обобщенными трехмерными числами Стирлинга первого snk, и второго Sh рода соответственно

Числа, задаваемые рекуррентным соотношением

Ц, +(&-> +ЮЦ м +(r„-, +n)LTj, п> 1, 0<к<п, 0<1<,п-к, с начальными условиями 0 = 1, L"kl=0, если п-к~1<0, назовем обобщенными трехмерными числами Лаха

Для этих чисел получены пары обратимых соотношений и показана связь с обычными числами Стерлинга, Уитни, Лаха

В параграфе 2 4 построены частично упорядоченные множества, на которых обращение линейных соотношений содержащих Вк, осуществляется, используя

функцию Мебиуса Получены утверждения, аналогичные теоремам 2 3-25

Пусть Д, конечное множество, элементы которого - веще-

ственные числа Рассмотрим множество G„ всех возможных различных произведений элементов из множества Д,. На множестве G„ вводим отношение частичного порядка, считая, что для x,yeGn х<у, если множество всех множителей у содержит множество всех множителей х Пусть п(х)— число элементов

й +у ft -f-v R -f-v

1<г£и-1, в произведении х Пусть х = ——-——- —^——, 211 ~ строятся

на базах НО) = %, v{k) = 1 <к<п(х)

Предложение 2.1. Для V* е Gn соотношения

1 П(х) п(х)-к 1 п(х) п(ху-к ( г/ \

§ ^ S

следуют друг из друга

Основные результаты главы опубликованы в работах [1-3, 5, 7-9] Глава 3 посвящена исследованию свойств комбинаторных полиномов и их приложениям В параграфе 3 1 вводятся новые комбинаторные объекты — обобщенные расщепленные числа Шредера Рассматриваются некоторые вопросы перечисления деревьев Получены комбинаторные решения четвертой задачи Шредера и ее обобщения

В работах М Л Платонова, О В Кузьмина, Т Г Тюрневой получен явный вид обобщенных (а при к = 1 обычных) чисел Шредера

I (2иТ^"Д'^'Ш'оот1, I {2n-2-riyY\wwT\

2я-24 п-к УК ~ 1) ,=2 2л—2 и-1 ;=2

где п>2,\<к<п-\, а суммирование ведется по всем разбиениям (2п-2к) на (п-к) слагаемых и (2п-2) на (и-1) слагаемых соответственно

Пусть дано «-множество X Для п> 2 разобьем X по крайней мере на два блока Затем разобьем каждый блок, состоящий из более чем одного элемента, по крайней мере на два блока Продолжая разбивать блоки, содержащие хотя бы два элемента, на не менее чем два блока, добьемся того, чтобы каждый блок состоял из одного элемента Эту процедуру называют полным разбиением множествах

Корневое дерево можно определить рекурсивно следующим образом Корневое дерево d есть такое множество вершин, что одна специально выбранная вершина называется корнем корневого дерева d, и оставшиеся вершины (исключая корень) разбиты на т > О непересекающихся непустых множеств, каждое из которых является корневым деревом Вершины, не имеющие приемников, называются висячими или концевыми вершинами Вершины, имеющие приемников,

называют внутренними вершинами Пусть п> 2, 2<к<п Обозначим D(n) - множество помеченных корневых деревьев, имеющих в точности п концевых вершин, у которых из каждой внутренней вершины, считая и корень, исходит не менее двух вершин, D{n,k)~ множество корневых помеченных деревьев, имеющих в точности п концевых вершин и к приемников корня, у которых из каждой внутренней вершины, считая и корень, исходит не менее двух вершин. Полное разбиение может быть естественным образом представлено в виде помеченного корневого дерева

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

Теорема 3.1. Справедливы следующие утверждения \D{ri)\=SnlU\D{n,k)\ = Snk

Обозначим n = {1,2, , п} Из теоремы 3 1 следует Алгоритм 3.1 построения по разбиению (2п - 2 к) на (и - к) слагаемых полного разбиения множества п, обладающих тем свойством, что если 2<к<п-\, то полное разбиение множества п содержит к внешних подмножеств разбиения Обратный ему Алгоритм 3.2 для случая бинарных деревьев имеется в работе Р Стенли О В Кузьминым и Т Г Тюрневой введены расщепленные числа Шредера второго рода Кпт, которые определяют число корневых деревьев по параметру т - количеству всех внутренних вершин дерева Den висячими вершинами В данном параграфе введены обобщения этих чисел Число Кптк определяет число корневых деревьев по параметрам т - количеству всех внутренних вершин и к - количеству приемников корня дерева Den висячими вершинами Числа Кптк назовем расщепленными обобщенными числами Шредера

В качестве следствий из теоремы 3 1 получены следующие утверждения Следствие ЪЛ.Для чисел справедливо разложение

к>2

пг= О

Следствие 3.2. Для чисел Кпт справедливо соотношение

2и—2,л—1 (=2

где п> 2, т<п-2, а суммирование ведется по всем таким разбиениям (2п-2) на (и-1) слагаемых, у которых гх=п-2~т

Следствие 3.3. Для чисел Кптк справедливо соотношение

= I -гг,

2п-2к„-к (Л- Ч ,=2

где 2<к<п, т<,п-к, а суммирование ведется по всем таким разбиениям (2п-2к) на (п-к) слагаемых, у которых гх=п-к—т

В параграфе 3 2 строится комбинаторная интерпретация А- и В- полиномов, для которых известен явный вид

л-к+1

4.*Сг) = "'Е Пв: [г,'(»')" Г1, п ;> 1,1 £ к < П,

пк 1=1

л-Лг+1

в„л(в) = (-1 у-*[(к- г1 XНУ г,1X (2п— к —г, -1)1 Ц§; [г,I(¿у- ]-',

2п-2к п-к 1=1

п> 2, \<,к<п-\ Дополнительно полагают Впп= , п> 1.

Введем на п весовую функцию, положив g¡ - вес блока длины I, вес разбиения произведение весов его блоков, вес множества сумма весов его элементов Эта весовая функция может быть естественным образом продолжена на П„ gr -вес цикла длины г Пусть

Предложение 3.3. Вес подмножества элементов множества Пп, имеющих ранг (п-к) есть А„ к (%) Вес всех разбиений множества п на к блоков есть А„к^)

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

Каждому дереву из D(n,k) сопоставим перестановку я е Пп по следующему правилу 3.1 Пусть (р\, ,p'j), \<i<n,\< j <n-l — последовательность всех концевых вершин дерева, у которых первым предком после корня является i-й приемник корня (2<у<«-1) или эта вершина сама является г-м приемником корня

к

0 =1) Тогда я = (р\, ,р\) (р\, , р",t), где = п

т=1

Для к> 2 дерево назовем к- проектируемым, если сопоставленная ему по правилу 3 1 перестановка ж имеет в точности к циклов Пусть gl ф 0 Введем на D(n,k)~ весовую функцию, полагая g, g¡~[, i>2, — вес вершины дерева, имеющей

1 приемников, g,"1 — вес вершины дерева, не имеющей приемников

Вес дерева считаем равным произведению весов всех его вершин кроме корня, а вес множества деревьев - сумме весов всех составляющих его элементов Каждому дереву из D(n) сопоставим перестановку ж е Пп по следующему правилу 3.2 Пусть (p¡, , pj - последовательность всех концевых вершин дерева, записанных в порядке появления Тогда перестановку я ~ (/?,, , рп) назовем 1-проекцией дерева Пусть g, # 0 Введем на D(n) весовую функцию, считая, что g, gf1, i > 2, - вес вершины дерева и корня, имеющих i приемников, gf1 - вес вершины дерева, не имеющей приемников

Вес дерева считаем равным произведению весов всех его вершин и корня, а вес множества деревьев — сумме весов всех составляющих его элементов Найдена новая интерпретация В-полиномов, которая дает Теорема 3.2. Для п, k е N, п> 2 суммарный вес всех различных к-проектируемых п-деревьев равен В„k(g) Суммарный вес всех п-деревьев,

имеющих различные l-проекции, равен (~l)"~] Bnl(g)

В параграфе 3 3 комбинаторные полиномы композиций применяются для построения дискретной модели оценки и контроля уровня риска В монографии7 комбинаторные методы применяются для моделирования дискретных вероятно-

7 Комбинаторные числа и полиномы в моделях дискретных распределений / В Н Докин, В Д Жуков, Н А Коло-кольникова и др Иркутск Изд-во Иркут ун-та, 1990 208 с

стных распределений В монографии2 строятся и исследуются модели некоторых структур и процессов техники и естествознания Следуя этим идеям, могут быть разработаны модели оценки и контроля уровня риска В данном параграфе предложена модель оценки кредитного риска

Основные результаты главы опубликованы в [2]

Публикации по теме диссертации

1. Балагура А А Обобщенные пирамиды Паскаля и им обратные / А А Балагура, О.В Кузьмин//Дискретная математика -2007 -Т 19, вып 4 - С 108-116

2. Балагура А А. Обобщенная пирамида Паскаля и частично упорядоченные множества / А А Балагура, О В Кузьмин // Обозрение прикладной и промышленной математики -2007 —Т. 14, вып 1 —С 88-91

3 Балагура А А Частично упорядоченные множества и некоторые комбинаторные объекты / А А Балагура, О В Кузьмин // Комбинаторные и вероятностные задачи дискретной математики -Иркутск Изд-воИркут ун-та, 2006 - С 18-32

4 Балагура А А О взвешенных траекториях на решетках с особенностями / О В Кузьмин, А А Балагура // Математическое моделирование в образовании, науке и производстве Материалы III междунар науч -практ конф - Тирасполь РИО ПТУ, 2003 -С 257-259

5 Балагура А А Обобщенные пирамиды Паскаля и им обратные / О В Кузьмин, А А. Балагура // Материалы IX Международного семинара «Дискретная математика и ее приложения», посвященного 75-летию со дня рождения академика О Б Лупанова - М • Изд-во мех -мат ф-та МГУ, 2007 - С 222-225

6 Балагура А А Траектории на решетках с особенностями / О В Кузьмин, А А Балагура // Труды Второй Восточно-сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе - Иркутск Изд-во Иркут пед ун-та, 2003. - С 139-140

7 Балагура А А О некоторых свойствах специальных матриц / А А Балагура, О В Кузьмин // Вестник Иркутского университета Специальный выпуск — Иркутск Изд-воИркут ун-та,2003 -С 70-71

8. Балагура А.А Частично упорядоченные множества и комбинаторные объекты / A.A. Балагура // Инфокоммуникационные и вычислительные технологии и системы: Материалы II Всерос. конф. — Улан-Удэ: Изд-во Бурят, ун-та, 2006. -Т.2.-С. 34-37.

9. Балагура A.A. Применение частично упорядоченных множеств для исследования комбинаторных объектов / A.A. Балагура // Математическое моделирование и информационные технологии: управление, искусственный интеллект, прикладное программное обеспечение и технологии программирования: Материалы VIII школы-семинара молодых ученых / Ин-т динамики систем и теории управления СО РАН. - Иркутск, 2006. - С. 19-22.

Подписано к печати 15.02.2008. Формат 60x84 1/16 Усл. печ. л. 1,0. Заказ 35. Тираж 100 экз.

Издательство Иркутского государственного университета 664003, Иркутск, бульвар Гагарина, 36

Введение

Глава 1. Обобщенные треугольники Паскаля и частично упорядоченные множества

1.1. Частично упорядоченные множества

1.2. Геометрические интерпретации обобщенных треугольников Паскаля

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

1.4. Частично упорядоченные множества обобщенных треугольников Паскаля

Глава 2. Обобщенные пирамиды Паскаля и им обратные

2.1. Обобщенные триномиальные коэффициенты первого и второго рода

2.2. Обращение А- и В-пирамид

2.3. Трехмерные обобщенные числа Стерлинга, Уитни,

2.4. Обращение типа Мебиуса

Глава 3. Комбинаторные полиномы и их приложения

3.1. Перечисление помеченных корневых деревьев

3.2. Комбинаторное построение А- и В-полиномов

3.3. Комбинаторные полиномы в модели управления рисками

Актуальность темы. Со второй половины XX века наблюдается-интенсивное развитие комбинаторики — одной из основных частей современной дискретной математики [1, 19, 48, 51, 54]. Важная, но не единственная, роль в этом принадлежит изменению статуса дискретной математики в связи с развитием информационных технологий и возрастанием возможностей дискретных методов исследования [55]. Внутренние причины изменений в комбинаторике связаны с объединением^ , ц согласованием ее разделов и проникновением идей комбинаторного анализа в смежные разделы математики и другие области науки [23, 38, 49, 50]. Одно из перспективных направлений исследований -комбинаторика на частично упорядоченных множествах [49].

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

Комбинаторные числа и различные способы их классификации известны давно. Наряду с общими подходами к построению комбинаторных чисел, берущих свое начало в работах P.A. Мак-Магона и А. Кэли, можно отметить теорию перечисления Дж. Пойа [6, 45] и Дж. Г. Редфилда [46]. M.JI. Платонов [38] предложил и разработал общую схему построения комбинаторных чисел класса-отображений, по построению близкую к схеме Пойа. Достаточно общий подход к изучению и построению комбинаторных объектов, основанный на анализе свойств обобщенной пирамиды Паскаля, был разработан 0;В. Кузьминым сравнительно недавно [23].

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

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

Изучение решеток и частично упорядоченных множеств имеет свое начало в работах Г. Буля, Ч.С. Пирса, Е. Шредера и Р. Дедекинда. Развитие этой теории началось в 1930-х годах с работ Г. Биркгофа (см. например, библиографию в [4]). Идея алгебр инцидентности восходит к Р. Дедекинду и Е.Т. Беллу. В общем виде формула обращения Мебиуса была впервые получена независимо друг от друга Л. Вайснером и Ф. Холлом. Дж.-К. Рота в [92] показал важность теории обращения функций Мебиуса в современной комбинаторной математике. Одним из наиболее полезных методов перечисления в дискретных задачах теории вероятностей и комбинаторного анализа является принцип включения-исключения. Идея этого метода встречается в работах нескольких математиков XIX века, но, по-видимому, наиболее ясно была сформулирована А. Пуанкаре. Следует отметить, что на практике не всегда легко заметить возможность применения данного метода. Часто множество перечисляемых объектов обладает некоторым естественным порядком (в общем случае частичным). Вместо того, чтобы вводить, на таком множестве линейный порядок, во многих случаях бывает полезнее применить технику, учитывающую его естественный (комбинаторный) порядок. Данный подход позволяет решить задачу обращения некоторых комбинаторных сумм. Такое обращение можно выполнить, определив функцию Мебиуса для частично упорядоченного множества. Статья Рота положила начало целому циклу работ, объединенных общим названием «Об основах комбинаторной теории» [3, И] и состоящему из работ как самого Рота, так и его учеников и сотрудников. О значении обращения Мебиуса в комбинаторной математике сказано очень много последователями и учениками Рота, а также российскими математиками [7].

Частично упорядоченные множества обобщенных треугольников Паскаля изучались в частности Р. Стенли [49, 95], им было сформулировано определение 4 обобщенного треугольника Паскаля в терминах частично упорядоченных множеств. Также, им было показано, что некоторые задачи о решеточных путях эквивалентны определению числа е(Р) для некоторого частично упорядоченного множества Р. Многие перечислительные задачи могут быть выражены в терминах решеточных путей. Пути на решетках, связанные с числами Фибоначчи и Люка рассматривались в [66]. Решетки, связанные с числами Фибоначчи, изучались в

49, 96]. Семейства чисел Каталана, Моцкина, Шредера их свойства и некоторые обобщения, связанные, в частности, с путями на решетках, рассматриваются. [30;

31, 61, 63, 71, 75, 82, 83, 85, 87, 88, 93, 97]. Ряд комбинаторных тождеств получен в [76, 77, 81, 90] путем подсчета решеточных путей на плоскости при некоторых ограничениях. В работах [8, 68] аппарат функциональных цепных дробей использован для построения общей схемы перечисления- помеченных путей наплоской целочисленной решетке. Взвешенные пути в двумерных и многомерных решетках и их комбинаторные приложения изучаются в [22, 56, 58, 59, 64, 65, 78].

Некоторые решеточные интерпретации комбинаторных объектов' позволяют выражать комбинаторные числа через определители, построенные из*. биномиальных коэффициентов. Такие определители позволяют обращать комбинаторные числа, а также представлять комбинаторное число как вес множества перестановок особого вида. Подобные задачи, в частности, рассматривались с появлением комбинаторного доказательства принципа включения-исключения [60, 74, 80]. В статье [65] опубликована первая явная' формулировка теоремы, позволяющей, строить такие определители. Существует много способов построения матриц и определителей, составленных из биномиальных, обобщенных биномиальных и триномиальных коэффициентов, чисел Фибоначчи, Люка, Каталана и других специальных чисел. Такие задачи связаны с решением конкретных систем алгебраических и разностных уравненийи обладают интересными свойствами. В монографии [5] содержится библиография по этой теме. В [16] осуществляется построение комбинаторного определителя, который в развернутом виде представляет многочлен с коэффициентами, описывающими комбинаторные распределения на множестве 5 подстановок. Но описанные выше построения частично упорядоченных множества и определителей не возможны без геометрических: интерпретаций. Поэтому актуальной является проблема построения геометрических интерпретаций? обобщенного треугольника Паскаля.

Обращение Мебиуса является фундаментальным принципом перечисления и позволяет решать задачу обращения ряда комбинаторных сумм. Вопросы, обращения- линейных выражений играют важную роль, во многих разделах, математики. В; математическом анализе это интегральные преобразования, в алгебре - обращение матриц, в теории чисел и комбинаторике - многочисленные-пары обратимых соотношений. В публикациях [12-15, 67, 86] описаны многочисленные пары обратимых соотношений; содержится: некоторый опыт их классификации. Но в этих работах, как правило, изучались суммы,: с биномиальными коэффициентами. В работах [38, 84, 98, 99] содержится; множество; тождеств и обратимых соотношений не только для биномиальных, коэффициентов, но и для чисел Каталана, Фибоначчи, Стирлинга и других. В: основном это объекты, описываемые обобщенным треугольником Паскаля. Платоновым и В.Н. Докиным были построены формулы обращения для достаточно широких классов комбинаторных объектов [37-39, 43]. В частности, в-[43] рассматривались различные варианты обращения линейных соотношений, в которых в качестве коэффициентов употребляются обобщенные числа Стирлинга и Лаха. Множество пар обратимых соотношений в явном и неявном; виде содержатся- в [11, 18, 24, 53, 92]. Это обуславливает актуальность проблемы построения и изучения новых пар обратимых соотношений; с трехмерными матрицами коэффициентов.

Некоторые пары обратимых соотношений: проясняют структуру комбинаторных полиномов. . Понятие «полином разбиения» - полином: от нескольких переменных, определяемый с помощью сумм по раличным разбиениям его индекса - введено Беллом в [57]. Один из таких полиномов; возникающий при получении явного вида производной от композиции функции формулы де Бруно, Риордан назвал полиномом Белла (см. перевод [47]). Платонов б в [40] ввел полиномы, являющиеся обратными в аналитическом и алгебраическом смысле однородным полиномам Белла. Эти объекты в работё [20] названы полиномами Платонова. Они и ряд обобщений А- и В- полиномов изучаются- в работах [8, 10, 21, 28, 29, 52, 67] и др.

Комбинаторные В-полиномы могут быть связаны с разбиением множеству перечислением помеченных корневых деревьев. Подобные задачи рассматриваются, в частности, в работах [17, 30, 31, 35, 36, 37, 41, 50, 62, 69-^71, 73, 94]. Р.Стенли привел решения четырех задач Шредера. Ответ на четвертую-задачу (число произвольных расстановок, скобок в множестве) дает известное соотношение, которому удовлетворяет производящая функция чисел Шредера-, £„[62]. Актуальным является нахождение перечислительной интерпретации- Вполиномов и прямого комбинаторного решения четвертой задачи Шредера- и ее обобщения.

Комбинаторные полиномы широко применяются при моделировании дискретных вероятностных распределений и некоторых структур и процессов-техники и естествознания. Они могут быть применены при создании модели оценки и контроля уровня риска.

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы были представлены на: всероссийском научно-практическом молодежном симпозиуме «Экология Байкала и Прибайкалья» (Иркутск, ИГУ, 1999); ежегодных научно-теоретических конференциях молодых ученых (Иркутск, ИГУ, 2001, 2002); второй ВосточноСибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе (Иркутск, ИГПУ, 2003); научно-практической конференции молодых ученых, посвященной 85-летию ИГУ (Иркутск, ИГУ, 2003); ИГ и V международных научно-практических конференциях «Математическое* моделирование в образовании, науке и производстве» (Тирасполь, ПриднГУ, 2003, 2007); VIII школе-семинаре молодых ученых «Математическое моделирование и информационные технологии» (Иркутск, ИДСТУ СО РАН; 2006); II Всероссийской конференции с международным участием-«Информокоммуникационные и вычислительные технологии и системы» (Улан-Удэ, БурГУ, 2006); Седьмом Всероссийском симпозиуме по прикладной w промышленной математике (Йошкар-Ола, 2006); IX международном семинаре «Дискретная математика и ее приложения», посвященном 75-летию со дня-рождения академика О.Б. Лупанова (Москва, МГУ, 2007).

Кроме того, материалы диссертации докладывались и обсуждались на*, семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2002 - 2008).

Публикации. По теме диссертации опубликовано 13 работ. В число указанных работ входит 1 статья [100] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2007 г.», 1 статья [101] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001-2006 гг.», 4 статьи [104, 108110] в научных сборниках, 7 полных текстов докладов [103, 105-107, 111-113] в материалах международных и всероссийских конференций. Публикации [100-109] выполнены в нераздельном соавторстве с научным руководителем.

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

Заключение

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

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

1. Айгнер М. Комбинаторная теория / М. Айгнер. М.: Мир, 1982. - 558 с.

2. Альбертьян М.К. Отображения частично упорядоченных множеств и обобщенные числа Стерлинга / М.К. Альбертьян // Сб. тр. ВНИИ систем, исслед.- 1982.-№ 10.-С. 142-145.

3. Бендер Э., Гольдман Дж. О приложения обращения Мебиуса в комбинаторном анализе / Э. Бендер, Дж. Гольдман // Перечислительные задачи комбинаторного анализа. М.: Мир, 1979. - С. 311-336.

4. Биркгоф Г. Теория решеток / Г. Биркгоф. М.: Наука, 1984. - 568 с.

5. Бондаренко Б.А. Обобщенные треугольники и пирамиды Паскаля, их фракталы, графы и приложения / Б.А. Бондаренко Ташкент: Фан, 1990. — 192с.

6. Брейн Н. Дж. Теория перечисления Пойа / Н. Дж. Брейн // Прикладная комбинаторная математика: М.: Мир, 1968. С. 61-107.

7. Гульден Я., Джексон Д. Перечислительная комбинаторика / Гульден Я., Джексон Д. М.: Наука, 1990. - 504 с.

8. Докин В.Н. О треугольной схеме развития популяций / Докин В.Н. // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1977.-Вып. 41.-С. 104-161.

9. Комбинаторные числа и полиномы в моделях дискретных распределений / В.Н. Докин, В.Д. Жуков, H.A. Колокольникова и др. Иркутск: Изд-во Иркут. ун-та, 1990.-208 с.

10. Дубиле П., Рота Дж.-К., Стенли Р. Об основах комбинаторной теории (VI): идея производящей функции / П. Дубиле, Дж.-К. Рота, Р. Стенли // Перечислительные задачи комбинаторного анализа. М.: Мир, 1979. С. 160228.

11. Егорычев Г.П. Интергральное представление и вычисление комбинаторных сумм / Г.П. Егорычев. Новосибирск: Наука, 1977.

12. Егорычев Г.П. К обращению комбинаторных соотношений / Г.П. Егорычев // Комбинаторный анализ. М.: Изд-во МГУ, 1974. Вып. 3. - С.10-14.

13. Егорычев Г.П. Комбинаторные суммы и метод производящих функций / Г.П. Егорычев. — Краснояр. ун-т, 1974.

14. Егорычев Г.П. Обращение одномерных комбинаторных соотношений / Г.П. Егорычев // Некоторые вопросы теории групп и колец. Красноярск: ИФ СО РАН СССР, 1973.-С. 110-122.

15. Жуков В. Д. Производящий определитель / В. Д. Жуков // Асимптотические и перечислительные задачи комбинаторного анализа. -Красноярск: Краснояр. ун-т, 1976. С. 47-58.

16. Калмыков Г.И. О частичном упорядочении деревьев и классов связных графов / Г.И. Калмыков // Дискретная математика. 1992. - Т. 4, вып. 2. - С. 66-73.

17. Кан И.Д. Мебиус-функции объединения частичных порядков / И.Д1 Кан // Дискретная математика. 1991.-Т. 3, вып. 2.-С. 121-127.

18. Кофман А. Введение в прикладную комбинаторику / А. Кофмат М.: Наука, 1975. -480 с.

19. Кузьмин О.В. Построение обобщенных А- и В-полиномов в пространстве отображений / О.В. Кузьмин // Методы дискретного анализа в теории графов и сложности. Новосибирск: ИМ СО РАН, 1992. - Вып. 52. - С. 66-76.

20. Кузьмин О.В. Комбинаторные методы моделирования дискретных распределений / О.В. Кузьмин: Учеб. пособие. Иркутск: Иркут. ун-т, 2003. -136 с.

21. Кузьмин О.В. Обобщение чисел Фибоначчи и Трибоначчи / О.В. Кузьмин // Оптимизация, управление, интеллект, 2000 Вып. 4. - С. 188-198.

22. Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения / О.В. Кузьмин. Новосибирск: Наука. Сибирская издательская фирма РАН, 2000. -294 с.

23. Кузьмин О.В. Обобщенные триномиальные коэффициенты и их построение в пространстве отображений / О.В. Кузьмин // Теоретические и прикладные вопросы в задачах управления и анализа систем. Иркутск: ИрВЦ' СО АН СССР, 1989. - С. 64-78.

24. Кузьмин О.В. Перечислительная комбинаторика / О.В. Кузьмин. М.: Дрофа, 2005.-112с.

25. Кузьмин О.В. Рекуррентные соотношения и перечислительные интерпретации некоторых комбинаторных чисел и полиномов / О.В. Кузьмин // Дискретная математика. 1994. - Т. 6, вып. 3. - С. 39-49.

26. Кузьмин О.В. Траектории на решетках и комбинаторные числа / О.В. Кузьмин // Математическое моделирование в образовании, науке и производстве: Материалы междунар. научно-практ. конф. Тирасполь: РИО ПриднГУ 2001. С. 220-221.

27. Кузьмин О.В., Леонова О.В. О полиномах разбиений / О.В. Кузьмин, О.В. Леонова // Дискретная математика. 2001. - Т. 13, вып. 2. - С. 144-158.

28. Кузьмин О.В., Леонова О.В. Полиномы Тушара и их приложения / О.В. Кузьмин, О.В. Леонова . Сер. Дискретная математика и информатика. Вып. 10. -Иркутск: Иркут. ун-т, 1999. 19 с.

29. Кузьмин О.В., Тюрнева Т.Г. Числа Шредера, их обобщения и приложения / О.В. Кузьмин, Т.Г. Тюрнева // Асимтотич. и перечислит, задачи комбинат, анализа. Иркутск: Иркут. ун-т, 1997. - С. 117-125.

30. Кузьмин О.В., Тюрнева Т.Г. Пути на решетках и некоторые комбинаторные числа / О.В. Кузьмин, Т.Г. Тюрнева // Тр. Вост.-сиб. зональной межвуз. конф. по математике и проблемам ее преподавания в вузе.-Иркутск: Изд-во Иркут. пед. ун-та, 1999. С. 159-160.

31. Ландо К.С. Лекции о производящих функциях / К.С. Ландо. М.: МЦНМО, 2002. - 144 с.

32. Макдональд И. Симметрические функции и многочлены Холла / И. Макдональд. М.: Мир, 1984. - 224 с.

33. Мельников A.B. Риск-менеджмент: Стохастический анализ рисков в экономике финансов и страхования / A.B. Мельников. М.: изд-во «Анкил», 2001.- 112 с.

34. Павлов Ю.Л. Некоторые свойства плоских деревьев с висячим корнем / Ю.Л. Павлов // Дискретная математика. 1992. - Т. 4, вып. 2. - С. 61-65.

35. Павлов Ю.Л. Случайные леса / Ю.Л. Павлов. Петрозаводск: Карельский научный центр РАН, 1996. - 259 с.

36. Платонов М.Л. Комбинаторные числа класса отображений / М.Л. Платонов // Комбинаторный и асимптотический анализ. Красноярск, Краснояр. ун-т, 1975. - С.81-95.

37. Платонов М.Л. Комбинаторные числа класса отображений и их приложения / М.Л. Платонов. Москва: Наука, 1979. - 152 с.

38. Платонов М.Л. Комбинаторные числа: Учеб. пособие. / М.Л. Платонов. -Иркутск: Изд-во Иркут. ун-та, 1980. 104 с.

39. Платонов М.Л. Обращения формулы Бруно // Исследования по геомагнетизму, аэрономии и физике Солнца / М.Л. Платонов. М.: Наука, 1975. -Вып. 35.-С.32-38.

40. Платонов М.Л. Приложение комбинаторных чисел в теории вероятностей: Учеб. пособие / М.Л. Платонов. Иркутск: Изд-во Иркут. ун-та, 1982.- 112 с.

41. Платонов М.Л. Соотношения между обобщенными числами Стерлинга, построенными на разных базах / М.Л. Платонов // Комбинаторный и асимптотический анализ. Красноярск: Краснояр. ун-т, 1977. - С. 142-152.

42. Платонов М.Л., Докин В.Н. Обращение линейных соотношений, содержащих обобщенные числа Стирлинга и Лаха / М.Л. Платонов, В.Н. Докин // Асимптотические и перечислительные задачи комбинаторного анализа. — Красноярск, Краснояр. ун-т, 1976.-С. 145-161.

43. Платонов М.Л., Докин В.Н. Треугольная схема развития популяций / М.Л.

44. Платонов, В.Н. Докин // Исследования по геомагнетизму, аэрономии и физике

45. Солнца. -М.: Наука, 1975.-Вып. 41.-С. 26-31.104

46. Пойа Д. Комбинаторные вычисления для групп графов и химических соединений / Д. Пойа // Перечислительные задачи комбинаторного анализа. — М.: Мир, 1979.-С. 36-138.

47. Редфилд Дж. Теория распределений, приведенных по группе / Дж. Редфилд // Перечислительные задачи комбинаторного анализа. —М.: Мир, 1979. -С. 9-35.

48. Риордан Дж. Введение в комбинаторный анализ / Дж. Риордан. М.: Наука, 1982.-287 с.

49. Рыбников К.А. Введение в комбинаторный анализ / К.А. Рыбников. М.: Изд-во Моск. ун-та, 1985. - 308 с.

50. Стенли Р. Перечислительная комбинаторика / Р. Стенли. М.: Мир, 1990.-434 с.

51. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции / Р. Стенли. М.: Мир, 2005. - 767 с.

52. Харари Ф., Палмер Э. Перечисление графов / Ф. Харари, Э. Палмер. М.: Мир. 1977.-324 с.

53. Хомяков М.А. Обращение многомерной формулы Бруно относительно производных любой из внутренних функций / М.А. Хомяков // Алгоритмические и комбинаторные задачи дискретных систем и ЭВМ. -Иркутск: Иркут. ун-т, 1991. С. 139-147.

54. Шматков В.Д. Изоморфизмы аггебр инцидентности / В.Д. Шматков // Дискретная математика. 1991.-Т. 3, вып. 1.-С. 133-144.

55. Эндрюс Г. Теория разбиений / Г. Эндрюс. М.: Наука, 1982. - 255 с.

56. Яблонский C.B. Введение в дискретную математику / C.B. Яблонский. -М.: Наука, 1979.-272 с.

57. Aissen M. Variations on a theme of Polya / M. Aissen // Ann. N.Y. Acad. Sci.-1979.-Vol. 319.-P. 1-6.

58. Bell E.T. Partition polynomials / E.T. Bell // Ann. Math., 1927. Vol.29. - P. 38-46.

59. Buzeteanu S.N., Domocos V. Polynomial identities from weighted lattice path counting / S.N Buzeteanu, V. Domocos // Disccrete Math. 1996. - Vol.150, № 1-3. -P. 421-425.

60. Carlitz L., Roselle D.P., Scoville R.A. Some remarks on ballot-type sequences of positive integers / L. Carlitz, D.P. Roselle, R.A. Scoville // J. Combin. Theory. Ser. A. 1971. - Vol.11, № 3. - P. 258-271.

61. Chaundy T.W. Partition-generated functions / T.W. Chaundy. — Quart. J. Math. (Oxford), 1931. -Vol. 2, P. 234-240.

62. Chu W. A new combinatorial interpretation for generalized Catalan numbers / W. Chu // Discrete Math. 1987. - Vol. 65, № 1. - P. 91-94.

63. Comtet L. Sur le quatrieme problem et nombres de Schoder / L. Comtet // C.R. Acad. Sci. Paris, 1970. - Serie A, 271, № 19. - P. 913-916.

64. Donaghey R., Shapiro L.W. Motzkin numbers / R. Donaghey, L.W. Shapiro // J. Combin. Theory. Ser. B. 1977. - Vol. 23, № 2. - P. 291-301.

65. Fray R.D., Roselle D.P. On weighted lattice paths / R.D. Fray, D.P. Roselle // J. Combin. Theory. Ser. A.-1973.-Vol. 14,№1.-P. 21-29.

66. Gessel I., Viennot G. Binomial determinants, paths, and hock length frmulae / I. Gessel, G. Viennot // Advances in Math. 1985. - Vol. 58, P. 300-321. .

67. Ghurch C.A. Lattice paths and Fibonacci and Lucas numbers / C.A. Ghurch // Fibonacci Quart. 1974. - Vol. 12, № 4. - P. 366-368.

68. Gould H.W. Combinatorial indentities / H.W. Gould. Morgantown: W. Va, 1972.

69. Goulden I.P., Jackson D.M. Path generating functions and continued fractions / I.P. Goulden, D.M. Jackson // J. Combin. Theory. Ser. A , 1986. Vol. 41, № 1. - P. 1-10.

70. Gouyou-Beauchams D., Vauquelin B. Deux proprieties des nombres de Schroder / D. Gouyou-Beauchams, B. Vauquelin // Inf. Theor. Et Appl. 1988. -Vol. 22, №3.-P. 361-388.

71. Grimson R. C. Some results on enumeration of symmetric arrays / Grimson R.

72. C. // Duke Math. J. 98, 1971. P. 711-715.106

73. Gupta H. Enumeration of matrices / Gupta H. // Duke Math. J. 35, 1968. P. 653-659.

74. Hoggatt V.E. A New angle on Pascal's triangle / V.E. Hoggatt // Fibonacci Quart. 1968. - Vol. 6, № 4 - P. 221-234.

75. Howard F.T. Bell polynomials and degenerate Stirling numbers / F.T. Howard //Rend. Sem. Mat. Univ. Padova, 1979 (1980). - Vol. 61.-P. 203-219.

76. Karlin S., McGregor G. Coincdence probabilities / S. Karlin, G. McGregor // Pacific J. Math. Vol. 9. 1959. -P. 141-164.

77. Kettle St. J. G. A class of natural bijections between Catalan families / St. J. G. Kettle // Lect. Notes Math. 1982. - Vol. 952. - P. 327-348.

78. Krattenthaler C. Counting lattice paths with a liner Boundary I / C. Krattenthaler // Sitzungsber. Osterr. Akad. wiss. Abt. 2, 1989. Vol. 198, № 1-3. - P. 87-107.

79. Krattenthaler C. Counting lattice paths with a liner Boundary II: q-ballot and q-Catalan numbers / C. Krattenthaler // Sitzungsber. Osterr. Akad. wiss. Abt. 2 Math.naturwiss. Kl. Abt. 2. 1989. - Vol. 198, № 4-7. - P. 171-199.

80. Krattenthaler C., Sulanke R.A. Counting pairs of nonintersecting lattice parths with respect to weighted turns / C. Krattenthaler, R.A. Sulanke // Discrete Math. -1996,-Vol.153, № 1-3.-P. 189-198.

81. Kuba M., Wagner S. Perfect matchings and k-decomposability of increasing trees / M. Kuba M., S. Wagner // Séminaire Lotharingien de Combinatoire (электронный журнал), 2007. P. 14, доступно по адресу: http://www.inat.univie.ac.at/~slc.

82. Linstrom В. On the vector representation of induced matroids / B. Linstrom// Bull. London Math. Soc. 5, 1973. P. 85-90.

83. McGregor J.R., Narayana T.V., Ozsoyoglu Z.M. On touching, crossings and meetings of lattice paths with the diagonal / J.R. McGregor, T.V. Narayana, Z.M. Ozsoyoglu // util. Math. 1986. - Vol. 30. - P. 45-51.

84. Nilsson E.W., Sundell P. A new relation among Catalan numbers / E.W

85. Nilsson, P. Sundell //J. Math. Phys. -1995. Vol. 13, № 2. - P. 64-75.107

86. Nilton P., Pedersen J. Catalan numbers, their generalization, and their uses / P. Nilton, J. Pedersen // Math. Intell. 1995.Vol. 13, № 2. - P. 64-75.

87. Nishiyama A. On a sum of multinomial coefficients / A. Nishiyama // Sci. Re. Kagshima. Univ.-1973. Vol. 22.-P. 9-11.

88. Olive G. Catalan numbers revisited / G. Olive // J. Math. Anal. And Appl. -1985.-Vol. 111.-P. 201-235.

89. Riordan J. Combinatorial indentities /J. Riordan // New York ect.: John Wiley and Sons, 1968.

90. Riordan J. The blossoming of Schroder s fourth problem / J. Riordan // Acta Math. 1976.-Vol. 137, № 1-2.-P. 1-16.

91. Rogers D.G. Pascal triangle, Catalan numbers and renewal arrays / D.G. Rogers//Discrete Math. 1978.-Vol. 22, № 3. -P. 301-310.

92. Rogers D.G. Schroder triangle: three combinatorial problems / D.G. Rogers // Lect. Notes Math. 1977. - Vol. 622. - P. 175-196.

93. Rohatgi V.K. Some combinatorial identities involving lattice paths / V.K. Rohatgi // Amer. Math. Monthly. 1966. - Vol. 73, № 5. - P. 507-508.

94. Roman S.M., Rota G.-C. The umbral calculus / S.M. Roman, G.-C. Rota // Advances Math., 1978. Vol. 27. - P. 95-188.

95. Rota G.-C. On the foundations of combinatorial theory. I. Theory of Mobius functions / G.-C. Rota // Z. Wahrscheinlichkeitstheorie and Verw. Gebiete,1964. -Vol. 2, P.340-368.

96. Sands A.D. On generalized Catalan numbers / A.D. Sands // Discrete Math.-1989. Vol.27, № 1.-P. 33-46.

97. Schoder E. Vier combinatorische Probleme / E. Schoder // Z. for Math. Hysik 15, 1870.-P. 361-376.

98. Stanley R. Ordered structures and partitions / R. Stanley. Thesis, Harvard Univ., 1971.

99. Stanley R. The Fibonacci lattice / R. Stanley // Fibonacci Quart. -1989. Vol. 27, № 1.-P. 33-36.

100. Sulanke R.A. A recurrence restricted by diagonal condition: generalized-Catalan arrays / R.A. Sulanke // Fibonacci Quart. 1974. - Vol. 12, № 4. - P. 366368.

101. Tauber S. Lah numbers for R-polynomials / S. Tauber // Fibonacci Quart., 1968.-Vol. 6, P. 100-107.

102. Tauber S. On quasi-orthogonal numbers / S. Tauber // Amer. Math. Monthly, 1962.-Vol. 69.-P. 365-372.1. Публикации автора

103. Балагура А.А. Обобщенные пирамиды Паскаля и им обратные / А.А. Балагура, О.В. Кузьмин // Дискретная математика. 2007. - Т. 19, вып. 4. -С.108-116.

104. Балагура А.А. Обобщенная пирамида Паскаля и частично упорядоченные множества / А.А. Балагура, О.В. Кузьмин // Обозрение прикладной и промышленной математики. 2007. - Т. 14, вып. 1. - С.88-91.

105. Balagura А.А. Combinatorial polynomials partly ordered sets / А.А. Balagura, O.V. Kuzmin // Математическое моделирование в образовании, ■ науке и производстве: Мат. V межд. науч.-практ. конф. Тирасполь: РИО ПриднГУ, 2007. - С.4-5.

106. Балагура А.А. Частично упорядоченные множества и некоторые комбинаторные объекты / А.А. Балагура, О.В. Кузьмин // Комбинаторные и вероятностные задачи дискретной математики. Иркутск: Изд-во Иркут. гос. ун-та, 2006.-С. 18-32.

107. Балагура А.А. О взвешенных траекториях на решетках с особенностями / О.В. Кузьмин, А.А. Балагура // Математическое моделирование в образовании, науке и производстве: Материалы III междунар. науч.-практ. конф. -Тирасполь: РИО ПриднГУ, 2003. С.257-259.

108. Балагура A.A. О некоторых свойствах специальных матриц / A.A. Балагура, О.В. Кузьмин // Вестник Иркутского университета. Специальный выпуск. Иркутск: Изд-во Иркут. ун-та, 2003. - С. 70-71.

109. Балагура A.A. О числе траекторий на решетках с запрещенными позициями / A.A. Балагура, О.В. Кузьмин // Вестник Иркутского университета. Специальный выпуск. Иркутск: Изд-во Иркут. ун-та, 2002. - С. 5.

110. Балагура A.A. Траектории на решетках с запрещенными позициями и комбинаторные числа / A.A. Балагура, О.В. Кузьмин // Вестник Иркутского университета. Специальный выпуск. Иркутск: Изд-во Иркут. ун-та, 200К - С.

111. Балагура А.А Частично упорядоченные множества и комбинаторные объекты / A.A. Балагура // Инфокоммуникационные и вычислительные технологии и системы: Материалы II Всерос. конф. Улан-Удэ: Изд-во Бурят, ун-та, 2006. - Т. 2. - С. 34-37.

112. Балагура A.A. Анализ изменения численности популяции методом траекторий / A.A. Балагура // Всероссийский научно-практический молодежный симпозиум. Иркутск: Изд-во Иркут. ун-та, 1999. - С. 12.62.