k-Protected Vertices in Unlabeled Rooted Plane Trees

被引：10

作者：

Copenhaver, Keith ^{[1
]}

机构：

[1] Univ Florida, Dept Math, Gainseville, FL 32612 USA

来源：

GRAPHS AND COMBINATORICS | 2017年 / 33卷 / 02期

关键词：

Tree; Enumeration; Asymptotics; NODES;

D O I：

10.1007/s00373-017-1772-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We find a simple, closed formula for the proportion of vertices which are k-protected in all unlabeled rooted plane trees on n vertices. We also find that, as n goes to infinity, the average rank of a random vertex in a tree of size n approaches 0.727649, and the average rank of the root of a tree of size n approaches 1.62297.

引用

页码：347 / 355

页数：9

共 9 条

[1]

Bona M, J APPL PROB IN PRESS

[2] k-Protected vertices in binary search trees [J].

Bona, Miklos .

ADVANCES IN APPLIED MATHEMATICS, 2014, 53 :1-11

[3] ISOMORPHISM AND SYMMETRIES IN RANDOM PHYLOGENETIC TREES [J].

Bona, Miklos ;

Flajolet, Philippe .

JOURNAL OF APPLIED PROBABILITY, 2009, 46 (04) :1005-1019

[4] Protected points in ordered trees [J].

Cheon, Gi-Sang ;

Shapiro, Louis W. .

APPLIED MATHEMATICS LETTERS, 2008, 21 (05) :516-520

[5] Protected nodes and fringe subtrees in some random trees [J].

Devroye, Luc ;

Janson, Svante .

ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2014, 19 :1-10

[6] Notes on protected nodes in digital search trees [J].

Du, Rosena R. X. ;

Prodinger, Helmut .

APPLIED MATHEMATICS LETTERS, 2012, 25 (06) :1025-1028

[7]

Flajolet P., 2009, Analytic Combinatorics, Vfirst

[8]

Mahmoud HM, 2015, J APPL PROBAB, V52, P290

[9] Protected points in k-ary trees [J].

Mansour, Toufik .

APPLIED MATHEMATICS LETTERS, 2011, 24 (04) :478-480

← 1 →