Protected vertices in Motzkin trees

MaRDI QIDQ5114843zbMATH OpenFDO

Authors Anthony van Duzer

Publication date 26 June 2020

Full work available at URL https://arxiv.org/abs/1712.09507, https://web.math.rochester.edu/misc/ojac/vol15/175.pdf#issue15

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)

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.

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

Cites work

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

Cited in

(5)

• \(k\)-protected vertices in unlabeled rooted plane trees
• \(k\)-protected vertices in binary search trees
• Protected Branches in Ordered Trees
• Enumeration of protected nodes in Motzkin 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)