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

Соловьева, Людмила Александровна

Комбинаторные числа и взвешенные траектории на решетках тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Соловьева, Людмила Александровна АВТОР

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

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

2007 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Комбинаторные числа и взвешенные траектории на решетках»

Автореферат диссертации на тему "Комбинаторные числа и взвешенные траектории на решетках"

На правах рукописи

СОЛОВЬЕВА Людмила Александровна

КОМБИНАТОРНЫЕ ЧИСЛА И ВЗВЕШЕННЫЕ ТРАЕКТОРИИ НА РЕШЁТКАХ

01 01 09 - дискретная математика

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

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

□ОЗ176332

Иркутск - 2007

Работа выполнена в Иркутском государственном университете

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

Докин Валерий Николаевич

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

Носков Сергей Иванович

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

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

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

Защита состоится 9 ноября 2007 г. в 10.00 на заседании диссертационного совета Д 212 074 01 при Иркутском государственном университете по адресу 664003, г Иркутск, ул К Маркса, 1, ИМЭИ ИГУ

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

Автореферат разослан 5 октября 2007 г

Ученый секретарь диссертационного совета,

канд физ -мат наук, доцент М А Аргучинцева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Диссертационная работа относится к одному из актуальных разделов дискретной математики - перечислительной комбинаторике Возрастающее значение комбинаторного анализа в последние годы связано не только с обновлением аппарата, но и с расширением самого предмета исследований Комбинаторные методы с успехом используются в таких разделах математики, как теория чисел, алгебра, теория вероятности, геометрия, теория графов, а также имеют много интересных и актуальных приложений в психологии, медицине, космической технике, радиосвязи и т д

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

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

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

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

Другой такой структурой обладает треугольная схема, предложенная В Н Докиным и М Л Платоновым, ее элементами являются обобщенные

числа Слирлинга первого рода В"к и второго рода А"к, удовлетворяющие следующим рекуррентным соотношениям, соответственно

в" = в;:\+«„_А"'1« 4 = а;:\ +

Также дополнительно полагают, что А"п = В" =1, п = 0,сс, = 0, если

т1п(иД,и-&) < О

Треугольные схемы составленные из чисел и Л" называются В - и Л -треугольниками, соответственно Они являются частными случаями обобщенного треугольника Паскаля, элементы которого удовлетворяют следующему рекуррентному соотношению

У{п,к) = /3„ кАУ{п - \,к -1) + ап>кУ(П -\,к)

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

Еще одной такой структурой является пирамида Паскаля, о которой по-видимому одним из первых упоминает Е В ЯоБейаЫ Пирамида Паскаля -это трехгранный пирамидальный массив, в п-сечении (треугольнике) параллельном основанию, которого располагаются триномиальные коэффициенты

( п ^

Обобщением данной структуры является обобщенная пирамида Пас-

каля, предложенная

О В Кузьминым, которая является трехгранным пирамидальным массивом, а его элементы удовлетворяют следующему рекуррентному соотношению У(ПХП = ап -1,к -1,/) + Д,лмИ(и -1,*,/ -1) + упЛ ,Г(п -1,*,/) с

граничными условиями V (0,0,0) = У0, У(п,к,1) = 0, если гтп(п,к,1,п - к -1) <0 Число У0, стоящее в вершине (нулевом слое) обобщенной пирамиды Паскаля, оговаривается особо (во многих случаях

можно считать У0 = 1) Величины ап к ¡, Д, к , и уп к ¡, фигурирующие в рекуррентном соотношении, называют весовыми коэффициентами

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

и В"и = а^ВГ-Ь + /?„_ А",7и + Г ж'

Также дополнительно полагают, что Лд0 = вЦ10=1, А"к,=В"к1-0, если тт{п,к,1,п-к-1)<0

Различным арифметическим треугольникам и пирамидам комбинаторного происхождении, которые предлагают многие авторы (Б А Бондаренко С Гамберг, Т Грин, В Н Докин, О В Кузьмин, Д Кнут, М Л Платонов, Д Прист, Дж Риордан, Д Роджерс, С Смит, Р Стенли, ТГ Тюрнева, В А Успенский, В Хоггат, Л Шапиро и др ), приписывают или можно приписать внутреннюю структуру

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

обслуживания и перечислительной комбинаторике, выполнение студенческих курсовых и дипломных работ)

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

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

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

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

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

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

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

