Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA refinement of the formula for $k$-ary trees and the Gould-Vandermondes convolution
69
0
0.0
(
0
)
Authors
Ricky X. F. Chen
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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$ if 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
