Counting Lattice Paths by Using Difference Equations with Non-constant Coefficients

Abstract

The lattice paths can be counted by the virtue of their step vectors that are aligned to the positive octant. A path can go from one point to an infinite others if there is no restriction applied such that each point only has finitely many predecessors. The linear difference equations with non-constant coefficients will be utilised to incorporate this restriction to study lattice paths that lie on or over a line having a rational slope. The generating functions are obtained and is based on developing a specific method to compute the number of restricted lattice paths.

Keywords

• generating function
• difference equation
• functional equation
• lattice path