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

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

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

Введение.

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

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

Особую роль в комбинаторике неотрицательных матриц занимают матрицы, состоящие из нулей и единиц. Это связано с тем, что многие существенные свойства неотрицательных матриц общего вида определяются свойствами их носителей - (ОД)-матриц, получающихся заменой положительных элементов исходной матрицы на единицы. Целочисленные (ОД)-матрицы были введены в конце 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)-матрицы порядка п, в каждой строке и каждом столбце которых содержится к единиц. Устанавливается связь задачи о вычислении мощности классов данных матриц с задачами перечисления взвешенных путей на геометрических решетках на плоскости. Предложен метод преобразования однородных рекуррентных соотношений, определяющих количество и суммарный вес взвешенных путей на решетках в л-мерном пространстве.

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

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.