Difference Equations and Generating Functions for some Lattice Path Problems

Abstract

An identity for generating functions is proved in this paper. A novel method to compute the number of restricted lattice paths is developed on the basis of this identity. The method employs a difference equation with non-constant coefficients. Dyck paths, Schr¨oder paths, Motzkins path and other paths are computed to illustrate this method

В работе доказано тождество для производящих функций, на основе которого разработан метод вычисления числа путей на целочисленной решетке с ограничениями. Данный метод использует разностные уравнения с переменными коэффициентами. В качестве примеров вычислены произвоящие функции для путей Дика, Моцкина и Шрёдера