کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647354 | 1632405 | 2014 | 16 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 337, 28 December 2014, Pages 9–24