Protected Vertices in Motzkin trees

zbMATH Open1442.05238arXiv1712.09507MaRDI QIDQ5114843FDOQ5114843

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

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

• Title not available (Why is that?)
• 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)