k-protected vertices in unlabeled rooted plane trees

DOI10.1007/S00373-017-1772-9MaRDI QIDQ2014218zbMATH OpenOpenAlexFDO

Authors Keith Copenhaver

Publication date 10 August 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.00083

zbMATH Keywords

asymptoticsenumerationtree

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Trees (05C05)

Abstract: 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.

Recommendations

• Protection number in plane trees
• Protected vertices in Motzkin trees
• Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves
• Protection number of recursive trees
• Protected nodes and fringe subtrees in some random trees

Cites work

• k-protected vertices in binary search trees
• Analytic combinatorics
• Asymptotic properties of protected nodes in random recursive trees
• Isomorphism and symmetries in random phylogenetic trees
• Notes on protected nodes in digital search trees
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• Protected nodes and fringe subtrees in some random trees
• Protected points in \(k\)-ary trees
• Protected points in ordered trees

Cited in

(15)

• Weakly protected points in ordered trees
• Limiting probabilities for vertices of a given rank in 1-2 trees
• Protected points in ordered trees
• Nonleaf patterns in trees: protected nodes and fine numbers
• k-protected vertices in binary search trees
• Protection number in plane trees
• Protected vertices in Motzkin trees
• Protected Branches in Ordered Trees
• On the peel number and the leaf-height of Galton–Watson trees
• Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves
• Protection numbers in simply generated trees and Pólya trees
• Protected points in \(k\)-ary trees
• The distribution of the maximum protection number in simply generated trees
• Characterization of trees with maximum security
• Protected cells in compositions

This page was built for publication: \(k\)-protected vertices in unlabeled rooted plane trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014218)