اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA refinement for ordered labeled trees
270
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $mathcal{O}_n$ be the set of ordered labeled trees on ${0,...,n}$. A maximal decreasing subtree of an ordered labeled tree is defined by the maximal ordered subtree from the root with all edges being decreasing. In this paper, we study a new refinement $mathcal{O}_{n,k}$ of $mathcal{O}_n$, which is the set of ordered labeled trees whose maximal decreasing subtree has $k+1$ vertices.
قيم البحث
اقرأ أيضاً
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.
For a labeled tree on the vertex set $set{1,2,ldots,n}$, the local direction of each edge $(i,j)$ is from $i$ to $j$ if $i<j$. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a ve
rtex is called its indegree. Thus the local (resp. global) indegree sequence $lambda = 1^{e_1}2^{e_2} ldots$ of a tree on the vertex set $set{1,2,ldots,n}$ is a partition of $n-1$. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prufer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a $q$-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.
We use a sign-reversing involution to show that trees on the vertex set [n], considered to be rooted at 1, in which no vertex has exactly one child are counted by 1/n sum_{k=1}^{n} (-1)^(n-k) {n}-choose-{k} (n-1)!/(k-1)! k^(k-1). This result corrects
a persistent misprint in the Encyclopedia of Integer Sequences.
In this paper, we present an involution on some kind of colored $k$-ary trees which provides a combinatorial proof of a combinatorial sum involving the generalized Catalan numbers $C_{k,gamma}(n)=frac{gamma}{k n+gamma}{k n+gammachoose n}$. From the c
ombinatorial sum, we refine the formula for $k$-ary trees and obtain an implicit formula for the generating function of the generalized Catalan numbers which obviously implies a Vandermonde type convolution generalized by Gould. Furthermore, we also obtain a combinatorial sum involving a vector generalization of the Catalan numbers by an extension of our involution.
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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
