کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6417583 1339300 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The asymptotic number of non-isomorphic rooted trees obtained by rooting a tree
ترجمه فارسی عنوان
تعداد تابعی از درختان ریشه ای غیر ایزومورفیک به دست آمده از طریق ریشه یابی درخت
کلمات کلیدی
درخت، درخت ریشه دار، الگو، شمارش، تولید تابع، محدود کردن توزیع، خودروسازی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات آنالیز ریاضی
چکیده انگلیسی

Let Tn denote the set of trees with n vertices. Suppose that each tree in Tn is equally likely. We show that the number of non-isomorphic rooted trees obtained by rooting a tree equals (μr+o(1))n for almost every tree of Tn, where μr is a constant. As an application, we show that in Tn the number of any given pattern, which is a fixed small tree with internal vertices specified, is asymptotically normally distributed with mean ∼μMn and variance ∼σMn, where μM and σM are some constants related to the given pattern. This solves an open question claimed in Kok's thesis.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Mathematical Analysis and Applications - Volume 434, Issue 1, 1 February 2016, Pages 1-11
نویسندگان
, , ,