Введение к работе
Актуальность проблемы. Диссертационная работа относится к одному из актуальных разделов дискретной математики - перечислительной комбинаторике Возрастающее значение комбинаторного анализа в последние годы связано не только с обновлением аппарата, но и с расширением самого предмета исследований Комбинаторные методы с успехом используются в таких разделах математики, как теория чисел, алгебра, теория вероятности, геометрия, теория графов, а также имеют много интересных и актуальных приложений в психологии, медицине, космической технике, радиосвязи и т д
Перечислительная комбинаторика является наиболее развитой ветвью современного комбинаторного анализа Эффективным средством решения перечислительных комбинаторных задач был и остается метод производящих функций Современное развитие комбинаторного анализа тесно связано с использованием данного метода, что намного сокращает обьем необходимых преобразований, позволяет унифицировать многие результаты и тем самым дает возможность охватить значительно больший круг вопросов
Настоящая диссертационная работа посвящена разработке методов исследования взвешенных траекторий на решетках, которые основаны на применении комбинаторных чисел, являющихся элементами обобщенных треугольников и пирамид Паскаля
Изучаемые в работе решетки рассматриваются с точки зрения алгоритмов их построения на основе информации о внутренней струкіуре
Одной из таких структур является так называемый «арифметический треугольник», в настоящее время известный как треугольник Паскаля Его часто выписывают в виде равнобедренного треугольника, в котором по боковым сторонам стоят единицы, а каждое из остальных чисел равно сумме двух чисел, стоящих над ним слева и справа в предшествующей строке Треуголь^ ник Паскаля обладает многими замечательными арифметическими и геометрическими свойствами, а также большой областью приложения
Другой такой структурой обладает треугольная схема, предложенная В Н Докипым и М Л Платоновым, ее элементами являются обобщенные
числа Слирлинга первого рода В"к и второго рода А"к, удовлетворяющие следующим рекуррентным соотношениям, соответственно
в; = в;:\+«„_ а"'1 и 4 = а;:\ + /мг1
Также дополнительно полагают, что А"п=В"п-\, /7 = 0,о, Л = =0, если тіп(иД,и-) <0
Треугольные схемы составленные из чисел ВІ и А"к называются В - и Л-треугольниками, соответственно Они являются частными случаями обобщенного треугольника Паскаля, элементы которого удовлетворяют следующему рекуррентному соотношению
V{n,k) = P„kAV{n-\,k-\) + a^kV{n-\,k)
с граничными условиями V(0,0)-V0, V(n,k) = 0, если тт(п,к,п-к) <0 Число К(0,0), стоящее в вершине обобщенного треугольника Паскаля, оговаривается особо (во многих случаях его можно принять за единицу) Величины апк иД( называются весовыми коэффициентами
Еще одной такой структурой является пирамида Паскаля, о которой по-видимому одним из первых упоминает Е В Rosentahl Пирамида Паскаля -это трехгранный пирамидальный массив, в n-сечении (треугольнике) параллельном основанию, которого располагаются триномиальные коэффициенты
f п\
Обобщением данной структуры является обобщенная пирамида Пас-
каля, предложенная
О В Кузьминым, которая является трехгранным пирамидальным массивом,
а его элементы удовлетворяют следующему рекуррентному соотношению
V(n,kJ) = а„ k.XJV{n - U -1,/) + Д,Л/_,И(л - \,кJ - О + Г„,к >У{п -1,*.0 с
граничными условиями У(0,О,0) = У0, У(п,к,1) = 0, если
mm(n,k,l,n-k-l)<0 Число У0, стоящее в вершине (нулевом слое) обобщенной пирамиды Паскаля, оговаривается особо (во многих случаях
можно считать V0 = 1) Величины ап к t, fi„ и и уп к h фигурирующие в рекуррентном соотношении, называют весовыми коэффициентами
Важными частными случаями обобщенной пирамиды Паскаля являются А - и В -пирамиды, в каждом сечении которых расположены обобщенные триномиальные коэффициенты первого В"/ и второго А"і рода, удовлетворяющие следующим рекуррентным соотношениям, соответственно
и B"kJ = a„_xBlti + Pn-xBV-x + Гп-Кі
Также дополнительно полагают, что Лоо = 2?о,о=1> А"к ,=B"kl-Q, если
тт{п,к,1,п-к-1)<0
Различным арифметическим треугольникам и пирамидам комбинаторного происхождении, которые предлагают многие авторы (Б А Бондаренко С Гамберг, Т Грин, В Н Докин, О В Кузьмин, Д Кнут, М Л Платонов, Д Прист, Дж Риордан, Д Роджерс, С Смит, Р Стенли, ТГ Тюрнева, В А Успенский, В Хоггат, Л Шапиро и др ), приписывают или можно приписать внутреннюю структуру
Арифметическим треугольникам и пирамидам в зависимости от их внутренней структуры можно приписать геометрическую интерпретацию в виде решеток
В данной диссертационной работе решетки рассматриваются как геометрические схемы, представляющие собой системы линий (на которых могут задаваться при необходимости определенные веса), соединяющие какие-то заданные точки, что придает рассматриваемым дискретным системам наглядность
Одной из задач на решетках является перечисление траекторий между фиксированными точками
Под траекториями обычно понимаются пути, начинающиеся в начале координат, являющиеся последовательностями точек целочисленной решетки плоскости с некоторыми ограничениями на приращение координат при
переходе от одной точки к следующей Как можно видеть, эти способы в своей сущности имеют комбинаторную природу, что и позволяет использовать комбинаторные числа для перечисления путей на решетках
Одной из интерпретаций взвешенных траекторий на решетках являются случайные блуждания, суммарный вес которых, для допустимых шагов в фиксированный момент времени, равен единице Они оказываются полезными, в частности, для описания игровых ситуаций и являются неплохими моделями физических процессов, в частности диффузии частиц
К случайным блужданиям можно отнести и процессы рождения и гибели - случайные процессы с конечным или счетным множествами состояний, протекающими в дискретном или непрерывном времени
С помощью процессов рождения и гибели составляются математические модели управления различными процессами, а также модели многих явлений в биологии, физике и других областях
При более широкой постановке задачи на события «рождение» и «гибель» объекта могут накладываться другие события и процессы Так возникает актуальная проблема моделирования систем с произвольным множеством состояний и другими предположениями о законах распределения случайных величин, отличных от показательного
Основная цель работы состоит в разработке методов описания и исследования различных классов взвешенных траекторий на решетках с помощью комбинаторных чисел, являющихся элементами обобщенных треугольников и пирамид Паскаля
Общая методика исследования основана на применении аппарата производящих функций и комбинаторных чисел, а именно обобщенных чисел Стирлинга и обобщенных триномиальных коэффициентов Применение производящих функций позволило расширить класс исследованных траекторий, а использование комбинаторных чисел позволило сделать некоторые обобщения Подход к ряду исследований основан на идеи рекуррентности и индуктивном скачке Научные положения и выводы, сформулированные в диссертации, обоснованы и базируются на доказанных в работе утверждениях
Научная новизна. Введены и изучены новые объекты комбинаторной структуры, рассмотрены вопросы перечисления взвешенных путей на решетках с ограничениями на приращение координат
Основные результаты, выносимые на защиту
-
Впервые разработан метод, позволяющий сводить изучение взвешенных траекторий на решетках с уровнями к соответствующим траекториям без уровней
-
Построен новый алгоритм перечисления взвешенных путей на решетках с помощью комбинаторных чисел
-
С помощью разработанного алгоритма перечисления взвешенных путей исследованы соответствующие случайные блуждания, для которых доказан ряд теорем
-
Обоснован и получил дальнейшее развитие метод «вложенных шагов» для схем типа треугольника Паскаля, который исполыован при исследованиях взвешенных траекторий на решетках
Личный вклад автора состоит в описании различных взвешенных траекторий на решетках с помощью элементов треугольника и пирамиды Паскаля, а также применении полученных результатов к исследованию соответствующих случайных блужданий
Все основные результаты, включенные в диссертацию, являются новыми и получены лично автором
Теоретическая и практическая значимость Полученные в диссертации результаты представляют интерес для развития теории комбинаторных чисел и исследования взвешенных траекторий на решетках
Исследования, проводимые в рамках диссертационной работы, были поддержаны грантом Рособразования «Развитие научно-исследовательской работы молодых преподавателей и научных сотрудников, аспирантов и студентов» (2005 г)
Отдельные разделы диссертации используются в учебном процессе кафедры теории вероятностей и дискретной математики Иркутского государственного университета (чтение спецкурсов по теории массового
обслуживания и перечислительной комбинаторике, выполнение
студенческих курсовых и дипломных работ)
Апробация работы Результаты диссертации докладывались на XII Байкальской международной конференции (Иркутск, 2001 г), Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, 2003 г), VIII международном семинаре «Дискретная математика и ее приложения» (Москва, 2004 г), Всероссийской конференции '(Математика, информатика, управление» посвященной памяти О В Васильева, (Иркутск, 2004 г), XLIII Международной научной студенческой конференции "Студент и научно-технический прогресс", (Новосибирск, 2005 г), XIV Международной конференции "Проблемы теоретической кибернетики", посвященной 80-летию со дня рождения С В Яблонского, (Пенза, 2005 г), Седьмом Всероссийском симпозиуме по прикладной и промышленной математики (Йошкар-Ола, 2006 г), III межвузовской зональной конференции, посвященной памяти профессора Б А Бельтюкова, «Математика и проблемы ее преподавания в вузе» (Иркутск, март, 2007 г)
Кроме того, материалы диссертации докладывались и обсуждались на семинарах кафедры теории вероятностей и дискретной математики Иркутского государственного университета (2001 -2007гг)
Основное содержание диссертационной работы опубликовано в работах [1-Ю] В число указанных работ входят 2 статьи [1,2] из "Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001-2006 гг", 3 статьи [3-5] в научных сборниках, 5 полных текстов докладов [6-Ю] в материалах международных и всероссийских конференций Публикации [3, 7-9] выполнены в нераздельном соавторстве с научным руководителем В Н Докиным
Структура и объем рабо і ы. Диссертация состоит из введения, трех глав, заключения и списка литературы Общий объем диссертации составляет 130 страниц Список литературы содержит 98 наименований
