In this paper we enumerate the cardinalities for the set of all vertices of outdegree $ge k$ at level $ge ell$ among all rooted ordered $d$-trees with $n$ edges. Our results unite and generalize several previous works in the literature.
In this paper we enumerate and give bijections for the following four sets of vertices among rooted ordered trees of a fixed size: (i) first-children of degree $k$ at level $ell$, (ii) non-first-children of degree $k$ at level $ell-1$, (iii) leaves having $k-1$ elder siblings at level $ell$, and (iv) non-leaves of outdegree $k$ at level $ell-1$. Our results unite and generalize several previous works in the literature.
Let $mathcal{T}^{(p)}_n$ be the set of $p$-ary labeled trees on ${1,2,dots,n}$. A maximal decreasing subtree of an $p$-ary labeled tree is defined by the maximal $p$-ary subtree from the root with all edges being decreasing. In this paper, we study a new refinement $mathcal{T}^{(p)}_{n,k}$ of $mathcal{T}^{(p)}_n$, which is the set of $p$-ary labeled trees whose maximal decreasing subtree has $k$ vertices.
Let $T_{n}$ be the set of rooted labeled trees on $set{0,...,n}$. A maximal decreasing subtree of a rooted labeled tree is defined by the maximal subtree from the root with all edges being decreasing. In this paper, we study a new refinement $T_{n,k}$ of $T_n$, which is the set of rooted labeled trees whose maximal decreasing subtree has $k+1$ vertices.
The Perron value $rho(T)$ of a rooted tree $T$ has a central role in the study of the algebraic connectivity and characteristic set, and it can be considered a weight of spectral nature for $T$. A different, combinatorial weight notion for $T$ - the moment $mu(T)$ - emerges from the analysis of Kemenys constant in the context of random walks on graphs. In the present work, we compare these two weight concepts showing that $mu(T)$ is almost an upper bound for $rho(T)$ and the ratio $mu(T)/rho(T)$ is unbounded but at most linear in the order of $T$. To achieve these primary goals, we introduce two new objects associated with $T$ - the Perron entropy and the neckbottle matrix - and we investigate how different operations on the set of rooted trees affect the Perron value and the moment.
We introduce some natural families of distributions on rooted binary ranked plane trees with a view toward unifying ideas from various fields, including macroevolution, epidemiology, computational group theory, search algorithms and other fields. In the process we introduce the notions of split-exchangeability and plane-invariance of a general Markov splitting model in order to readily obtain probabilities over various equivalence classes of trees that arise in statistics, phylogenetics, epidemiology and group theory.