В перечислительном комбинаторном анализе широко известна задача о решёточных путях: для заданного набора векторов A = {a1, a2, ...an} E TP требуется вычислить количество способов, которыми можно прийти в точку из начала координат, пользуясь только шагами из набора A. Решеточные пути возникают в различных задачах перечислительного комбинаторного анализа.
Одним из основных средств исследования свойств функции являются про-изводящие функции, то есть функции, имеющие вид F(z) = ^2xEznf(x)zx. Преимуществом такого представления является возможность использования средств комплексного анализа для исследования свойств функции f(x).
В 1722 году Абрахам Муавр доказал, что в одномерном случае степенной ряд F(z) представляет собой рациональную функцию тогда и только тогда, когда его коэффициенты удовлетворяют рекуррентному соотношению с постоянными коэффициентами.
В.Ю. Гришунов и А.П. Ляпин доказали, что это утверждение справедливо для многомерного разностного уравнения с постоянными коэффициентами. В их работе была выведена рекуррентная формула для сечений производящей функции F(z).
В данной работе был разработан и реализован алгоритм вычисления про-изводящей функции и рекуррентного соотношения для произвольного набора векторов, а также вывод соответствующего уравнения для заданного сечения на языке Matlab.
В ходе написания данной работы рассмотрены базовые понятия и инструменты анализа решеточных путей. Введены некоторые обобщения при построении решетки.
На основе теоремы был разработан и реализован алгоритм для автоматизации подсчета производящих функция, составления рекуррентных соотношений, а также нахождения сечений для любого набора векторов, удовлетворяющих начальным требованиям теоремы. Программа оформлена в виде Toolbox’a MatLAB с собственным графическим интерфейсом. Что означает, что любой желающий владеющий MatLAB может добавить этот компонент как дополнение.
Продемонстрирована возможность генерации коэффициентов большого класса многочленов с помощью решеточных путей.
