ترغب بنشر مسار تعليمي؟ اضغط هنا

A refinement of the formula for $k$-ary trees and the Gould-Vandermondes convolution

69   0   0.0 ( 0 )
 نشر من قبل Ricky Xiaofeng Chen
 تاريخ النشر 2019
  مجال البحث
والبحث باللغة English
 تأليف Ricky X. F. Chen




اسأل ChatGPT حول البحث

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 combinatorial 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.



قيم البحث

اقرأ أيضاً

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 refi nement $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.
182 - Yidong Sun , Huajun Zhang 2008
In this paper, we define two kinds of hook length for internal vertices of complete $m$-ary trees, and deduce their corresponding hook length formulas, which generalize the main results obtained by Du and Liu.
143 - Hein van der Holst 2012
Let $mathbb{F}$ be an infinite field with characteristic different from two. For a graph $G=(V,E)$ with $V={1,...,n}$, let $S(G;mathbb{F})$ be the set of all symmetric $ntimes n$ matrices $A=[a_{i,j}]$ over $mathbb{F}$ with $a_{i,j} ot=0$, $i ot=j$ i f and only if $ijin E$. We show that if $G$ is the complement of a partial $k$-tree and $mgeq k+2$, then for all nonsingular symmetric $mtimes m$ matrices $K$ over $mathbb{F}$, there exists an $mtimes n$ matrix $U$ such that $U^T K Uin S(G;mathbb{F})$. As a corollary we obtain that, if $k+2leq mleq n$ and $G$ is the complement of a partial $k$-tree, then for any two nonnegative integers $p$ and $q$ with $p+q=m$, there exists a matrix in $S(G;reals)$ with $p$ positive and $q$ negative eigenvalues.
A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $min {{rm deg}_G(x), {rm deg}_G(y)}$ vertex(edge)-disjoint paths between $x$ and $y$. In this paper, we consider strong Menger ( edge) connectedness of the augmented $k$-ary $n$-cube $AQ_{n,k}$, which is a variant of $k$-ary $n$-cube $Q_n^k$. By exploring the topological proprieties of $AQ_{n,k}$, we show that $AQ_{n,3}$ for $ngeq 4$ (resp. $AQ_{n,k}$ for $ngeq 2$ and $kgeq 4$) is still strongly Menger connected even when there are $4n-9$ (resp. $4n-8$) faulty vertices and $AQ_{n,k}$ is still strongly Menger edge connected even when there are $4n-4$ faulty edges for $ngeq 2$ and $kgeq 3$. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that $AQ_{n,k}$ is still strongly Menger edge connected even when there are $8n-10$ faulty edges for $ngeq 2$ and $kgeq 3$. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا