Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwo kinds of hook length formulas for complete $m$-ary trees
177
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 $mge 2$ be a fixed positive integer. Suppose that $m^j leq n< m^{j+1}$ is a positive integer for some $jge 0$. Denote $b_{m}(n)$ the number of $m$-ary partitions of $n$, where each part of the partition is a power of $m$. In this paper, we show that $b_m(n)$ can be represented as a $j$-fold summation by constructing a one-to-one correspondence between the $m$-ary partitions and a special class of integer sequences rely only on the base $m$ representation of $n$. It directly reduces to Andrews, Fraenkel and Sellers characterization of the values $b_{m}(mn)$ modulo $m$. Moreover, denote $c_{m}(n)$ the number of $m$-ary partitions of $n$ without gaps, wherein if $m^i$ is the largest part, then $m^k$ for each $0leq k<i$ also appears as a part. We also obtain an enumeration formula for $c_m(n)$ which leads to an alternative representation for the congruences of $c_m(mn)$ due to Andrews, Fraenkel, and Sellers.
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.
Efficient optimal prefix coding has long been accomplished via the Huffman algorithm. However, there is still room for improvement and exploration regarding variants of the Huffman problem. Length-limited Huffman coding, useful for many practical applications, is one such variant, in which codes are restricted to the set of codes in which none of the $n$ codewords is longer than a given length, $l_{max}$. Binary length-limited coding can be done in $O(n l_{max})$ time and O(n) space via the widely used Package-Merge algorithm. In this paper the Package-Merge approach is generalized without increasing complexity in order to introduce a minimum codeword length, $l_{min}$, to allow for objective functions other than the minimization of expected codeword length, and to be applicable to both binary and nonbinary codes; nonbinary codes were previously addressed using a slower dynamic programming approach. These extensions have various applications -- including faster decompression -- and can be used to solve the problem of finding an optimal code with limited fringe, that is, finding the best code among codes with a maximum difference between the longest and shortest codewords. The previously proposed method for solving this problem was nonpolynomial time, whereas solving this using the novel algorithm requires only $O(n (l_{max}- l_{min})^2)$ time and O(n) space.
By considering the specialisation $s_{lambda}(1,q,q^2,...,q^{n-1})$ of the Schur function, Stanley was able to describe a formula for the number of semistandard Young tableaux of shape $lambda$ in terms of two properties of the boxes in the diagram for $lambda$. Using specialisations of symplectic and orthogonal Schur functions, we derive corresponding formulae, first given by El Samra and King, for the number of semistandard symplectic and orthogonal $lambda$-tableaux.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
