کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647354 1632405 2014 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Enumerations of plane trees with multiple edges and Raney lattice paths
ترجمه فارسی عنوان
شمارش درخت های هواپیما با لبه های متعدد و مسیرهای شبکه رانی
کلمات کلیدی
شمارش درختان هواپیما، مسیرهای شبکه لانه رانی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 337, 28 December 2014, Pages 9–24
نویسندگان
,