Пусть м0, , ип - такая последовательность точек из 2 , что 1)

2) «и+| ="А +(1.0. ге{г -1<1<т}, / >0,ОТ>0,0</с<и, Тогда щ, , ип называется путем с началом г/0 ~{а,/3) и концом ип = (п,к) и обозначается л(а,Р,п,к) Если -1<1<т}, то (г) на-

зывается шагом на высоте ; , а (г)( называется ! шагом Обозначим за вес шага (г)

В дальнейшем рассматриваются £/пк{а,Р,\\'(г) ) - множества траекторий л(а,/3, п,к) с весами и^г) шага

В параграфе 1.2. исследуются взвешенные пути ип к (0,0,Н'(г)у) с г = {0,1}, где для различных значений г каждый вес и{г)/ принимает только

одно из значений ОС или Р] и ип^к(0,т,м/(г) ^ с г = {0,-1}, где для различных значений г каждый вес принимает одно из значений или

Обозначим №п(к) и \¥п{к,т) - число траекторий ипк(0,0,>у(г);) и 1]п к(0,т,\И(г) ), соответственно

В предложениях 1.1 и 1.2 сформулированы и доказаны рекуррентные соотношения для Vп к (0,0, ) и Vп к{0,т,Щг)1), соответственно Обозначим

Г 1, если I = 0,

ДН у-

[«0 если I =\,п

Г 1, если / = 0,

П = ^ _1_

И ■*')л-| | ~ ~ ~ 1

К если / = 1,и'

тогда имеют место

Утверждение 1,1. Для IVп (к) справедливо соотношение

я,,

где и = 0, оо, к = 0,п, - обобщенные числа Стирлинга второго рода, построенные на базе {Д

Утверждение 1,2. Для \Уп{к,т) справедливо соотношение

где я = 0, оо, к = 0,п Л " - обобщенные числа Стирлинга второго рода, (Я и

построенные на базе | д

Пусгь л(а,р,п,к) - траектория, имеющая начало в точке с координатами (а,Р) и конец в точке с координатами (п,к), тогда я(0,0,п,к) и яг(0,т,п,£) - траектории, задаваемые путями (0,0, ) с г = {0,1} и и„¿($),т,Щг) ) с /" = {0,-1} соответственно Решеточным многоугольником {я

(0,0 ,п,к),я{0,т,п,к)) назовем замкнутую фигуру между траекториями л"(0,0,п,к) и я(0,т,п,к) и осью ординат, имеющими только одну общую точку (п,к) Обозначим я „^ (гп)-\(я(0,0, п, к), я(0,т,п,

В предложении 1 3 сформулировано и доказано рекуррентное соотношение ДЛЯ 71 п к (ш)

Теорема 1.1. Для ппк{т) справедлива формула

*я,*0и)=»;(*)

7я-1 А 11 1 7"-1

лт-А-1 , лк-\ Ак-1

п-1

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

В параграфе 1.3 исследуются взвешенные пути 1/пк (0,0,0,и>(г)с ге {(-1,1),(0,0),(1,1)}, где для различных значений г каждый вес и (г) принимает только одно из значений ау, /3] и у} и и„ к</ (0,0,0, \й(г) ) с ге {(-1,1),(1,1)}, где для различных значений г каждый вес принимает только одно из значений а] и ¡¡} Обозначим 1¥п(к,/) и IV / (к) - число всех траекторий V пк(0,0,0, н(г)у) и Vп (0,0,0, й(г) /), соответственно

В предложениях 1.4 и 1 5 сформулированы и доказаны рекуррентные соотношения для (0,0,0, Мг) и 11пк ; (0,0,0, и>(/))), соответственно Символом Я, обозначим

где А" - обобщенные числа Стерлинга второго рода, построенные на базе

Лемма 1 1. Для 1У„{к,]) и №у(к) справедливо равенс1во

Г„ (£,;) = л;

Лемма 1 2. Для справедливо следующее соошошение

где В"к - обобщенные числа Стерлинга второго рода, построенные на ба-( чА

а,

