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

• Автор: Соловьева, Людмила Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Иркутск
• Количество страниц: 130 с.

Глава 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]).
Роль существенной части языка современной дискретной математики отводится комбинаторике, древнейшей ветви математики, долгое время остававшейся на периферии математической науки. Комбинаторные задачи считались полезными для тренировки ума, развлечения или в силу их эстетической привлекательности. В настоящее время комбинаторный анализ продолжает заниматься вопросами исследования задач развлекательного характера, но основной целью является описание и изучение дискретных математических структур в различных областях.
К настоящему времени появилось большое количество руководств по комбинаторике, укажем лишь некоторые из них - это книги М. Айгнера, Я. Гульдена, Д. Джексона, Г. П. Егорычева, Ф. Картеси, А. Кофмана, О. В. Кузьмина, Р. А. Макмагона, М. Л. Платонова, Г. Дж. Райзера, Дж. Риордана, К. А. Рыбникова, В. Н. Сачкова, Р. Стенли, М. Холла, и многие другие [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].

-Пп- X е"у X К І
ґ іЛ ( “

у-я + Зі-х,
-п„- х е“>' у в: х
,=-л+і -(>-~)^„ У=пШЩ£к
1 з
ґ )Л
у-п+Зк-х,

у-п + Зк- х.
ч ^’Е®; I
у=л+1 у-пйкйп у-п+М

Используя формулу (2.4), находим Ж„(у) число взвешенных траекторий, начинающихся в точке с координатами (0,0) и заканчивающихся в точке (п,у):
для у = - 2«,-«
^(к)=я„- У л; X
уцци^у-п+н
3 4
(к' / *1
• у-п+3к-хх
1 з )
(2.15)
для у = -п + ,п
к(у)=пп- х я; I
—(у—л) ^, -(у-л) у-п+Зк
—* йх,йу-п+2к
3 2 4
Хі 1
у - п + Зк - х, +
чУ 1 3 )
Ґ Ъ-
+п.
.• Е г; Е
2 3
у-п + 3к-х]
(2.16)
для 7 = п +1,2« ж„(у)=я„- X в; X
у-пйкйп у-п+1к
<х,<к
у-п + 3к-хх
(2.17)
Полученные результаты проиллюстрируем в терминах случайных блужданий частицы по целочисленным точкам правой полуплоскости.
Задача 2.4. Частица выходит из начала координат и способна перемещаться скачками в дискретные моменты времени I, / = 0, со. Если частица к моменту / = п находится в точке с координатами (п,к), то к моменту / = « +1 она окажется в точке (« + 1Д-2), {п + ,к-) или в точке (и + 1Д + 2)с вероят-