Simple Rules of a Discrete Stochastic Process Leading to Catalan-like Recurrences

A method for obtaining integer sequences is presented by defining simple rules for the evolution of a discrete dynamical system. This paper demonstrates that various Catalan-like recurrences of known integer sequences can be obtained from a single stochastic process defined by simple rules. The resulting exact equations that describe the stationary state of the process are derived using combinatorial analysis. A specific reduction of the process is applied, and the solvability of the reduced system of equations is demonstrated. Then, a procedure for providing appropriate parameters for a given sequence is formulated. The general method is illustrated with examples of Catalan, Motzkin, Schröder, and A064641 integer sequences. We also point out that by appropriately changing the parameters of the system, one can smoothly transition between distributions related to Motzkin numbers and shifted Catalan numbers.