зеfr , 7 = 0,и и k = -j,j {"') 1=0

Утверждение 1.3. Для Wn(k,j) справедливо следующее равенство W.{k,j)=A' BU, Л,,

где п = 0,со, j = 0, п и k = -j,j

Исследуются взвешенные пути Unk{0,0, w(r),) t г = {-1,0,1}, где для различных значений г каждый вес w(r), принимает только одно из значений а, или Д

В предложении 1.6 сформулировано и доказано рекуррентное соотношение для Un k (0,0, w(r)()

f 1, если i = 0,

Пусть д •/?,_,,если г = \ji

Утверждение 1.4. Для Wn(j) имеет место соотношение

K(j)=nn Z

/=о

n-k s n-j-k

2 )

j п

а,

где п = 0,со и у ~-п,п, В" - построены на базе < — >

IА ] 1=0

В параграфе 1 4 исследуются взвешенные пути IIпк } (0,0,0, w{r)J ) с г е |{(к,1), где у - -1,т), (0,0)}, где для различных значений г каждый вес

и-(г) принимает только одно из значении и р} и

(0,0,0,и'(г);) с г е {(к,1),где V = -/,«}, 1де для различных значений г

каждый вес £(;) принимает только одно из значений ^ Обозначим

1Уп(ки - число всех траекторий II п к (0,0,0, ы(г)^ и

(0,0,0, ), соответственно

В предложениях 1.7 и 1.8 сформулированы и доказаны рекуррентные соотношения для (0,0,0, и IIп к ; (0,0,0, г) /), соответственно

где А" - обобщенные числа Стирлинга второго рода, построенные на базе

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

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

1) сведение задачи о взвешенных траекториях к задаче о частичных суммах,

2) составления соответствующих производящих функций,

3) применение аппарата обобщенных чисел Стирлинга,

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

С помощью данного алгоритма исследованы взвешенные траектории ипк( 0,0, и^г),) с I е {-1,0,1}, где для различных значений г каждый вес и (г), принимает только одно из значений а1 или Д И найдено число таких взвешенных пугей

В параграфе 2.2. исследуются взвешенные пути и„к(0,0,и>(г),) с I е {-2,-1,1,2}, где для различных значений г каждый вес и(г)1 принимает только одно из значений а, или /?,

В предложениях 2.1-2.5 сформулированы и доказаны рекуррентные соотношения для V„ ^ (0,0, )

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

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

В параграфе 2.3. исследуются взвешенные пути £/и ¿(0,0, и^г),) с /-£{-2,-1,0,1,2}, где для различных значений г каждый вес н>(г)1 принимает ровно одно из значений а, или Д

В предложениях 2.6-2.10 сформулированы и доказаны рекуррентные соотношения для £/„ ¿(0,0, и{г),)

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

Обозначим Л'„ = +¿1 + +£„_], где ^ , ] = 0,оо последовательность независимых случайных величин каждая из которых принимает только одно из следующих значений {-2,-1,0,1,2}

Пусть Сп^) - производящая функция случайной величины

п - дисперсия случайной величины Теорема 2.2. При п -» со

где 1 №

Теорема 2.4. Если Еп —> со, при п —> со, то

-fä Р„{к)—¿=

sup

0<,к<п

1 ТЕ

В параграфе 2 4 исследуются взвешенные пути Unk (0,0, w(r)/) с cej© ü) = - m,/и) и г е {о» а = -т,т,аФ 0}, где для различных значений г каждый вес w(r), принимает только одно из значений а, или Д

В предложениях 2.11-2.12 сформулированы и доказаны рекуррентные соотношения для [/„ ¿(0,0, м^г),)

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

В параграфе 3.1 приводятся необходимые сведения по обобщенным триномиальным коэффициентам и исследуются взвешенные пути t/n ¿(ОДм^г),) с г е {—1,0,1}, где для различных значений г каждый вес w(r), принимает только одно из значений а}, ß] и у j

В предложении 3.1 сформулированы и доказаны рекуррентные соотношения для Unk(0,0, w(r)J Также найдено число рассматриваемых траекторий

В параграфе 3.2 С помощью алгоритма перечисления путей комбинаторными числами исследуются взвешенные пути Uп к (0,0, w{r)t) с г е{-2,-1,0,1,2}, где для различных значений г каждый вес w(r), принимает только одно из значений а , ß} и уj

В предложениях 3.2-3.3 сформулированы и доказаны рекуррентные соотношения для ипк{ 0,0,и>(>)7)

