Affordable Access

Enumerations of plane trees with multiple edges and Raney lattice paths

Discrete Mathematics
Publication Date
DOI: 10.1016/j.disc.2014.07.024
  • Enumeration Of Plane Trees
  • Lattice Paths
  • Raney Lemma


Abstract An N-ary plane multitree is a rooted tree whose subtrees at any vertex are linearly ordered, and every node has at most N outgoing edges to its children, and two nodes can be connected by multiple edges. An N-Raney path of length n is a lattice path running from (0,1) to (n,0) consisting of steps (1,k) for k∈Z such that k≤N, and for which all points except the last one lie above the x-axis. We show a bijection between N-Raney paths of length n and (N+1)-ary plane multitrees of n nodes. We show also a bijection between Raney paths and Raney sequences of integers whose sum is +1 and every partial sum is positive. These two bijections are a main tool to derive formulas for the number of N-ary plane multitrees with specified number of nodes, edges, and leaves. Some statistical properties are considered. It is shown that when N and n tend to infinity, the ratio of the number of leaves to the total number of nodes in all N-ary plane multitrees with n nodes is 1/e.

There are no comments yet on this publication. Be the first to share your thoughts.