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

• Балагура, Анна Александровна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Балагура, Анна Александровна

Введение

Глава 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 наименований. Общий объем.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Балагура, Анна Александровна

Заключение

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Балагура, Анна Александровна, 2008 год

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.