Algebraic Succession Rules and Lattice Paths With an Infinite Set of Jumps

Whereas walks on N with a finite set of jumps were the subject of numerous studies, walks with an infinite number of jumps remain quite rarely studied, at least from a combinatorial point of view. A reason is that even for relatively well structured models, the classical approach with context-free grammars fails as we deal with rewriting rules over an infinite alphabet. However, several classes of such walks offer a surprising structure: in this article, we show that one can make explicit the generating functions of the number of walks (with respect to their length) between two fixed points. We also give several theorems on their nature (rational, algebraic). In fact, we mostly deal with succession rules of the type (k); (0) e