History

Please fill in your query. A complete syntax description you will find on the General Help page.
Weighted increasing trees and exponential generating functions. (English)
Int. J. Pure Appl. Math. 38, No. 3, 403-413 (2007).
The author here studies the counting of various tree with labelled nodes and weighted edges and its exponential generating functions, finally giving a construction of labelled weighted trees structure to count certain sequences. An increasing tree is a tree with nodes labelled with $[n]=\{0,1,2,3,4,\dots,n\}$ which satisfies the following two conditions: { indent=7mm \item{(1)}Increasing on any branch going up. \item{(2)}Increasing from left to right of the immediate success of a node. } A tree is said to be 1‒2 tree, if the out degree of each node is at most two. A Riordan matrix is a lower triangular matrix for which the generating function for the $k$th column, $k\ge 0$, is given by $g(x)[f(x)]^k$, where $$g(x)= 1+ g_1x+ g_2x^2+\cdots, \quad f(x)= x+ f_2x^2+ f_3 x^3+\cdots.$$ Riordan matrix with exponential generating function is a lower triangular matrix for which the generating function for the $k$th column, $k\ge 0$, is given by ${1\over k!} g(x)[f(x)]^k$, where $$g(x)= 1+ g_1x+ g_2{x^2\over 2!}+ g_3{x^3\over 3!}+\cdots, \quad f(x)= x+ f_2 x^2+ f_2{x^3\over 3!}+\cdots,$$ Remarked that: There is a bijection between 1‒2 trees and Motzkin paths. For weighted increasing 1‒2 trees $(\text{WIT}(b,c))$ weight $b$ is assigned for that single edge and for a node with outdegree 2, the left edge weight 1 is assigned and the right edge weight $c$. The weight of a weighted increasing tree is the product of the weights of the edges. For a generalized weighted increasing trees $(\text{GWIT}(a,b,c,d))$ weights $a$, $d$ are assigned instead of $b$, $c$ for those edges with initial nodes on left most branch. If $h_n$ is the sum of the weights of all trees in $(\text{GWIT}(a,b,c,d))$ of order $n$ and the trees are partitioned by the first node of the left-most branch, then the recurrence relation is $h_n= ah_{n-1}+ d \sum{n-1\choose k}h_k w_{n-2-k}$ and after solving, $h= h(x)= \exp(\int(a+ dy)\,dx)$. Examples discussed are: taking { indent=7mm \item{i)}$b=1$, $c=2$, the sequence is $w_0=1,1,3,9,39,\dots$ and it counts the number of permutations on $n$ letters without double falls and without initial falls. \item{ii)}$b=3$, $c=4$, the sequence is $w_0=1,3,13,75,541,\dots$ and it counts the number of ways $n$ competitors can rank in a competition, allowing for the possibility of ties. \item{iii)}$B=c=2$, the sequence is $w_0=1,2,6,24,120,\dots$ . \newl The sequence is $h_0= 1,1,4,16,88,568,4288,36832,354688$. } Hankel matrix generated by the sequence $a_0,a_1,a_2,\dots$, is given by $$H= \left[\matrix a_0 & a_1 & a_2 & a_3 & a_4 & *\ a_1 & a_2 & a_3 & a_4 & a_5 & *\ a_2 & a_3 & a_4 & a_5 & a_6 & *\ a_3 & a_4 & a_5 & a_6 & a_7 & *\ a_4 & a_ 5 & a_6 & a_7 & a_8 & *\ * & * & * & * & * & *\endmatrix\right]$$ and the Stieltjes matrix $L^{-1}\overline L$ ($\overline L$ is obtained from $L$ by removing the first row) has the form $$S_L= \left[\matrix a & 1 & 0 & 0 & 0 & *\ d & λ_1 & 1 & 0 & 0 & *\ 0 & μ_1 & λ_2 & 1 & 0 & *\ 0 & 0 & μ_2 & λ_3 & 1 & *\ 0 & 0 & 0 & μ_3 & λ_4 & *\ * & * & * & * & * & *\endmatrix\right].$$ The following two theorems are of importance for what has been proposed in the paper. { indent=7mm \item{(i)}Let $H$ be the Hankel matrix generated by the sequence $1,a_1,a_2,\dots$ and let $H= LDL^T$. Then $L$ is a Riordan matrix if and only if the Stieltjes $S_L$ has the form $$S_L= \left[\matrix a & 1 & 0 & 0 & 0 & *\ d & λ& 1 & 0 & 0 & *\ 0 & μ& λ& 1 & 0 & *\ 0 & 0 & μ& λ& 1 & *\ 0 & 0 & 0 & μ& λ& *\ * & * & * & * & * & *\endmatrix\right].$$ And the ordinary generating function $g(x)= \sum a_n x^n$ of the sequence $1,a_1,a_2,\dots$ is given by $g(x)= {1\over 1- ax- dxf}$, where $f= x(1+ λf+μf^2)$, $f(0)$. \item{(ii)}Let $H$ be the Hankel matrix generated by the sequence $1,a_1,a_2, a_3,\dots$ and let $H= LDL^T$. Then $L$ is a Riordan matrix with exponential generating function if and only if the Stieltjes matrix $S_L$ has the form $$S_L= \left[\matrix a & 1 & 0 & 0 & 0 & *\ d & λ_1 & 1 & 0 & 0 & *\ 0 & μ_1 & λ_2 & 1 & 0 & *\ 0 & 0 & μ_2 & λ_3 & 1 & *\ 0 & 0 & 0 & μ_4 & λ_4 & *\ * & * & * & * & * & *\endmatrix\right],$$ where $\{λ_i\}_{i\ge 0}$ is an arithmetic sequence with common difference $μ$, and the exponential generating function $g(x)=\sum a_n{x^n\over n!}$ for the sequence $1,a_1,a_2,a_3,\dots$ is given by $\ln(g)=\int(a+ df)\,dx$, $g(0)=1$, where $f$ is given by $f’= 1+λf+μf^2$, $f(0)= 0$. } The above result helps one to find $\text{GWIT}(a, λ, 2μ,d)$. An algorithm of constructing $\text{GWIT}(a,λ,$ $2μ,d)$ is also supplied.
Reviewer: K. C. Chowdhury (Guwahati)