Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках

Кроткин, Владислав Сергеевич

Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Кроткин, Владислав Сергеевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Иркутск МЕСТО ЗАЩИТЫ

2009 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках»

Автореферат диссертации на тему "Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках"

Кроткин Владислав Сергеевич

КОМБИНАТОРНЫЕ СВОЙСТВА (ОД)-МАТРИЦ И ВЗВЕШЕННЫЕ ПУТИ НА РЕШЕТКАХ

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

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

Иркутск - 2009

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

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

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

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

Павлов Юрий Леонидович

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

Ведущая организация: Омский филиал Института математики

им. С. Л. Соболева СО РАН

Защита состоится 27 ноября 2009 г. в 14-30 на заседании диссертационного совета Д.212.074.01 при Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20, Институт математики, экономики и информатики.

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

Автореферат разослан 26 октября 2009 г.

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

В.Г. Антоник

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

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

Основополагающим для современного комбинаторного анализа является введенное В.Н. Сачковым понятие комбинаторной конфигурации, включающее в себя множество различных типов дискретных систем, таких как конфигурации подмножеств, тактические конфигурации и блок-схемы, графы и сети и т.д. Чаще всего на комбинаторных конфигурациях рассматривают задачи, требующие установления факта существования конфигураций, построения конфигураций определенного вида (задачи комбинаторного моделирования), задачи перечисления всех конфигураций системы (задачи перечислительной комбинаторики) и задачи о выборе конфигураций, удовлетворяющих заданным требованиям (экстремальные комбинаторные задачи). Характерная общность и высокая степень абстракции постановок задач дает возможность получения различных интерпретаций и широту их применения.

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

Можно говорить о том, что на стыке теории матриц и комбинаторного анализа сформировалось новое направление — комбинаторная теория матриц, использующая методы линейной алгебры и комбинаторики. Объектом изучения данной области науки являются, главным образом, неотрицательные целочислен-

ные матрицы, которые рассматриваются в качестве матриц инцйдентности для различных комбинаторных конфигураций1.

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

Особую роль в комбинаторике неотрицательных матриц занимают матрицы, состоящие из нулей и единиц. Это связано с тем, что многие существенные свойства неотрицательных матриц общего вида определяются свойствами их носителей - (0,1)-матриц, получающихся заменой положительных элементов исходной матрицы на единицы. Целочисленные (ОД)-матрицы были введены в конце 50-х годов в работах Дж. Райзера, Д.Р. Фалкерсона и Д. Гейла и с тех пор интенсивно изучаются. Такие матрицы находят свое применение в задачах о потоках в сетях и используются при решении различных проблем логистики, в анализе и построении электронных схем, в задачах моделирования нейронных сетей. Комбинаторные свойства (ОД)-матриц изучались в работах P.A. Бруалди, В.Н.Сачкова, В.Е. Тараканова, H.H. Кузьюрина и др.

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

С классами данных матриц связано два фундаментальных вопроса:

1. Когда класс не пуст?

2. Чему равно точное число матриц в классе?

1 Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. - М.: ТВП, 2000.

Ответом на первый вопрос служат критерии непустоты класса. Один из первых известен, как теорема Гейла-Райзера. Более сложным оказывается второй вопрос о вычислении мощности классов Райзера, так называемая проблема Райзера. Данная задача была поставлена в конце 50-х гг. 20-го века, но до сих пор не имеет общего решения. За полвека изучения проблемы Райзера были получены различные оценки мощности данных классов и вычислительные формулы для определения мощности классов Райзера для некоторых частных случаев.

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

Еще одно направление исследований в данной диссертационной работе связано с задачами перечисления взвешенных путей на целочисленных решетках. Чаще всего пути на решетках определенного вида задаются при помощи однородных рекуррентных соотношений с соответствующими весовыми коэффициентами. Задачи перечисления путей на геометрических решетках и теория однородных рекуррентных соотношений активно развиваются и широко используются при решении различных проблем комбинаторного анализа и теории вероятностей и имеют большое значение при изучении дискретных структур.

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

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

Идеи построения пирамид и гиперпирамид и их использования высказывались многими авторами, но одни из наиболее полных и систематических исследований, посвященных обобщенной пирамиде Паскаля, сделаны Б. А. Бондаренко2 и О.В. Кузьминым3. В работах О.В. Кузьмина, Т.Г Тюрневой, В.Д. Жукова, В.Н. Докина, H.A. Колокольниковой исследуются вопросы перечисления путей на решетках и их связь с пирамидой Паскаля, рассматриваются суммы элементов, расположенных на диагоналях обычного и обобщенного треугольника Паскаля. В частных случаях получено множество соотношений для ряда хорошо известных комбинаторных чисел и их некоторых обобщений.

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

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

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

3 Кузьмин О.В. Обобщенные пирамиды Паскаля и их приложения. - Новосибирск: Наука, 2000.

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

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

Научная новизна. В работе получены новые формулы вычисления мощности классов квадратных (ОД)-матриц с заданным значением сумм элементов в строках и столбцах. Впервые установлена связь задачи вычисления мощности классов Райзера с задачами перечисления взвешенных путей на целочисленных плоских решетках. Основные результаты, представленные в диссертационной работе, являются новыми.

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

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

2. Получены рекуррентные формулы вычисления мощности классов квадратных (ОД)-матриц порядка п с заданным значением сумм элементов в строках и столбцах.

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

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

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

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

Апробация работы. Результаты были представлены на Международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2006), Ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета, (Иркутск, 2006), Межвузовской зональной конференции, посвященной памяти проф. Б.А. Бельтюкова (Иркутск, 2007), XV Всероссийской школе-коллоквиуме по стохастическим методам и IX Всероссийском симпозиуме по прикладной и промышленной математике (Волгоград, 2008), а также неоднократно докладывались и обсуждались на семинаре кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2006 - 2009).

Публикации. По теме диссертации опубликовано 8 работ. Основное содержание представлено в работах [1-6]. В число указанных работ входит 2 статьи [1,2] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ (редакция 2008 г.)», 3 статьи [3-5] в научных сборниках, 1 полный текст доклада [6] в материалах всероссийской конференции. Работы [1-4] выполнены в нераздельном соавторстве с научным руководителем.

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

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

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