В параграфе 3.3 исследуются взвешенные траектории Vп ¿(0,0, ^'(г),) с г е {¿у со = -т,т\, где для различных значений г каждый вес и>(г), =а\г\ ге{со со = -т,т\ Обозначим Nп (к) - число рассматриваемых траекторий

Рассматриваются взвешенные траектории 1!п ¿(ОДи^г),) с ге{-1,1}, обозначим (к) - число рассматриваемых траекторий, для которых справедливо

К (к) = !¥„_, (к + 1)/?„ч + (к - \)а„_х,

с граничными условиями 1У0(0) = 1, а при \к\ > п ¡¥п(к) = 0

т-1 _

Обозначим П}™1+т - Х\Ргтк+у, при к = 0,оо 5" О)- обобщенные

у=й

числа Стерлинга первого рода с фиксированным началом, строящиеся на базе {а,и удовлетворяющие рекуррентному соотношению вида

для которых справедливы условия В" (5) = 1, если ] В" (5) = 0, если )>П

Из идеи «вложенных шагов» следует

Утверждение 3.1. Для чисел №п(к) и IVп(к) справедливо следующее равенство

Мп(к) = 1¥2тп(2тк) Тогда веса шагов удовлетворяют следующим выражениям

а^=П22:кк+тВ2т-Л2тк),

