Комбинаторные числа и взвешенные траектории на решетках

Широкое использование дискретной математики в различных сферах человеческой деятельности вызывает интерес к данному разделу математики, а так же стимулирует ее постоянное развитие. Дискретная математика объединяет многие теории, использующиеся в исследовании разнообразных моделей дискретного принципа действия. В современной дискретной математике в основном выделяют следующие разделы: математическая логика, комбинаторика, теория графов, теория множеств, теория алгоритмов и вычислений, которым посвящено множество литературы (см., например, [13,41, 63, 67]).

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

К настоящему времени появилось большое количество руководств по комбинаторике, укажем лишь некоторые из них — это книги М. Айгнера, Я. Гульдена, Д. Джексона, Г. П. Егорычева, Ф. Картеси, А. Кофмана, О. В. Кузьмина, Р. А. Макмагона, М. JI. Платонова, Г. Дж. Райзера, Дж. Риордана, К. А. Рыбникова, В. Н. Сачкова, Р. Стенли, М. Холла, и многие другие [12, 21, 24, 32, 33, 44, 45,48,49, 50, 53, 54, 57, 65].

В комбинаторном анализе, как и в дискретной математике в целом, речь идет об исследовании дискретных систем и их разнообразных интерпретаций, исходящих из общих комбинаторных представлениях о наборе операций. Подобные интерпретации, изучаемые в комбинаторном анализе, появляются и существуют во многих видах: сети (транспортные, электрические, информационные и другие), матрицы, блок-схемы, дискретные математические модели процессов техники и естествознания (см., например, [25, 32]).

Комбинаторный анализ способствовал формированию и применению ряда математических методов: полной математической индукции, производящих функций, рекуррентных соотношений, конечных разностей, включения и исключения и других[51].

Возрастающее значение комбинаторного анализа в последние годы связано не только с обновлением аппарата, но и с расширением самого предмета исследований. Комбинаторные методы с успехом используются в таких разделах математики, как теория чисел, алгебра, теория вероятностей, геометрия, теория графов, а также имеют много интересных и актуальных приложений в психологии, медицине, космической технике, радиосвязи и т. д. [20,41,44, 62, 89].

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

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

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

Задачи на перечисление. В задачах такого типа речь идет о нахождении числа тех или иных конфигураций из элементов некоторого конечного множества. При этом мощность множества, как правило, представляет собой основной параметр задачи, а конкретные ее условия обычно выражаются также через те или иные числовые характеристики. Тем самым решение перечислительной задачи естественным образом оказывается связанным с изучением свойств числовых последовательностей, зависящих от нескольких натуральных параметров. Рассмотрение формального степенного ряда от одной или нескольких переменных (производящая функция), дает возможность представить в свернутом виде наиболее существенную информацию о числовых последовательностях, связанных с данной перечислительной задачей. Решением такого рода задач занимается перечислительная комбинаторика[15,42, 57, 54, 66].

Перечислительная комбинаторика является наиболее развитой ветвью современного комбинаторного анализа, имеющая разнообразные приложения^, 76]. Эффективным средством решения перечислительных комбинаторных задач был и остается метод производящих функций[21,49, 98]. Современное развитие комбинаторного анализа тесно связано с использованием данного метода. Применение производящих функций намного сокращает объем необходимых преобразований, позволяет унифицировать многие результаты и тем самым дает возможность охватить значительно больший круг вопросов[12,21,37,40, 83].

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

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

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

В последние десятилетия расширился круг исследователей, как самого треугольника Паскаля, так и его плоских[59, 60, 72, 96, 97] и пространственных аналогов и обобщений, что способствует появлению новых арифметических треугольников с алгоритмом их построения (см., например, [18,33,70,77,86,93]).

Одной из таких структур является треугольная схема, предложенная В. Н. Докиным и М. JI. Платоновым[22, 46], её элементами являются обобщенные числа Стирлинга первого рода и второго рода А^, удовлетворяющие следующим рекуррентным соотношениям, соответственно.