В первом параграфе приводятся определения, необходимые для дальнейшего изложения.

Пусть заданы два непустых множества 5 = {$,,...,£„} и е = {Е1,...,Ет}.

Положим, что на их декартовом произведении задана функция со значениями во множестве неотрицательных действительных чисел ср\ ехБ Я*:

Назовем:

тройку (3,е,<р) - комбинаторной конфигурацией С, функцию <р: е х 5 -» Я* - весовой функцией конфигурации, значение я,, = <р(Е1^]) - весом элемента sJ в Е,.

Если > 0, то говорят, что элементы sj и Е1 инцидентны друг другу. Неотрицательную матрицу А = А(С) = («у) размера т х п называют матрицей инцидентности конфигурации С. И наоборот, можно говорить, что неотрицательная матрица Л = А (С) = (ац) размера т х п, у которой для любого

;=1

I = 1 ,...,т, порождает некоторую конфигурацию С = (8,с,<р), если в качестве 5 взять п каких-либо элементов а в качестве е взять т элементов Е1,...,Ет и опре-

делить весовую функцию ац = для всех г = 1у = 1,...,«.

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

Важным и часто используемым на практике понятием является понятие носителя матрицы. Носителем матрицы А называется (0,1)-матрица, получающаяся заменой положительных элементов исходной матрицы на единицы. Многие существенные свойства неотрицательных матриц общего вида определяются свойствами их носителей.

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

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

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

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

Рассмотрим «-множество X = {а,,...,а„} и на нем семейства 91 = {Х,,...,Хт}, состоящие из т подмножеств X, от которых требуем:

1) число элементов в них удовлетворяет условию | X, |= г(, г = 1 ,...,т;

2) элемент а] е X встречается в подмножествах из 91 в точности раз, где

г, ,г2,..., гт, ,..., - заданные целые неотрицательные числа.

Рассмотрим вопрос о существовании конфигураций 91 с данными свойствами.

Для матрицы А = [а., ] размера тхп вектором строчных сумм называется вектор Л = (г1;г2,...,гт), где г, - сумма элементов в 1-й строке Л = [«,_,], 1 = 1,...,от, и вектором столбцевых сумм называется вектор = О,,.где б 1 - сумма элементов ву'-м столбце А = [а:]], у = 1 ...п.

