Article ID Journal Published Year Pages File Type
4647354 Discrete Mathematics 2014 16 Pages PDF
Abstract

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

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,