Также дополнительно полагают, что Апп = В&bdquo- = 1, п = 0, о>- =В% =0, если min (п, к, п-к) < 0 (см., например, [15]).

Треугольные схемы составленные из чисел В£ и А£ называются Ви.

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

V{n, k) = ря>4/(л —, к -1)+<хatkV (n —, к) с граничными условиями V (0,0) = V0, V (n, k) = 0, если тт (п, к, пк) < 0. Число К (0,0), стоящее в вершине обобщенного треугольника Паскаля, оговаривается особо (во многих случаях его можно принять за единицу). Величины ал к и Рл к называются весовыми коэффициентами[33].

Еще одной такой структурой является пирамида Паскаля, о которой, по-видимому, одним из первых упоминает Е. В. Rosentahl [18]. Пирамида Паскаляэто трехгранный пирамидальный массив, в n-сечении (треугольнике) параллель п Л ном основанию, которого располагаются триномиальные коэффициенты k, l j.

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

V (n, k, l) = a", kuV (n —, к -1,/) + рnXlxV (n -1, к, 1 ~ 1) + Jn, k, iV (n ~ W) с граничными условиями V (0,0,0) = VQ, V (n, k, l) = 0, если тт (п, к,1,п-к-1)<0. Число V0, стоящее в вершине (нулевом слое) обобщенной пирамиды Паскаля, оговаривается особо (во многих случаях можно считать V0 = 1). Величины а"Х1, $п>к>1 и уи>м, фигурирующие в рекуррентном соотношении, называют весовыми коэффициентами[33].

Важными частными случаями обобщенной пирамиды Паскаля являются А-и Впирамиды, в каждом сечении которых расположены обобщенные триномиальные коэффициенты первого и второго рода, удовлетворяющие следующим рекуррентным соотношениям, соответственно ak-^k-, l + 1 + YkKj и В1, = а +д. А" +r&bdquo—tBnkjl ¦

Также дополнительно полагают, что Л®->0 = Bq0 = 1- = 1= 0, если min («, k, l, n — k — l) < 0 [33].

Ещё одним частным случаем обобщенной пирамиды Паскаля является рассмотренный ранее обобщенный треугольник Паскаля.

Различным арифметическим треугольникам и пирамидам комбинаторного происхождения, которые предлагают многие авторы (Б. А. Бондаренко, С. Гамберг, Т. Грин, В. Н. Докин, О. В. Кузьмин, Д. Кнут, М. JL Платонов, Д. Прист, Дж. Риордан, Д. Роджерс, С. Смит, Р. Стенли, Т. Г. Тюрнева, В. А. Успенский, В. Хоггат, JI. Шапиро и др.), приписывают или можно приписать внутреннюю структуру [59, 18, 33, 35, 57,22,46].

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

Решетка (или структура) — частично упорядоченное множество, в котором каждое двух элементное подмножество имеет как точную верхнюю, так и точную нижнюю грань[19, стр. 18]. Такие частично упорядоченные непустые множества являются простейшими алгебраическими системами с определенными на них операциями и отношениями. Сведения об упорядоченных множествах и решетках можно найти в книгах Г. Биркгофа, J1. Комте, А. Г. Куроша, Г. Гретцера, JI. А. Скорняков, где отмечается что, теория решеток (теория структур) является ветвью алгебры и решетку можно определить как универсальную алгебру многообразия[17, 18, 36, 55]. Теоретико-решеточными понятиями пронизана вся современная алгебра, а решетки и группы относятся к числу основных инструментов универсальной алгебры, в частности, строение алгебраических систем обычно наиболее отчетливо выявляются путем анализа связанных с ними решеток (см., например, [36, стр. 178]). Не только алгебра, но и многие другие разделы в математике могут быть сформулированы в теоретико-решеточных понятиях, систематическое использование которых унифицирует и упрощает их рассмотрение[87]. Так книга М. Айгнера[13] сочетает аналитические и алгебраические методы в комбинаторике и теоретико-множественные и теоретико-структурные (базирующиеся на теории решеток) подходы. Широкий диапазон применения теории решеток в математике и смежных областях продемонстрировал в своей книге Г. Биркгоф [17].

