Введение 3
1 Задача о числе путей на целочисленной решетке 4
1.1 Постановка задачи 4
1.1.1 Постановка задачи при п=1 4
1.1.2 Постановка задачи при п=2 4
1.2 Примеры путей на целочисленной решетке 5
1.2.1 Последовательность Фибоначчи 5
1.2.2 Пути Дика 5
1.2.3 Числа в треугольнике Паскаля 7
2 Производящие функции на целочисленной решетке 8
2.1 Производящие функции в одномерном случае 8
2.2 Производящие функции в двумерном случае 8
2.3 Общие идеи нахождения двумерной производящей функции .... 9
3 Примеры 12
3.1 Нахождение производящей функции для чисел Фибонначи 12
3.2 Общий вид производящей функции при п=1 13
3.3 Нахождение производящей функции для чисел в треугольнике Паскаля 14
3.4 Общий вид производящей функции при п=2 18
3.5 Алгоритм нахождения производящей функции 20
Заключение 22
Список использованных источников 23
Приложение А 25
Всем, кто изучал математику, хорошо известен метод конечных разностей, который используется для аппроксимации непрерывного уравнения дискретным. Но исчисление конечных разностей пригодилось не только для аппроксимации, оно развивалось параллельно основным разделам математического анализа и имеет свою теоретическую базу для решения различных задач. Основными задачами в исчислении конечных разностей являются интерполирование и суммирование функций. С последней задачей тесно связана задача решения уравнений в конечных разностях. Задача суммирования тесно связана с производящими функциями. Как в математической статистике, так и в комбинаторике невозможно переоценить значение производящих функций. Зная производящую функцию решения, можно найти решение для большого количества комбинаторных задач.
Дадим общую постановку задачи. Дано разностное уравнение вида
caf (x+ a) = 0,x Е Zn, (0.1)
aEAcZn
где переменная x = {x1, x2,..., хп}—п-мерный вектор, а константы а имеют вид а = {ai,a2,... ,ап}.
С начальными (краевыми) условиями вида
f(x) = ф(х),х ЕM c Zn. (0.2)
Необходимо найти производящую функцию решения задачи (0.1) с начальными условиями (0.2).
В работе решена задача поиска производящей функции решения задачи о числе путей на целочисленной решетке для одномерного и двумерного случая.
Представлен и запрограммирован алгоритм нахождения производящей функции в двумерном и одномерном случае.
