Protected vertices in Motzkin trees

zbMATH Open1442.05238arXiv1712.09507MaRDI QIDQ5114843FDOQ5114843

Authors: Anthony van Duzer 

Publication date: 26 June 2020

Abstract: In this paper we find recurrence relations for the asymptotic probability a vertex is $k$ protected in all Motzkin trees. We use a similar technique to calculate the probabilities for balanced vertices of rank $k$. From this we calculate upper and lower bounds for the probability a vertex is balanced and upper and lower bounds for the expected rank of balanced vertices.

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

Recommendations

• Enumeration of protected nodes in Motzkin trees
• \(k\)-protected vertices in unlabeled rooted plane trees
• \(k\)-protected vertices in binary search trees
• Protected nodes and fringe subtrees in some random trees
• Asymptotic properties of protected nodes in random recursive trees

zbMATH Keywords

enumerative combinatoricsMotzkin trees

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Analytic combinatorics
• Protected points in ordered trees
• Notes on protected nodes in digital search trees
• Protected points in \(k\)-ary trees
• Protected nodes and fringe subtrees in some random trees
• On the number of vertices of each rank in phylogenetic trees and their generalizations

Cited In (3)

• \(k\)-protected vertices in binary search trees
• Protected Branches in Ordered Trees
• Protection number in plane trees

This page was built for publication: Protected vertices in Motzkin trees

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