Решетки можно рассматривать и как некоторые конфигурации, то есть конечное множество точек, прямых, плоскостей связанных между собой взаимными инцидентностями, которые могут определяться также как и конечная частичная плоскость[31, 64]. Возможность существования некоторой конфигурации определяется из геометрических и комбинаторных соотношений между количеством точек и прямых и количеством взаимных инцидентностей. Комбинаторными будем называть конфигурации, построенные в соответствии с определенными правилами.

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

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

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

С помощью различных комбинаторных чисел перечисляются некоторые пути на решетках [34, 35, 91], а метод путей в решетках позволяет получать новые комбинаторные результаты [75, 81, 84].

Пути с весами называют взвешенными траекториями. Взвешенные пути в двумерных и многомерных решетках и их комбинаторные приложения изучаются в [21]. Частными случаями взвешенных траекторий являются пути с весами равными единицы, которым посвящена основная часть исследований в данной области[78, 82, 85, 94].

Одной из интерпретаций взвешенных траекторий на решетках являются случайные блуждания, суммарный вес которых, для допустимых шагов в фиксированный момент времени, равен единице (см., например, [30, 56, 62, 68, 92]). Они оказываются полезными, в частности, для описания игровых ситуаций и являются неплохими моделями физических процессов, в частности диффузии частиц[29,71,73,79].

К случайным блужданиям можно отнести и процессы рождения и гибели — случайные процессы с конечным или счетным множествами состояний, протекающими в дискретном или непрерывном времени [8 8]. Он состоит в том, что некоторая система в случайные моменты времени переходит из одного состояния в другое, причем переходы между состояниями происходят скачком, когда наступают некоторые события. Как правило, эти события бывают двух типов: одно из них условно называют рождением некоторого объекта, а второе — гибелью этого объекта. Термин «схема рождения и гибели» заимствован из биологических задач, где состояние популяции определяется числом объектов[27,74].

С помощью процессов рождения и гибели составляются математические модели управления различными процессами, а также модели многих явлений в биологии, физике и других областях [29, 28, 39, 46, 52, 61].

При более широкой постановке задачи на события «рождение» и «гибель» объекта могут накладываться другие события и процессы. Так возникает актуальная проблема моделирования систем с произвольным множеством состояний и другими предположениями о законах распределения случайных величин, отличных от показательного [5 8].

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на XII Байкальской международной конференции (Иркутск, 2001 г.) — Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам её преподавания в вузе (Иркутск, 2003 г.) — VIII международном семинаре «Дискретная математика и её приложения» (Москва, 2004 г.);

Всероссийской конференции «Математика, информатика, управление» посвященной памяти О. В. Васильева, (Иркутск, 2004 г.) — XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс», (Новосибирск, 2005 г.) — XIV Международной конференции «Проблемы теоретической кибернетики», посвященной 80-летию со дня рождения С. В. Яблонского, (Пенза, 2005 г.) — Седьмом Всероссийском симпозиуме по прикладной и промышленной математики (Йошкар-Ола, 2006 г.) — III межвузовской зональной конференции, посвященной памяти профессора Б. А. Бельтюкова, «Математика и проблемы ее преподавания в вузе» (Иркутск, март, 2007 г.).

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

Основное содержание диссертационной работы опубликовано в работах [1−11]. В число указанных работ входят 2 статьи [1,2] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001;2006 гг.», 3 статьи [3−5] в научных сборниках, 5 полных текстов докладов [6−10] в материалах международных и всероссийских конференций. Публикации [3, 7−9] выполнены в нераздельном соавторстве с научным руководителем В. Н. Докиным.

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

Список литературы

содержит 98 наименований.

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

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

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

Заключение

.