Random walks, trees and extensions of Riordan group techniques.

摘要

The Catalan number sequence 1,1,2,5,14,42,&ldots;,1n+1 2nn,&ldots; is one of the most important sequences in all of enumerative combinatorics. Richard Stanley cites at least 66 combinatorial settings where the sequence appears [7]. Among the numerous interpretations of the Catalan numbers, we have the number of paths restricted to the first quadrant of the x, y-plane starting at (0, 0) and ending at (2n, 0) using “up” steps (1,1) or “down” steps (1, −1) (known as Dyck paths). This research will focus on a generalization of the Catalan numbers which can be interpreted as taking Dyck paths and perturbing the length of the down step. One particular example of this generalization is given by the sequence of numbers known as the ternary numbers, 1,1,3,12,55,273,1428,7752,43263,&ldots;,1 2n+13nn ,&ldots;. This sequence arises in many natural contexts and extensions of known results related to combinatorial objects such as paths, trees, permutations, partitions, Young tableaux and dissections of convex polygons. Hence, we use this sequence as an important example of something which lies on the boundary of what is known and what is new. Much of this research is an attempt to extend many of the known results for the Catalan numbers to ternary and m-ary numbers.; In this dissertation, we establish, in the setting of the ternary numbers, several analogues to the better known Catalan numbers setting. We present an analogue to the Chung-Feller Theorem which says that for paths from (0, 0) to (3n, 0) with step set {lcub}(1,1), (1, −2){rcub}, the number of up (1,1) steps above the x-axis is uniformly distributed. We also present analogues to the Binomial, Motzkin and Fine generating functions and discuss combinatorial interpretations of each. In addition, we establish some computational results regarding the area bounded by ternary paths and the number of returns to the x-axis. We also present generating function proofs for the area under Dyck and ternary paths, an interesting connection to weighted trees, and a conjecture for a closed form generating function for the area under ternary paths.