Для заданных целочисленных векторов К = (г,,г2,...,гп) и 5 = (л,,.у О матрица инцидентности А = [ац~\ конфигурации 91, удовлетворяющей условиям 1 и 2, есть (0,1)-матрица с вектором строчных сумм К = (г1,г1,...,гт) и вектором столбце-

вых сумм 5 = Обратно, любая (ОД)-матрица А = [а,у] размера тхп с

вектором строчных сумм Л = (г,, гг,—,гт) и вектором столбцевых сумм 5 = приводит к конфигурации подмножеств 9? с условиями 1 и 2.

Классом Райзера итп(Я,8) называется совокупность (0,1)-матриц размера тхп с заданными векторами М = (г1,г2,...,гт)н Я = в качестве векторов

строчных и столбцевых сумм соответственно.

Задача вычисления мощности классов Райзера называется проблемой Райзера.

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

В первом параграфе рассмотрен случай, когда Я = 5 = (к,к,...,к), т = п. Получена следующая теорема, которая дает способ вычисления 11!п(к,к) |.

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

\и„{к,к)\= 4,(0,...,0),

^^(ТХТНТЬ^

где суммирование ведется по всем композициям натурального к на к целых неотрицательных слагаемых, а Ап(п,...,п) = 1.

Для доказательства данного соотношения используется конструктивный подход, в соответствии с принципами которого строится алгоритм получения (0,1)-матриц размера п, в каждой строке и каждом столбце которых содержится к единиц, с подсчётом их количества.

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

Во втором параграфе рассмотрен случай т = п, Я =5 = (2,2,...,2). Получена следующая

Теорема 2.2. Число всевозможных квадратных (0,1)-матриц порядка п, в каждой строке и каждом столбце которых содержится 2 единицы, равно:

|^(2,2)|=|о„.2(0),

<3„ (к) = ^„..(к +1) + 2 (к +1)0.., (к) + (2к + 1)(к + 1)Оп., (к -1), О0(к) = ¿к0.

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

Доказано, что |£/„(2,2)| равно суммарному весу всех путей Моцкина. Пути Моцкина определяются как последовательность шагов таких, что на каждом шаге из каждой точки с координатами (п,к) можно перейти в одну из трех точек: (« + 1Д + 1), (п+\,к) или (п+\,к-Х). Числом Моцкина называется количество всех путей Моцкина, ведущих из начальной вершины с координатами (0,0) в конечную вершину (п,0), и при этом не опускающихся ниже уровня к=0. Известны многие их свойства, выражения для производящих функций и тождества, связывающие пути Моцкина с известными комбинаторными числами.

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

Основные результаты главы опубликованы в работах [1-4, 6].

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

В первом параграфе рассматривается связь задач перечисления взвешенных путей на целочисленных решетках с однородными рекуррентными соотношениями.

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

А(*\.■) = Е«/ (*1 ■. Х2)А(/1' (X,), /2 (Х2 )) . (1)

¡=1

Конкретные типы и значения комбинаторных чисел существенно зависят от начальных и конечных условий на параметры этого соотношения.

В рассмотренных выше терминах задачи о перечислении взвешенных путей на целочисленных плоских решетках можем записать следующую интерпретацию для элементов формулы (1):

А(х„х2) - точка (узел) решетки с координатами х, и х2, а1(х1,х2) - зависящий от координат вес шага - то есть весовой коэффициент, присваиваемый отрезку, при переходе от точки Л(х,,х2) к точке А(Л(х1),Д(х2),

Л(х1) = хх+Л,/2(х1) = х1+/г - функции, определяющие приращения координат для каждого шага, х1,х2,/1,/1 е = \,...,к.

Поскольку множество точек плоскости ^(х,,х2), удовлетворяющих рекуррентному соотношению (1), зависят от двух переменных (х, и х2), то такое соотношение будем называть двумерным (двухпараметрическим).

Говорят, что рекуррентное соотношение имеет порядок к, если оно позволяет выразить А(х1,х2) через: Л(/1'(л'1),/2'(х2)), А(/1\х1),/2(х2)),

Также иногда удобно записать соотношение (1) в виде:

¿>ХхнХ2)Д//<лШ*2)) = 0, (2)

1=0

Л0(х1) = х1, /°(х2) = х2, /1'(х1)^х1+Л,/2(х2) = х2+/2, х1,х2,Д,/2ег,У1 = 1,...,к.

Рекуррентное соотношение вида (2) называется однородным.

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

Естественным обобщением взвешенных путей на решетках на плоскости являются взвешенные пути на решетках в и-мерном пространстве, определяемые соотношениями вида:

¿«,(х1,...,х„)д//(Л1),...,/;"(х„))=о. (3)

¡-о

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

Во втором параграфе предложен новый метод преобразования рекуррентных соотношений, определяющих суммарный вес взвешенных путей на решетках в «-мерном пространстве, названный методом проецирования. Данный метод получил такое название, так как с геометрической точки зрения он представляет собой проецирование узлов целочисленной плоской решетки, через которые проходит заданный путь, определение координат и получение нового рекуррентного соотношения для точек проекций. Учитывая особенности рассматриваемых путей на целочисленных плоских решетках и используя методы аналитической геометрии, разработана пошаговая процедура проецирования узлов целочисленной решетки на плоскости в декартовой системе координат, через которые проходит путь, заданный рекуррентным соотношением вида (2).

Процедура 3.1

Шаг I. Рассматриваем лежащие в плоскости проецирования точки Л(х1,х2),А(х1+ Л,х2+ 72), 1 = \,...,к. Точку А(х1,х2) назовем основной точкой. Остальные точки получаются путем смещения от основной точки на значения у,' и ]'г по первой и второй координате соответственно.

Шаг 2. Выбираем направление проецирования. Через целочисленные параметры а,р задаем угловой коэффициент прямой, вдоль которой осуществляется операция проецирования.

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

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

На выходе получаем значения г и /', / = 1

Определяем вид точек проекций:

А(х^х2) имеет точку проекции А'(:) = А'(-х10 + х2а);

А(х, + Л,х2 + /2) имеют точки проекции Л'(2 + /') = А'((-х]/1 + х2а) + (-/¡/?+Уга)),

Метод проецирования обобщается на случай и-мерных рекуррентных соот-

ношений вида ^а1(х1,...,хп)А(/'(х1),...,/"(хп)) = 0. Выбирая две переменных со-

1=0

отношения и фиксируя остальные, можно с помощью вышеизложенной процедуры проделать операцию проецирования для каждой из плоскостей и получить вид (и-1)-мерного соотношения. Метод проецирования, дает возможность построить иерархию рекуррентных соотношений и соответствующих им комбинаторных чи-

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

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

V(n, k, I) = а„к_К, V(n - 1Д -1, /) + ß„^V{n -1XI -1) + Г„А, V{n -1, к, /), с граничными условиямиV(0,0,0) = V0, V(n,k,l) = 0, если min(n,k,l,n-k-l) <0.

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

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

В качестве примеров рассмотрены важные частные случаи обобщенного треугольника Паскаля — А- и ß-треугольники, образованные обобщенными числами Стерлинга второго и первого рода соответственно. При помощи суммирования элементов, расположенных на восходящих диагоналях А- и 5-треуголышков, построены два обобщения чисел Фибоначчи. Также рассматриваются важные частные случаи обобщенной пирамиды Паскаля -А- и ß-пирамиды, в каждом сечении которых расположены обобщенные триномиальные коэффициенты второго и первого рода соответственно. Строятся два обобщения чисел Трибоначчи как суммы элементов на плоских сечениях А- и 5-пирамид.

Метод проецирования применим также и к некоторым комбинаторным числам с коэффициентами, являющимися функциями, зависящими от параметров. В

качестве примеров таких чисел рассмотрены расщепленные числа Рюньона, Шредера и Каталана.

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

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

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

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

1. Кроткин B.C. О конструктивном подходе к вычислению мощности классов Райзера / B.C. Кроткин, О.В. Кузьмин // Дискретная математика. - 2009. -Т.21, вып. 3. - С.33-36.

2. Кроткин B.C. Мощность классов Райзера и взвешенные пути Моцкина / B.C. Кроткин, О.В. Кузьмин // Журнал Сибирского федерального университета. Математика и физика. -2009. - Т.2, вып. 3. - С.312-318.

3. Кроткин B.C. Рекуррентное соотношение для вычисления мощностей классов Райзера / B.C. Кроткин, О.В. Кузьмин // Обозрение прикладной и промышленной математики. -2009. - Т. 16, вып. 1. - С.120-122.

4. Кроткин B.C. О комбинаторном моделировании и мощности классов Райзера / B.C. Кроткин, О.В. Кузьмин // Моделирование. Системный анализ. Технологии: межвуз. сб. науч. тр. - Чита: ЗабИЖТ, 2008. - С.8-13.

5. Кроткин B.C. Комбинаторные операторы и геометрические свойства обобщенной пирамиды Паскаля / B.C. Кроткин // Современные проблемы математики и информатики: сб. науч. тр. студентов и аспирантов. - Оренбург: ИПК ГОУ ОГУ, 2008. - С. 31-33.

6. Кроткин B.C. Рекуррентное соотношение для вычисления мощности классов Райзера / B.C. Кроткин // Вестник Иркутского университета, Материалы ежегодной научно-теоретической конференции молодых ученых. - Иркутск: Иркут. гос. ун-т, 2006. - С. 109-110.

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

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

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

Введение.

Глава 1. Комбинаторные конфигурации и комбинаторные числа класса отображений.

1.1. Комбинаторные конфигурации и их матрицы инцидентности.

1.2. Комбинаторные числа класса отображений.

1.3. (0,1 )-матрицы и классы Райзера.

Глава 2. Комбинаторные свойства (ОД)-матриц и проблема Райзера.

2.1. Конструктивный подход к вычислению мощности классов Райзера.

2.2. Мощность классов Райзера и взвешенные пути на плоских решетках.

Глава 3. Перечисление взвешенных путей на решетках.

3.1. Рекуррентные соотношения и перечисление взвешенных путей на решетках.

3.2. Исследование взвешенных путей на геометрических решетках методом проецирования.

3.3. Комбинаторные операторы и преобразование рекуррентных соотношений.

Введение диссертация по математике, на тему "Комбинаторные свойства (0,1)-матриц и взвешенные пути на решетках"

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

А.Н. Колмогоров считал что, «кибернетика занимается изучением систем любой природы, способных воспринимать, хранить и перерабатывать информацию и использовать ее для управления и регулирования. При этом кибернетика широко пользуется математическим методом и стремится к получению специальных конкретных результатов, позволяющих как анализировать такого рода системы, так и синтезировать их» [73].

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

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

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

Первые общие схемы комбинаторных построений, позволяющие с единых позиций рассматривать обширные классы задач и объектов, возникли лишь к середине 20-го века. Наиболее известной и широко применяемой подобной конструкцией является схема перечисления Редфилда-Пойа. Они, не зависимо друг от друга, построили схему перечисления отображений конечных множеств в конечные. Удачное сочетание трех факторов: метода производящих функций, эквивалентности, индуцируемой группами подстановок на множестве отображений, и весов, приписываемых перечисляемым объектам -обеспечивает теории Редфилда-Пойа большую общность и следующую из нее широкую применимость. Метод Редфилда-Пойа получил дальнейшее развитие и многочисленные применения в работах других исследователей [41,43,50, 68].

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

В СССР развитию комбинаторного анализа способствовала работа математиков В.Л. Гончарова, К.А. Рыбникова, В.Н. Сачкова,

B.Е. Тараканова, А.О. Гельфонда, Г.П. Егорычева, О.Б. Лупанова,

C.В. Яблонского и др. Многие основополагающие результаты западных математиков можно найти на русском языке в их книгах [9, 48, 51, 57]. Серия этих книг свидетельствует о несколько более поздней, но активной и плодотворной деятельности отечественных математиков.

В 1975 году М.Л. Платоновым была предложена общая схема построения комбинаторных чисел класса отображений [41, 42]. Не умаляя достоинств замечательных работ Д. Пойа, Дж.-К. Рота и их последователей, отметим, что основные понятий предыдущих теорий перечисления можно вывести из общей схемы Платонова, как частные случаи.

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

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

Основополагающим для современного комбинаторного анализа является введенное В.Н. Сачковым понятие комбинаторной конфигурации, включающее в себя множество различных типов дискретных систем, таких как конфигурации подмножеств, тактические конфигурации и блок-схемы, графы и сети и т.д [54]. Чаще всего на комбинаторных конфигурациях рассматривают задачи, требующие установления факта существования конфигураций, построения конфигураций определенного вида (задачи комбинаторного моделирования), задачи перечисления всех конфигураций системы (задачи перечислительной комбинаторики[24]) и задачи о выборе конфигураций, удовлетворяющих заданным требованиям (экстремальные комбинаторные задачи[3]). Характерная общность и высокая степень абстракции постановок задач дает возможность получения различных интерпретаций и широту их применения.

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

В настоящее время можно говорить о том, что на стыке теории матриц и комбинаторного анализа сформировалось новое направление -комбинаторная теория матриц, использующая методы линейной алгебры и комбинаторики [54, 87, 90, 94]. Объектом изучения данной области науки являются неотрицательные целочисленные матрицы, которые с одной стороны могут рассматриваться как матрицы инцидентности для различных комбинаторных конфигураций, а с другой при изучении свойств которых применяются методы комбинаторного анализа.

Особую роль в комбинаторике неотрицательных матриц занимают матрицы, состоящие из нулей и единиц. Это связано с тем, что многие существенные свойства неотрицательных матриц общего вида определяются свойствами их носителей - (ОД)-матриц, получающихся заменой положительных элементов исходной матрицы на единицы. Целочисленные (ОД)-матрицы были введены в конце 50-х годов в работах Дж. Райзера, Д.Р. Фалкерсона и Д. Гейла [105-108, 125-127] и с тех пор интенсивно изучаются. Такие матрицы находят свое применение в задачах о потоках в сетях и используются при решении различных проблем логистики, в анализе и построении электронных схем, в задачах моделирования нейронных сетей. Комбинаторные свойства (ОД)-матриц изучались в работах P.A. Бруалди [85-98], Дж. Райзера [124-128], В.Н. Сачкова [54], В.Е.Тараканова [57-64], H.H. Кузьюрина [30, 31, 116] Спитцером и многих других.

С классами данных матриц связано два фундаментальных вопроса:

1. Когда класс не пуст?

2. Чему равно точное число матриц в классе?

Ответом на первый вопрос служат критерии непустоты класса. Один из первых известен, как теорема Гейла-Райзера [54]. Более сложным оказывается второй вопрос о вычислении мощности классов Райзера, так называемая проблема Райзера. Данная задача была поставлена в конце 50-х годов 20-го века, но до сих пор не имеет общего решения. За полвека изучения проблемы Райзера были получены различные оценки мощности данных классов [54] и вычислительные формулы для определения мощности классов Райзера для некоторых частных случаев [120, 137, 138].

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

Задачи перечисления взвешенных путей на решетках и случайных блужданий по узлам целочисленных решеток рассматривались О.В;, Кузьминым, Т.Г Тюрневой, В.Н. Докиным, Н.А. Колокольниковой, В. Феллером, Э.В. Монтроллом, Р. Стэнли, Ф. Спитцером и многими другими [19, 24, 26, 28, 32, 43,. 55]. В большинстве публикаций, рассматриваются только одномерные и двумерные решетки и задачи блуждания на них. Принципиальную сложность имеет именно задача перехода с плоских схем на трехмерный случай, а дальнейшие обобщения носят скорее технический характер и делаются по аналогии.

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

Имеется множество научных и методических публикаций [75-78, 80, 83, 84, 99, 100, 111-115, 119, 121, 123, 131-133, 136], а также несколько книг и монографий, посвященных пирамиде Паскаля [7, 22, 65, 103, 110]. Идеи построения пирамид и гиперпирамид и их использования высказывались многими авторами, но одни из наиболее полных и систематических исследований посвященных обобщенной пирамиде Паскаля сделаны Б.А. Бондаренко [7] и О.В. Кузьминым [22]. В работах О.В. Кузьмина, Т.Г. Тюрневой, В.Д. Жукова, В.Н. Докина, H.A. Колокольниковой [19, 21-29] исследуются вопросы перечисления путей на решетках и их связь с пирамидой Паскаля, рассматриваются суммы элементов, расположенных на диагоналях обычного и обобщенного треугольника Паскаля. В частных случаях получено множество соотношений для ряда хорошо известных комбинаторных чисел и их некоторых обобщений.

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

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

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

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

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

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

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

Во второй главе исследуются классы Райзера - классы квадратных (ОД)-матриц порядка п, в каждой строке и каждом столбце которых содержится к единиц. Установлена связь задачи о вычислении мощности классов данных матриц с задачами перечисления взвешенных путей на геометрических решетках на плоскости. Получено выражение мощности класса Райзера через взвешенные числа Моцкина. Получены новые формулы вычисления мощности классов квадратных (0,1)-матриц порядка п с заданным значением сумм элементов в строках и столбцах. Приведены примеры использования данных формул. Полученные формулы дают возможность проводить дальнейшие исследования проблемы Райзера, используя общие методы дискретной математики для работы с рекуррентными соотношениями.

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

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

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

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

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

2. Андерсон Д. Дискретная математика и комбинаторика / Д. Андерсон. М: Вильяме, 2004.

3. Баранов В.И.Экстремальные комбинаторные задачи и их приложения / В.И. Баранов, Б.С. Стечкин. -М.: ФИЗМАТЛИТ, 2004.

4. Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати. М.: Наука, 1974.

5. Берж К. Теория графов и ее применения / К. Берж. М.: ИЛ, 1962.

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

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

8. Гантмахер Ф.Р. Теория матриц / Ф.Р. Гантмахер. М.: Наука, 1967.

9. Гельфонд А. О. Исчисление конечных разностей / А. О. Гельфонд. -М.: Наука, 1967.

10. Грэхем Р. Начала теории Рамсея / Р. Грэхем. М: Мир, 1984.

11. Грэхем Р. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник. М.: Мир, 1998.

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

13. Дистель Р. Теория графов. / Р. Дистель Новосибирск: Изд-во Ин-та математики, 2002.

14. Егорычев Г. П. Доказательство гипотезы Ван дер Вардена для перманентов / Г. П. Егорычев // Сиб. матем. ж., т. 22, 1981. С. 65-71.

15. Кнут Д. Искусство программирования, т. 1. Основные алгоритмы / Д. Кнут. СПб.: Вильяме, 2000.

16. Кнут Д. Искусство программирования, т. 2. Получисленные алгоритмы / Д. Кнут. СПб.: Вильяме, 2000.

17. Кнут Д. Искусство программирования, т. 3. Сортировка и поиск / Д. Кнут. СПб.: Вильяме, 2000.

18. Кнут Д. Искусство программирования, т. 4. Вып.2-4 / Д. Кнут. СПб.: Вильяме, 2008.

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

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

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

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

23. Кузьмин О.В. Операторная форма обобщений чисел Трибоначчи / О.В. Кузьмин // Труды. Вост.-Сиб. зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. -Иркутск: Изд-во Иркут. пед. ун-та, 1999. С. 156-157.

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

25. Кузьмин О.В. Тензорное представление комбинаторных чисел / О.В. Кузьмин, М.В. Лобах // Асимптотические и перечислительные задачи комбинаторного анализа. Иркутск: Иркут. ун-т, 1997. - С. 110-116.

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

27. Кузьмин О.В. Числа Каталана, их обобщения и разложения / О.В. Кузьмин, Т.Г. Тюрнева// Серия Дискретная математика и информатика. Иркутск: Иркут. ун-т, 1999. - Вып. 11.

28. Кузьмин О.В. Некоторые свойства и перечислительные интерпретации чисел Моцкина / О.В. Кузьмин, Т.Г. Тюрнева // Труды 12-й Байкальской междунар. конф. "Методы оптимизации и их приложения", Секция 5: Дискретная математика. Иркутск, 2001. - С. 87-91.

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

30. Кузюрин H.H. Асимптотическое исследование задачи о покрытии / H.H. Кузюрин // Проблемы кибернетики. М.: Наука, 1980. - Вып. 37. -С. 19-56.

31. Кузюрин H.H. К задаче об а-глубине матриц / H.H. Кузюрин // Вопросы кибернетики, 1982, т. 87. С. 131-139.

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

33. Ланкастер П. Теория матриц / П. Ланкастер. М: Мир, 1981.

34. Марков A.A. О логике конструктивной математики / A.A. Марков. -М: Мир, 1972.

35. Марков A.A. Конструктивная математика / A.A. Марков // Математический энциклопедический словарь. — М, 1983.

36. Марков A.A. Теория алгорифмов / A.A. Марков// Тр. матем. ин-та им.В.А.Стеклова АН СССР. 1954. Т.42.

37. Мартин-Леф П. Очерки по конструктивной математике / П. Мартин-Леф. М.: Мир, 1975.

38. Минк X. Перманенты / X. Минк. М.: Мир, 1982.

39. Новиков Ф.А. Дискретная математика для программиста / Ф.А. Новиков. СПб.: Питер, 2004.

40. Ope. О. Теория графов / О. Ope. M.: Наука, 1968.

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

42. Платонов М.Л. Комбинаторные числа / М.Л. Платонов. Иркутск: Иркут. ун-т, 1980.

43. Прикладная комбинаторная математика: Сб. статей. / ред. Э. Беккенбах. -М.: Мир, 1968.

44. Проблемы комбинаторного анализа: Сб. переводов. М.: Мир, 1980.

45. Райзер Г.Дж. Комбинаторная математика / Г. Дж. Райзер. М.: Мир, 1966.

46. Риордан Дж. Введение в комбинаторный анализ / Дж. Риордан. М.: Иностр. лит., 1963.

47. Риордан Дж. Комбинаторные тождества / Дж. Риордан. М.: Наука, 1982.

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

49. Рыбников К.А. История математики / К.А. Рыбников. — М.: Изд-во Моск. ун-та, 1994.

50. Рыбников К.А. Комбинаторный анализ. Очерки истории / К.А. Рыбников. М.: Изд-во мех.-мат. ф-та МГУ, 1996.

51. Сачков В.Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. М.: МЦНМО, 2004.

52. Сачков В.Н. Комбинаторные задачи классические / В.Н. Сачков // Мат. Энциклопедия М.: Сов. Энциклопедия. - Т. 2, 1979.

53. Сачков В.Н. Комбинаторный анализ / В.Н. Сачков // Мат. энциклопедия М.: Сов. Энциклопедия. - Т. 2, 1979.

54. Сачков В.Н. Комбинаторика неотрицательных матриц / В.Н. Сачков, В.Е. Тараканов. М.: ТВП, 2000.

55. Спитцер Ф. Принципы случайного блуждания / Ф. Спитцер. М.: Мир, 1969.

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

57. Тараканов В.Е. Комбинаторные задачи и (0,1 )-матрицы / В.Е. Тараканов. М.: Наука, 1985.

58. Тараканов В.Е. Максимальная глубина произвольных классов (0,1)-матриц и некоторые ее применения / В.Е. Тараканов // Матем. сб., 1973, т. 92, № 134, С. 472-490.

59. Тараканов В.Е. О глубине (ОД)-матриц с одинаковыми строчными и одинаковыми столбцевыми суммами / В.Е. Тараканов // Матем. заметки. 1983. - Т. 34. - С. 463-476.

60. Тараканов В.Е. О максимальной глубине одного класса (ОД)-матриц / В.Е. Тараканов // Матем. сб., 1968. Т. 75, № 117. - С. 4-14.

61. Тараканов В.Е. О реберном числе независимости и числе покрытия для регулярных графов / В.Е. Тараканов // Дискретн. матем., 1990. Т. 2.-С. 16-25.

62. Тараканов В.Е. О свойствах операции замены в классах (ОД)-матриц / В.Е. Тараканов//Матем. заметки, 1993, т. 53.-С. 131-141.

63. Тараканов В.Е. О числах покрытия регулярных мультиграфов /

64. B.Е. Тараканов // Матем. заметки. 1989, т. 46, С. 66-75.

65. Тараканов В.Е. Соотношения максимальных глубин классов квадратных (ОД)-матриц при различных параметрах / В.Е. Тараканов // Матем. сб., 1968, т.77, №119, С. 59-70.

66. Успенский В.А. Треугольник Паскаля / В.А. Успенский. М.: Наука, 1979.

67. Фаликман Д.И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы / Д.И. Фаликман // Мат. заметки, 1981, т. 29, С. 931-938.

68. Харари Ф. Теория графов / Ф. Харари. М.: Мир, 1973.

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

70. Холл М. Комбинаторика / М. Холл. М.: Мир, 1970.

71. Холл М. Комбинаторный анализ / М.Холл. М.: ИЛ, 1963.

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

73. Эрдеш П. Вероятностные методы в комбинаторике / П. Эрдеш, Дж. Спенсер. -М.: Мир, 1976.

74. Эшби У.Р. Введение в кибернетику / У.Р. Эшби. М.: Иностр. лит., 1959.

75. Яблонский С.В. Введение в дискретную математику. 2-е изд. /

76. C.В. Яблонский. М.: Наука, 1986.

77. Alexanderson G.L. A Property of Multinomial Coefficients /

78. G.L. Alexanderson, V.E. Hoggatt, Jr. // Fibonacci Quarterly. 1971. - Vol. 9, No. 4.-P. 351-356.

79. Alexanderson G.L. Sums of Partition Sets in Generalized Pascal Triangles / G.L. Alexanderson, V.E. Hoggatt, Jr. // The Fibonacci Quarterly. 1976. -Vol. 14,No. 2.-P. 117-125.

80. Ando S. Generalization to Large Hexagons of the Star of David Theorem with Respect to GCD / S. Ando, C. Long, D. Sato // Applications of Fibonacci Numbers. 1998. Vol. 7. -P. 23-28.

81. Ando S. A necessary and Sufficient Condition that Rays of a Star Configuration on Pascal's Triangle Cover its Center with Respect to GCD and LCM / S. Ando, D. Sato // Applications of Fibonacci Numbers. 1999. -Vol. 5.-P. 11-36.

82. Andrews G.E. Lattice gas generalization of the hard hexagon model III q-trinomials coefficients / G.E. Andrews, J. Baxter// J. Stat. Phys. 1987. -Vol. 47.-P. 297-330.

83. Basil M. Pascal's pyramid / Basil M. // Math Teacher. 1968. - Vol. 61, P. 19-21.81., Belbachir H. Linear Recurrent Sequences And Powers Of A Square Matrix / H. Belbachir, F. Bencherif // Electronic Journal Of Combinatorial Number Theory.-2006.-No. 6.

84. Bicknell M. Numerator Polynomial Coefficient Arrays for Catalan and Related Sequence Convolution Triangles / M. Bicknell, V.E. Hoggatt, Jr. // Fibonacci Quarterly. 1977. - Vol. 15, No. 1. - P. 30-34.

85. Boisen M.B., Jr. Overlays of Pascal's Triangle / M.B. Boisen, Jr. // Fibonacci Quarterly. 1969. - Vol. 7, No. 2. - P. 131-139.

86. Bollinger R.C. A note on Pascal-T triangles, multinomial coefficients, and Pascal pyramids / R.C. Bollinger// The Fibonacci Quarterly. 1986. - Vol. 24, No. 2.-P. 140-144.

87. Brualdi R.A. A note on multipliers of difference sets / R.A. Brualdi // J. Research. National. Bur. Standards. 1965. - Vol 69B. - P. 87-89.

88. Brualdi R.A. Algorithms for constructing (0,l)-matrices with prescribed row and column sum vectors / R.A. Brualdi // Discrete Math. 2006. - Vol. 36, No. 23.-P. 3054-3062.

89. Brualdi R.A. Combinatorial Matrix Theory / R.A. Brualdi, H J. Ryser. -Cambridge University Press., 1991.

90. Brualdi R.A. Matrices of zeros and ones with fixed row and column sum vectors / R.A. Brualdi // Linear Algebra Appl. 1980. - Vol. 33. - P. 159 -231.

91. Brualdi R.A. On Haber's minimum term rank formula / R.A. Brualdi // Europ. J. Combinatorics. 1981, - Vol. 2, No. 1. - P. 17-20.

92. Brualdi R.A. Some Highlights of Combinatorial Matrix Theory / R.A. Brualdi. Madison: Department of Mathematics. University of Wisconsin., 2003.

93. Brualdi R.A. Matrices of zeros and ones with given line sums and a zero block / R.A. Brualdi, G. Dahl // Linear Algebra and its Applications. -2005.-Vol. 371.-P. 191 -207.

94. Brualdi R.A. More on the Bruhat order for (0, l)-matrices / R.A. Brualdi, L. Deaett // Linear Algebra and its Applications. 2007. - Vol. 421, No. 2-3.-P. 219-232.

95. Brualdi R.A. Ordering classes of matrices of 0s and Is / R.A. Brualdi, A. Hilton, J. Talbot // Surveys in Combinatorics 2007. Cambridge University Press, 2007. - P. 41 - 67.

96. Brualdi R.A. The many facets of combinatorial matrix theory /

97. R.A. Brualdi, C.R. Johnson // Matrix Theory and Applications, American Mathematical Society, AMS Bookstore, 1990. P. 1 -37.

98. Brualdi R.A. Small diameter interchange graphs of classes of matrices of zeros an ones. / R.A. Brualdi, Li Qiao // Linear Algebra and Appl. 1982. -Vol. 46.-P. 177-194.

99. Brualdi R.A. Two Extremal Problems in Graph Theory / R.A. Brualdi,

100. S. Mellendorf // The Electronic Journal of Combinatorics. 1994. - Vol. 1, No. 1.

101. Brualdi R.A. Invariant sets for matrices of zeros and ones / R.A. Brualdi, J.A. Ross // Proc. Amer. Math. Soc. 1980. - Vol. 80. - P. 706-710.

102. Brualdi R.A. Discrepancy of Matrices of Zeros and Ones / R.A. Brualdi, J. Shen // Electronic J. Combinatorics. 1999. - Vol. 6, No. 1- P. 1-12.

103. Call G.S. Pascal's Matrices / G.S. Call, D. Velleman // Am. Math. Monthly. 1993. - Vol. 100. -P. 372-376.

104. Dence T.P. Some Half-Row Sums from Pascal's Triangle via Laplace Transforms / T.P. Dence // The College Mathematics Journal. 2007. -Vol. 38, No. 3.-P. 205-209.

105. Donaghey R. Motzkin numbers / R. Donaghey, L.W. Shapiro // Journal of Combinatorial Theory. 1977. Series A23. - P. 291-301.

106. Edelman A. Pascal Matrices / A. Edelman, G. Strang // Amer. Math. Monthly. 2004. - Vol. lll,No3.-P. 189-197.

107. Edwards A.W.F. Pascal's Arithmetical Triangle: The Story of a Mathematical Idea / A.W.F. Edwards. Baltimore, Maryland: The Johns Hopkins University Press, 2002.

108. Fonsecaa C.M. On (0, l)-matrices with prescribed row and column sum vectors / C.M. Fonsecaa, R. Mamedea // Discrete Math. 2009. - Vol. 309, -P. 2519-2527.

109. Fulkerson D.R. Zero-one matrices with zero trace / D.R. Fulkerson // Pacific J. Math. 1960. - Vol. 10, No. 3. - P. 831-836.

110. Fulkerson D.R. Widths and heights of (0, l)-matrices / D.R. Fulkerson, H.J. Ryser // Can. J. Math. 1961. - Vol. 13, No. 2. -P. 239-255.

111. Fulkerson D.R. Widths sequences for special classes of (0, l)-matrices / D.R. Fulkerson, H.J. Ryser // Can. J. Math. 1963. - Vol. 15, No. 3. -P. 371-396.

112. Gale D. A theorem on flows in networks ID. Gale // Pacific J. Math. -1957.-Vol. 7, No 2.-P. 1073-1082.

113. Gerard Y. Reconstructing a Matrix with a Given List of Coefficients and Prescribed Row and Column Sums Is NP-Hard / Y. Gerard // Lecture Notes in Computer Sciences 2008. Vol. 4992, - P. 363-371.

114. Green T.M. Pascal's Triangle / T.M. Green, C.L. Hamberg. Palo Alto: Dale Seymour, 1986.

115. Hilton P. Relating Geometry and Algebra in the Pascal Triangle, Hexagon, Tetrahedron, and Cuboctahedron Part I / P. Hilton, J. Pedersen // College Mathematics Journal. 1999. - Vol. 30, No. 3. - P. 170 - 186.

116. Hilton P. Looking into Pascal's Triangle / P. Hilton, J. Pedersen // Combinatorics, Arithmetic, and Geometry, Math. Magazine. 1987. - Vol. 60.-P. 305-316.

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

118. Kallos G. A Generalization of Pascal's Triangle Using Powers of Base Numbers / G. Kallos // Annales mathématiques Blaise Pascal. 2006. -Vol. 13, No. l.-P. 1-15.

119. Kapur J.N. Generalized Pascal triangles / J.N. Kapur // Math. Education. -1975.-Vol. 9.-P. 80-86.

120. Kuzjurin N.N. Combinatorial Problems Of Packing And Covering And Related Problems Of Integer Linear Programming / N.N. Kuzjurin // Journal of Mathematical Sciences. 2002. - Vol. 108, Num. 1. - P. 1 - 48.

121. Mink H. Permanential compounds permanents of (0,l)-circulants / H. Mink // Linear Algebra and Appl. 1987. - Vol. 86. - P: 11-42.

122. Mink H. Recurrence formulas for permanents of (0,l)-matrices / H. Mink // Linear Algebra and Appl. 1985. - Vol. 71. - P. 241-265.

123. Ollerton R.L. Partial row-sums of Pascal's triangle / R.L. Ollerton // International Journal of Mathematical Education in Science and Technology. 2007. - Vol. 38, Num. l.-P. 124-127.

124. Pérez-Salvador B.R. A reduced formula for the precise number of (0, 1)-matrices in A (R, S) / B.R. Pérez-Salvador, S. Cobos-Silva, M.A. Gutiérrez-Ándrade, A. Torres-Chazaro // Discrete Math. 2002. - Vol. 256, No. 1-2. -P. 361-372

125. Puritz C.W. Extending Pascal's Triangle Upwards / C.W. Puritz // The Mathematical Gazette. 1981. - Vol. 65, No. 431. - P. 42-44.

126. Putz J.F. The Pascal Polytope: An Extension of Pascal's Triangle to N Dimensions / J.F. Putz // The College Mathematics Journal. 1986. - Vol. 17, No. 2.-P. 144-155.

127. Rogers D.G. Pascal triangle, Catalan numbers and renewal arrays /

128. D.G. Rogers // Discrete Math. 1978. - Vol. 22, № 3. - P.301-310

129. Ryser H.J. Combinatorial properties of matrices of zeros and ones / H.J. Ryser // Cañad. J. Math. -1957. Vol. 9. - P. 371-377.

130. Ryser H.J. Matrices and differences / H.J. Ryser // Discrete Math. 1984. -Vol. 49.-P. 169-173.

131. Ryser H.J. Matrices Of Zeros And Ones / H.J. Ryser // Bull. Amer. Math. Soc. 1960. - Vol. 66, Num. 6. - P. 442-464.

132. Ryser H.J. Matrices of zeros and ones in combinatorial mathematics / H.J. Ryser // Recent advances in Matrix theory. Wisconsin: Univ. of Wisconsin Press, 1964, P. 103-124.

133. Ryser H.J. The term rank of a matrix / H.J. Ryser // Cañad. J. Math. 1958. -Vol. 10.-P. 57-65.

134. Schilling A., Supernormal coefficients, Polynomial identities and q-series / A. Schilling, S.O. Warnaar // The Ramanujan Journal. 1998. - Vol. 2. -P. 459-494.

135. Sierksma G. The structure matrix of (0,l)-matrices: its rank, trace and eigenvalues. An application to econometric models / G. Sierksma,

136. E. Sterken // Linear Algebra and Appl. 1986. - Vol. 83. - P. 151-166.

137. Smith С. Generating functions of central values of generalized Pascal triangles / C. Smith, V.E. Hogatt // The Fibonacci Quarterly. 1979. - Vol. 17.-P. 58-67.

138. Smith K.J. Pascal's Triangle / K.J. Smith // The Two-Year College Mathematics Journal. 1973. - Vol. 4, No. 1. - P. 1-13.

139. Smith S. Row and Rising diagonal sums for a type of Pascal Triangle / S. Smith, D. Priest // Fibonacci Quart. 1977. -Vol. 15, No.4. - P. 359361.

140. Snijders T. Enumeration and simulation methods for (0,l)-matrices with given marginals / T. Snijders // Psychometrika. 1991. - Vol. 56, No. 3. -P. 397-417.

141. Walkup D.W. Minimal interchanges of (0,l)-matrices and disjoint circuits in graphs / D.W. Walkup // Canad. J. Math. 1965. - Vol. 17.-P. 831838.

142. Walser H. The Pascal Pyramid / H. Walser // The College Mathematics Journal. 2000. - Vol. 31, No. 5. - P. 383 - 392.

143. Wang B.Y On the precise number of (0, l)-matrices in U(R, S) /

144. B.Y Wang, F. Zhang // Discrete Mathematics. 1998. - Vol. 187.-P. 211220.

145. Wang B.Y. Precise number of (0,l)-matrices in U(R,S) / B.Y Wang // Scientia sinica. 1988. - Series A, Vol. 1. - P. 1-6.1. Публикации автора.

146. Кроткин B.C. О конструктивном подходе к вычислению мощности классов Райзера / B.C. Кроткин, О.В. Кузьмин // Дискретная математика. 2009. - Т.21, вып. 3. - С.33-36.

147. Кроткин B.C. Мощность классов Райзера и взвешенные пути Моцкина / B.C. Кроткин, О.В. Кузьмин // Журнал Сибирскогофедерального университета. Математика и физика. 2009. - Т.2, вып. 3. - С.312-318.

148. Кроткин B.C. Рекуррентное соотношение для вычисления мощностей классов Райзера / B.C. Кроткин, О.В. Кузьмин // Обозрение прикладной и промышленной математики. 2009. - Т. 16, вып. 1. — С. 120-122.

149. Кроткин B.C. О комбинаторном моделировании и мощности классов Райзера / B.C. Кроткин, О.В. Кузьмин // Моделирование. Системный анализ. Технологии: межвуз. сб. науч. тр. — Чита: ЗабИЖТ, 2008. -С.8-13.

150. Кроткин B.C. Комбинаторные операторы и геометрические свойства обобщенной пирамиды Паскаля / B.C. Кроткин // Современные проблемы математики и информатики: сб. науч. тр. студентов и аспирантов. Оренбург: ИПК ГОУ ОГУ, 2008. - С. 31-33.

151. Кроткин B.C. Рекуррентное соотношение для вычисления мощности классов Райзера /B.C. Кроткин // Вестник Иркутского университета, Материалы ежегодной научно-теоретической конференции молодых ученых. Иркутск: Иркут. гос. ун-т, 2006. - С. 109-110.

152. Кроткин B.C. О подходе к классификации комбинаторных чисел с помощью проецирования обобщенной пирамиды Паскаля /

153. B.C. Кроткин // Математика и проблемы ее преподавания в вузе: Тр. III межвузовской зональной конференции, посвящ. памяти проф. Б.А.Бельтюкова. — Иркутск: Изд-во Иркут. гос. пед. ун-та, 2007.1. C. 127.

154. Кроткин B.C. О мощности классов Райзера / B.C. Кроткин // Студент и научно-технический прогресс: Материалы XLIV международной научной студенческой конференции. Новосиб. гос. ун-т. Новосибирск, 2006. - С. 71.