при г е {¿у а = -т,т\ и В" (я) строятся на базе

Теорема 3.1. Для Nn(к) справедливо равенство

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

Соискатель выражает благодарность, научному руководителю, доценту В H Докину и заведующему кафедрой теории вероятностей и дискретной математики ИГУ, профессору О В Кузьмину за проявленное внимание и полезные замечания, которые способствовали улучшению стиля изложения и качества работы

Основные публикации по теме диссертации

1 Соловьева JI А Случайные блуждания и связанные с ними задачи суммирования случайных величин / Л А Соловьева // Вестник Бурятского университета Сер 13 Математика и информатика - Улан-Удэ Изд-во Бурятского ун-та, 2005 -Вып 2 - С 85-91

2 Соловьева Л А Комбинаторные числа в задачах симметричных случайных блужданий / Л А Соловьева // Обозрение прикладной и промышленной математики -2006 -Т 13, вып 5 - С 839-840

3 Соловьева Л А Описание симметричных случайных блужданий с произвольным нечетным числом переходов / Л А Соловьева, В H Докин // Комбинаторные и вероятностные задачи дискретной математики - Иркутск Изд-во Иркут гос ун-та, 2006 - С 37-42

4 Соловьева Л А Обобщенные триномиальные коэффициенты в задачах случайных блужданий / Л А Соловьева И Комбинаторные и вероятностные задачи дискретной математики - Иркутск Изд-во Иркут гос ун-та, 2006 - С 114-121

5 Попова (Соловьева) Л А Случайные блуждания на плоскости / Л А Попова (Соловьева) // Студент и научно-технический прогресс докл студ иасп - Иркутск Изд-во Иркут ун-та, 1999 - С 80-81

6 Попова (Соловьева) Л А Симметричные блуждания на плоскости / Л А Попова (Соловьева) // Труды XII Байкальской международной конфе-

ренции Иркутск, 24 июня - 1 июля, 2001 Т 5 Дискретная математика -Иркутск, 2001 -С 130-134

7 Соловьева JI А Симметричные случайные блуждания на плоскости с четным числом переходных вероятностей / JI А Соловьева, В H До-кин // Труды Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе - Иркутск Изд-во Иркут гос пед ун-та, 2003 - С 155-156

8 Соловьева Л А Суммирование независимых случайных величин в задачах симметричных блужданий / Л А Соловьева, В H Докин // Материалы VIII Международного семинара «Дискретная математика и ее приложения» 2-6 февраля 2004 г -М Изд-во МГУ, 2004 - С 176-179

9 Соловьева Л А Случайные блуждания на плоскости с четырьмя переходными вероятностями / Л А Соловьева, В H Докин // Труды Всероссийской конференции «Математика, информатика, управление» - Иркутск, 2004 - С 104-107

10 Соловьева Л А Обобщенные числа Стерлинга в описании случайных блужданий / Л А Соловьева // Материалы XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» Математика - Новосибирск, 2005 - С 225-226

Подписано к печати 01 102007 Формаг60х84 1/16 Уел печ л 1,0 Заказ 77 Тираж 100 экз

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

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

Введение.

Глава 1. Элементы треугольника Паскаля и взвешенные траектории на решетках.

1.1. Основные понятия комбинаторики путей и обобщенные числа Стерлинга.

1.2. Взвешенные траектории с двумя переходными шагами.

1.3. Взвешенные траектории с тремя переходными шагами.

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

Глава 2. Производящие функции и взвешенные траектории на решетках.

2.1. Производящие функции.

2. 2 Взвешенные траектории с четырьмя переходными шагами.

2. 3 Взвешенные траектории с пятью переходными шагами.

2. 4. Симметричные взвешенные траектории с "произвольным" числом переходных шагов.

Глава. 3 Обобщенные пирамиды Паскаля и взвешенные траектории на решетках.

3.1 Обобщенные триномиальные коэффициенты и взвешенные траектории на решетках.

3.2 Два вида взвешенных траекторий.

3.3. Треугольник Паскаля и взвешенные траектории на решетках.

Введение диссертация по математике, на тему "Комбинаторные числа и взвешенные траектории на решетках"

Широкое использование дискретной математики в различных сферах человеческой деятельности вызывает интерес к данному разделу математики, а так же стимулирует ее постоянное развитие. Дискретная математика объединяет многие теории, использующиеся в исследовании разнообразных моделей дискретного принципа действия. В современной дискретной математике в основном выделяют следующие разделы: математическая логика, комбинаторика, теория графов, теория множеств, теория алгоритмов и вычислений, которым посвящено множество литературы (см., например, [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], её элементами являются обобщенные числа Стирлинга первого рода и второго рода А^, удовлетворяющие следующим рекуррентным соотношениям, соответственно

Также дополнительно полагают, что Апп = В„ = 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„-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].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Соловьева, Людмила Александровна, Иркутск

1. Соловьева J1. А. Комбинаторные числа в задачах симметричных случайных блужданий / Л. А. Соловьева Л. А. // Обозрение прикладной и промышленной математики. - 2006. - Том 13. - Вып. 5. - С. 839-840.

2. Соловьева Л. А. Случайные блуждания и связанные с ними задачи суммирования случайных величин / Л. А. Соловьева Л. А. // Вестник Бурятского университета. Серия 13: Математика и информатика. Улан-Удэ: Изд-во Бурятского ун-та, 2005. - Вып. 2. - С. 85-91.

3. Соловьева Л. А. Описание симметричных случайных блужданий с произвольным нечетным числом переходов / Л. А. Соловьева, В.Н. Докин // Комбинаторные и вероятностные задачи дискретной математики. Иркутск: Изд-во Иркут. гос. ун-та, 2006. - С. 37-42.

4. Соловьева Л. А. Обобщенные триномиальные коэффициенты в задачах случайных блужданий / Л. А. Соловьева Л. А. // Комбинаторные и вероятностные задачи дискретной математики. Иркутск: Изд-во Иркут. гос. ун-та, 2006. - С. 114-121.

5. Соловьева Л. А. Обобщенные числа Стирлинга в описании случайных блужданий / Л. А. Соловьева // Материалы XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс»: Математика. Новосибирск, 2005. - С. 225-226.

6. Соловьева Л. А. Случайные блуждания на плоскости с четырьмя переходными вероятностями / Л. А. Соловьева, В.Н. Докин // Труды Всероссийской конференции «Математика,информатика,управление».- Иркутск, 2004.-С. 104-107.

7. Попова (Соловьева) JI. А. Симметричные блуждания на плоскости / JL А. Попова (Соловьева) // Труды XII Байкальской международной конференции. Иркутск, 24 июня 1 июля, 2001. Том 5: Дискретная математика. -Иркутск, 2001.-С. 130-134.

8. Попова (Соловьева) Л. А. Случайные блуждания на плоскости / Л. А. Попова (Соловьева) // Студент и научно-технический прогресс: тез. докл. студ. и асп. Иркутск: Изд-во Иркут. ун-та, 1999. - С. 80-81.

9. Айгнер М. Комбинаторная теория \ пер. с англ. В. В. Ермакова, В. Н. Лямина \ под ред. Г. П. Гаврилова. М.: Мир, 1982. - 558 с.

10. Андерсон Джеймс А. Дискретная математика и комбинаторика: пер. с англ. М.: Изд. дом «Вильяме», 2003. - 957 с.

11. Асимптотические и перечислительные задачи комбинаторного анализа : Сб. науч. тр. Иркутск : Иркут. гос. ун-т, 1997. - 144 с.

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

13. Биркгоф Г. Теория решеток : пер. с англ. М. : Наука. Гл. ред. физ.-мат. лит., 1984.-568 с.

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

15. Гретцер Г. Общая теория решеток: пер. с. англ. / под ред. Д. М. Смирнова. -М.: Мир, 1981. 456 с.

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

17. Гульден Я. Перечислительная комбинаторика: пер. с англ. / Я. Гульден, Д. Джексон / Под ред. В. Е. Тараканова. М. : Наука. Гл. ред. Физ.-мат. Лит., 1990.-504 с.

18. Асимптотические и перечислительные задачи комбинаторного анализа: Сб. науч. тр. Иркутск: Иркут. Ун-т, 1997. -144 с.

19. Докин В. Н. О треугольной схеме развития популяции // Исследования по геомагнетизму, аэрономии и физике Солнца. М. : Наука, 1977. -Вып. 41.-С. 104-106.

20. Докин В. Н., Жуков В. Д., Колокольникова Н. А., Кузьмин О. В., Платонов М. Л. Комбинаторные числа и полиномы в моделях дискретных распределений. Иркутск: Изд-во Иркут. гос. ун-та, 1990. - 206 с.

21. Егорычев Г. П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука. Сиб. отд-ние, 1977. - 285 с.

22. Зверев Н. В. Векторная U( 1) модель фермионов на решетке и алгоритмы её исследования. М.: Прометей, 2003. - 111 с.

23. Зеленцов Б.П. Математические модели на основе процесса размножения и гибели объектов // СОЖ, 2001. Т. 7, № 6. - р. 92-97.

24. Карелова О. Л., Банько М. А. Применение Марковских цепей для прогнозирования демографической ситуации в мире // Математическое моделирование, 2006. 18, № 2. - С. 43-50

25. Карлин С. Основы теории случайных процессов : пер. с англ. В. В. Калашникова / Под ред И. Н. Коваленко. М.: Мир, 1971. - 53 6 с.

26. Колчин А. В. Предельные теоремы для обобщенной схемы размещения // Дискрет, мат., 2003. 15, № 4. - С. 148-157.

27. Колчин В. Ф. Случайные графы 2. изд. - М.: ФИЗМАТЛИТ, 2004. - 255 с.

28. Ежова Л. Н., Маркова Е. В. Планирование и анализ многофакторных экспериментов на основе комбинаторных схем. Иркутск: Изд-во Иркут. ун-та, 1993. -230 с.

29. Кофман А. Введение в прикладную комбинаторику / пер. с фр. В. П. Мя-кишева, В. Е. Тараканова /под ред. Б. А. Севастьянова. М.: Наука, 1975. - 480 с.

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

31. Кузьмин О. В., Лобах М. В. Комбинаторные числа и структуры решеток // Математика в вузе: Тр. междунар. науч.-метод. конф., Санкт-Петербург, сент. 2004. Спб.: ПГУПС, 2004. - С. 163-165.

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

33. Курош А. Г. Лекции по общей алгебре : Учебник. СПб.: Изд. «Лань», 2005.-560 с.

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

35. Лозвану Д. Д. Экстремально-комбинаторные задачи и алгоритмы их решения / под ред. доктора физ-мат. наук В. А. Трубина. Кишинев: «Штиин-ца», 1991.-222 с.

36. Лубенцова В. С., Ефремов А. Решение задачи определения вместимости контейнерного терминала с использованием модели «гибели и размножения» // В. Вестн. Самар. гос. техн. ун-та., 2005. № 38. - С. 155-158.

37. Макдональд И. Симметрические функции многочлены Холла / Пер. с англ. А. В. Зелевинского. М.: Мир, 1985. - 222 с.

38. Оре О. Графы и их применения : пер. с англ. / Под ред. и с предисл. И. М. Яглома. М.: КомКнига, 2006. - 168 с.

39. Перечислительные задачи комбинаторного анализа: Сб. переводов / Пер. с англ. под ред. Г. П. Гаврилова. М.: Мир, 1979. - 363 с.

40. Петров В. В. Предельные теоремы для сумм независимых случайных величин. М.: Наука. Гл. ред. физ.-мат. лит., 1978. - 320 с.

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

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

43. Платонов М. Л., Докин В. Н. Треугольная схема развития популяции // Исследования по геомагнетизму, аэрономии и физике Солнца. М. : Наука, 1975. - Вып. 35. - С. 26-31.

44. Проблемы комбинаторного анализа: Сб. статей / Перевод с англ. И фр. А. М. Ревяуина, Б. С. Стечкина; Под ред. К. А. Рыбникова. М.: Мир, 1980. - 250 с.

45. Райзер Г. Дж. Комбинаторная математика / пер. с англ. К. А. Рыбникова.-М. : 1966.- 154 с.

46. Риордан Дж. Введение в комбинаторный анализ / пер. с англ. Л. Е. Садовского, под ред. Л. Я. Куликова. М.: Издат. иностр. лит., 1963. - 288 с.

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

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

49. Рыков В. В. Обобщенные процессы рождения и гибели и их применение к моделям старения // Автомат, и телемех., 2006. -№ 3. С. 103-120.

50. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Изд-во МЦНМО, 2004. - 321 с.

51. Сачков В. Н. Комбинаторные методы дискретной математики. М. : Наука, 1977.-320 с.

52. Скорняков Л. А. Элементы теории структур. М. : Наука, Гл. ред. физ.-мат. лит., 1970. - 148 с.

53. Спицер Ф. Принципы случайного блуждания / Перевод с англ. О. В. Вискова и Е. В. Чепурина; Под ред. Э. Л. Пресмана и Ю. В. Прохорова. М. : Мир, 1969.-472 с.

54. Стенли Р. Перечислительная комбинаторика : пер. с англ. / Под ред. А. М. Вершина. М.: Мир, 1990. - 440 с.

55. Такач Л. Комбинаторные методы теории случайных процессов / Перевод с англ. В. А. Малышева; Под ред. А. Д. Соловьева. М. : Мир, 1971.-264 с.

56. Успенский В. А. Треугольник Паскаля. 2-е изд., доп. - М. : Наука, 1979.-48 с.

57. Устинов А. В. Об одном обобщении чисел Стирлинга // Чебышев. сб., 2002.-3, №2.-р. 107-122.

58. Федосеев В. Н. Решение вероятностных задач. М. : Авангард, 2004.- 112 с.

59. Феллер В. Введение в теорию вероятностей и ее приложения. М. : Мир, 1984.-Т. 1.-528 с.

60. Хаггарти Р. Дискретная математика для программистов. М : Техносфера, 2004.-320 с.

61. Харари Ф. Теория графов / Пер. с англ., под ред. Г. П. Гаврилова. -М.: Едиториал УРСС, 2003. 296 с.

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

63. Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике / перевод с англ. Б. С. Стечкина; с предисл. Ю. В. Прохорова. М. : Мир, 1976.- 131 с.

64. Яблонский С. В. Введение в дискретную математику. / Под ред. В. А. Садовничего. 3-е изд., стер. - М.: Высш. шк.; 2001. -384 с.

65. Alili S. Persistent random walks in stationary environment // Statist. Phys., 1999. 94, № 3-4. - p. 469-494.

66. Alon Noga. Problems and results in extremal combinatorics I // Discrete Math., 2003.-273, № 1-3.-p. 31-53.

67. Ando Shiro, Sato Daihachiro. On GCD-LCM duality between Pascal's pyramid and the modified Pascal pyramid//Fibonacci Quart., 2005.-43, № 1. -p. 15-21.

68. Balea P., Linca' G. H. A Markov process for chemical reactions // Sci. Bull. A. "Politechn." Univ. Bucharest., 1999. 61, № 1-2. - p. 113-121.

69. Bier Thomas, Padmanabchan Peter Suresh. Some formulas for generalized Stirling numbers // Ars. comb., 2005. 76. - p. 65-82.

70. Bohm W. The correlated random walk with boundaries: a combinatorial solution // Appl. Probab., 2000. 37, № 2. - p. 470-479.

71. Bose A., Kaj I. A scaling limit process for the age-reproduction structure in a Markov population // Markov Process. And Relat. Fields., 2000. 6, № 3.-p. 397-428.

72. Butzer Paul L., Kilbas Anatoly A., Trujillo Juan. Stirling functions of the second king in the setting of difference and fractional calculus // J. Numer. Funct. Anal, and Optimiz., 2003. 24, № 7-8. - p. 673-711.

73. Cheon Gi-Sang, Kim Jin-Soo. Stirling matrix via Pascal matrix // Linear Algebra and Appl., 2001. 329. - p. 49-59.

74. Coker Curtis Enumerating a class of lattice paths // Discrete Math., 2003. -271,№ 1-3.-p. 13-28.

75. Costabile Massimo. A combinatorial approach for pricing Parisian options // Decis. and Econ. Finan., 2002. 25, № 2. - p. 111-125.

76. Csaki E., Csorgo M., Foldes A., Shi Z. Path properties of Cauchy's principal values related to local time // Stud. sci. math, hung., 2001. 38. - p. 149-169.

77. Dress Andreas, Grunewald Stefan, Gutman Ivan, Lepovic' Mirko, Vido-vic' Dus'ica. On the number of walks in trees // MATCH: Commun. Math. And Comput. Chem., 2003. № 48. - p. 63-85.

78. Elizalde Sergi, Deutsch Emeric. A simple and unusual bijection for Dyck paths and its consequences // Ann. Comb., 2003. 7, № 3. - p. 281-297.

79. El-Mikkawy Moawwad, El-Desouky Beih. On a connection between symmetric polynomials, generalized Stirling numbers and the Newton general divided difference interpolation polynomial // Appl. Math, and Comput., 2003. 138, №2-3.-p. 375-385.

80. Goulden Ian, Yong Alexander. Dyck paths and a bijection for multisets of hook numbers // Discrete Math, 2002. 254, № 1-3. - p. 153-164.

81. Habsieger Laurent, Royer Emmanuel. L-functions of automorphic forms and combinatorics: Dyck paths // Ann. Inst. Fourier., 2004. 54, № 7. - p. 2105-2141.

82. Kubelka Richard P. Self-similarity and symmetries of Pascal's triangles and simplices mod p // Fibonacci Quart., 2004. 42, № 1. - p. 70-75.

83. Lehner Franz. Cumulants, lattice path, and orthogonal polynomials // Discrete Math, 2003. 270, № 1 -3. - p. 177-191.

84. Lenin R. В., Parthasarathy P. R., Scheinhardt W. R. W., Van Doom E. A. Families of birth-death processes with similar time-dependent behaviour // J. Appl. Probab., 2000. 37, № 3. - p. 835-849.

85. Linial Nathan. Finite metric spaces combinatorics, geometry and algorithms // Proceedings of the International Congress of Mathimaticians, Beijing, Aug. 20-28, 2002.-p. 573-586.

86. Rucker Gerta, Rucker Christoph. Walking backward: Walk counts of negative order // J. Chem. Inf. and Comput. Sci., 2003. 43, № 4. - p. 1115-1120.

87. Santos Jose' Pli'nio O., Mondek Paulo.q-Fibonacci sequences, bipartite numbers and lattice paths // Adv. Stud. Contemp. Math., 2002. 5, № 2. - p. 127-140.

88. Takeshima Masaki .Behavior of 1-dimensional reinforced random walk. Osaka J. Math., 2000. 37, № 2. - p. 355-372.

89. Tauber S. On quasi-othogonal numbers. // Amer. Math. Monthly, 1962. -69. p. 365-372.

90. Viennot Xavier G.erard. A Strahler bijection between Dyck paths and planar trees: 11 International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC'99), Barcelona, 7-11 June, 1999. Discrete Math., 2002. -246, № 1-3.-p. 317-329.

91. Wan Honghui, Wootton John C. Algorithms for computing lengths of chains in integral partition lattices // Theor. Comput. Sci., 2002. 289, № 1. - p. 783-800.

92. Yang Shengliang, Hu Zhangjian. Stirling numbers and Stirling matrices // J. Gansu Univ. Technol., 2002. 6. - p. 110-112.

93. You Yong-xing, Zhang Shao-hua. Shuxue Zazhi. A new theorem on thebinomial coefficientm + n11

94. J. Math., 2003. 23, № 2. - p. 146-148. 98. Zhou Chi-zhong. Hunan ligong xueyuan xuebao. Ziran kexue ban. Column generating function of the Pascal-type triangle // J. Hunan Inst. Sci. Techol. Natur. Sci., 2003. - 16, № 2. - p. 1-4.