\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\negbin}{negbin} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On the Total Positivity of \\ \vskip .1in Delannoy-Like Triangles } \vskip 1cm \large Lili Mu\\ School of Mathematics \\ Liaoning Normal University\\ Dalian, 116029\\ PR China\\ \href{mailto:lly-mu@hotmail.com }{\tt lly-mu@hotmail.com} \\ \ \\ Sai-nan Zheng\\ School of Mathematical Sciences \\ Dalian University of Technology \\ Dalian, 116024\\ PR China\\ \href{mailto: zhengsainandlut@hotmail.com}{\tt zhengsainandlut@hotmail.com}\\ \end{center} \vskip .2in \begin{abstract} Define an infinite lower triangular matrix $D(e,h)=[d_{n,k}]_{n,k\geq 0}$ by the recurrence $$d_{0,0}=d_{1,0}=d_{1,1}=1,\ d_{n,k}=d_{n-1,k-1}+ed_{n-1,k}+hd_{n-2,k-1},$$ where $e$, $h$ are both nonnegative and $ d_{n,k}=0$ unless $n\geq k \geq 0$. We call $D(e,h)$ the {\it Delannoy-like triangle}. The entries $d_{n,k}$ count lattice paths from $(0,0)$ to $(n-k,k)$ using the steps $(0,1)$, $(1,0)$ and $(1,1)$ with assigned weights $1$, $e$, and $h$. Some well-known combinatorial triangles are such matrices, including the Pascal triangle $D(1,0)$, the Fibonacci triangle $D(0,1)$, and the Delannoy triangle $D(1,1)$. Futhermore, the Schr\"oder triangle and Catalan triangle also arise as inverses of Delannoy-like triangles. Here we investigate the total positivity of Delannoy-like triangles. In addition, we show that each row and diagonal of Delannoy-like triangles are all PF sequences. \end{abstract} \section{Introduction}\label{Intro} \hspace*{\parindent} The Delannoy number $d(n,k)$ is defined as the number of lattice paths from $(0,0)$ to $(n,k)$ with steps $(0,1)$, $(1,0)$ and $(1,1)$. Banderier and Schwer \cite{BS05} gave historical background on Delannoy numbers. There is a link between Legendre polynomials and Delannoy numbers \cite{Good58, Law52}. The Delannoy triangle $D=[t_{n,k}]_{n,k\geq 0}$ is an infinite lower triangular matrix defined by $t_{n,k}=d(n-k,k)$. Its entries satisfy the recurrence $$t_{0,0}=1,\ t_{n,k}=t_{n-1,k-1}+t_{n-1,k}+t_{n-2,k-1},$$ where $t_{n,k}=0$ unless $n\geq k \geq 0$. The first few entries of $D$ are as follows: $$D=\left[ \begin{array}{ccccccc} 1 & & & & & & \\ 1 & 1 & & & & & \\ 1 & 3 & 1 & & & & \\ 1 & 5 & 5 & 1 & & & \\ 1 & 7 & 13 & 7 & 1 & & \\ 1 & 9 & 25 & 25 & 9 & 1 & \\ \vdots & \vdots &\vdots & \vdots & \vdots & \vdots & \ddots\\ \end{array}\right].$$ An immediate calculation shows that the row sums of Delannoy triangle form the Pell sequence \cite{B75}. The unsigned inverse of $D$ is the Schr\"oder triangle (\seqnum{A132372}). The central coefficients $t_{2n,n}$ are called the central Delannoy numbers (\seqnum{A001850}) and have appeared in several problems, such as the alignments between DNA sequences \cite{TCN03}. In this paper, we study the infinite lower triangular matrix $D(e,h)=[d_{n,k}]_{n,k\geq 0}$ defined by the recurrence \begin{equation} \label{delannoy} d_{0,0}=d_{1,0}=d_{1,1}=1,\ d_{n,k}=d_{n-1,k-1}+ed_{n-1,k}+hd_{n-2,k-1}, \end{equation} where $e$, $h$ are both nonnegative and $ d_{n,k}=0$ unless $n\geq k \geq 0$. We call $D(e,h)$ the {\it Delannoy-like triangle}. The first few rows of a Delannoy-like triangle are as follows: $$D(e,h)=\left[ \begin{array}{cccccc} 1 & & & & \\ 1 & 1 & & & \\ e & 1+e+h & 1 & & \\ e^2 & e^2+2e+eh+h & 1+2e+2h & 1 & \\ \vdots & \vdots &\vdots & & \ddots \\ \end{array}\right].$$ The special cases are Delannoy triangle $D(1,1)$, the Pascal triangle (\seqnum{A007318}) $D(1,0)$, and the Fibonacci triangle (\seqnum{A026729}) $D(0,1)$. On the other hand, we let $S(e,h)$ denote the unsigned inverse of $D(e,h)$, i.e., $S(e,h)=MD(e,h)^{-1}M$, where $M$ is the diagonal matrix with diagonal entries alternately $1$ and $-1$. We call $S(e,h)$ the {\it generalized Schr\"oder matrix} \cite{YZYH13}. $$S(e,h)=\left[ \begin{array}{cccccc} 1 & & & & \\ 1 & 1 & & & \\ 1+h & 1+e+h & 1 & & \\ 1+2h+eh+2h^2 & e^2+e+3eh+2h^2+2h+1 & 1+2e+2h & 1 & \\ \vdots & \vdots &\vdots & & \ddots \\ \end{array}\right].$$ Such matrices include the Catalan triangle (\seqnum{A033184}) with $e=0$, $h=1$, and Schr\"oder triangle (\seqnum{A132372}) with $e=1$, $h=1$. $$S(1,1)=\left[ \begin{array}{cccccc} 1 & & & & & \\ 1 & 1 & & & & \\ 2 & 3 & 1 & & & \\ 6 & 10 & 5 & 1 & & \\ 22 & 38 & 22 & 7 & 1 & \\ \vdots & \vdots &\vdots & \vdots & \vdots & \vdots \\ \end{array}\right].$$ The row sums of $S(1,1)$ are the large Schr\"oder numbers \cite{C74}. An infinite matrix is called {\it totally positive} ({\it TP}, for short) if its minors of all orders are nonnegative. The theory of totally positive matrices is rich with deep and highly non-trivial results, and has been studied extensively \cite{CLW-EuJC, Pin10}. Brenti \cite{Bre95} showed the total positivity of the Delannoy square (\seqnum{A008288}) $[d(n,k)]_{n,k\geq0}$ by giving a combinatorial interpretation of its minors in terms of nonintersecting paths in a digraph. It is natural to conjecture that Delannoy-like triangles are totally positive. The primary purpose of this paper is to show this is true. \begin{theorem} The Delannoy-like triangles defined by \eqref{delannoy} are totally positive matrices. \label{gf} \end{theorem} We give the proof of this, our main theorem, by showing the total positivity of the generalized Schr\"oder matrix $S(e,h)$ in Section \ref{proof}. It turns out that the Pascal triangle, the Fibonacci triangle, the Delannoy triangle, the Catalan triangle, and the Schr\"oder triangle are all TP matrices. In Section \ref{remark}, we briefly consider the PF sequence (see Section \ref{remark} for definitions) in Delannoy-like triangles. With a simple proof, we conclude that each row and diagonal of Delannoy-like triangles all form PF sequences. \section{Proof of Theorem \ref{gf}}\label{proof} \hspace*{\parindent} To prove the total positivity of Delannoy-like triangles $D(e,h)$, it suffices to show that the generalized Schr\"oder matrix $S(e,h)$ is TP, because the unsigned inverse of a TP matrix is still TP \cite[Prop. 1.6]{Pin10}, and $D(e,h)$ is also the unsigned inverse of $S(e,h)$. Actually, since the $D(e,h)$ are Riordan arrays (we will prove it first), so are $S(e,h)$. This implies that $S(e,h)$ possess $A$-sequences and $Z$-sequences, since any Riordan array can be characterized by the $A$- and $Z$-sequences uniquely \cite{HS09}. Therefore, our idea is to construct a class of Riordan arrays with $A$-sequences and $Z$-sequences having a certain form, and make sure $S(e,h)$ are such matrices. Then $S(e,h)$ is TP if we show this class of Riordan arrays is TP (Claim \ref{az}). We let $(g(x),f(x))$ denote a Riordan array $R=[r_{n,k}]_{n,k\geq 0}$ \cite{SGWW91}, and $(g(x),f(x))$ is an infinite lower triangular matrix whose generating function of the $k$th column is $g(x)f^k(x)$ for $k=0,1,2,\ldots,$ where $g(x)$ and $f(x)$ are formal power series with $g(0)=1$ and $f(0)=0$, $f'(0)\neq 0$. Suppose we multiply the array $(g(x), f(x))$ by a column vector $ (b_0,b_1, b_2, \ldots )^T $ with generating function $b(x)$. Then we get a column vector whose generating function is given by $g(x)b( f (x))$. If we identify a sequence with its generating function, the composition rule can be rewritten as \begin{equation} \label{vector} (g(x), f(x)) b(x) = g(x)b( f (x)). \end{equation} This is called the fundamental theorem for Riordan arrays and this lead to the multiplication rule for the Riordan arrays (see Shapiro et al.~\cite{SGWW91}): \begin{equation}\label{multi} \left(g(x),f(x)\right)\left(d(x),h(x)\right)=\left(g(x)d(f(x)),h(f(x))\right). \end{equation} The inverse of $(g(x),f(x))$ is \begin{equation} \label{inverse} (g(x),f(x))^{-1}=(1/g(\bar{f}(x)),\bar{f}(x)), \end{equation} where $\bar{f}(x)$ is the compositional inverse of $f(x)$, such that $f(\bar{f}(x))=\bar{f}(f(x))=x$. The bivariate generating function $R(x,y)$ of the Riordan array $R$ is given by $$R(x,y)=(g(x),f(x))\frac{1}{1-yx}=\frac{g(x)}{1-yf(x)},$$ following \eqref{vector}. A Riordan array $R=[r_{n,k}]_{n,k\geq 0}$ can also be characterized by two sequences $(a_n)_{n\geq 0}$ and $(z_n)_{n\geq 0}$ such that $$r_{0,0}=1,\ r_{n+1,0}=\sum_{j\geq 0}z_jr_{n,j},\ r_{n+1,k+1}=\sum_{j\geq 0}a_jr_{n,k+j}$$ for $n,k \geq 0$ (see \cite{Spr94} for instance). Call $(a_n)_{n\geq 0}$ and $(z_n)_{n\geq 0}$ the $A$- and $Z$-sequences of $R$, respectively. Following \cite{CLW-EuJC}, call $$J(R)=\left[ \begin{array}{cccccc} z_{0} & a_{0} & & & \\ z_{1} & a_{1} &a_{0} & & \\ z_{2} &a_{2} & a_{1} & a_{0}& \\ z_{3} &a_{3} & a_{2} & a_{1} & a_{0} \\ \vdots & \vdots & & \cdots & & \ddots \\ \end{array} \right]$$ the {\it coefficient matrix} of the Riordan array $R$. Let $A(x)$ and $Z(x)$ be the generating functions of $A$-sequence and $Z$-sequence respectively. Then \begin{equation}\label{AZ} A(x)=\frac{x}{\bar{f}(x)};\qquad Z(x)=\frac{1}{\bar{f}(x)}\left(1-\frac{1}{g(\bar{f}(x))}\right). \end{equation} Now we start by proving that Delannoy-like triangles are Riordan arrays, and deduce the generating functions of $A$-sequence and $Z$-sequence of $S(e,h)$. Let $B(x,y)$ denote the bivariate generating function of $D(e,h)$. By \eqref{delannoy}, we have \begin{align*} B(x,y)&=\sum_{n=0}^ {\infty}\sum_{k=0}^{\infty}d_{n,k}x^ny^k\\ &=1+x+xy+\sum_{n=2}^ {\infty}\sum_{k=0}^{\infty}d_{n,k}x^ny^k\\ &=1+x+xy+\sum_{n=2}^ {\infty}\sum_{k=0}^{\infty}(d_{n-1,k-1}+ed_{n-1,k}+hd_{n-2,k-1})x^ny^k\\ &=1+x+xy+xy(B(x,y)-1)+ex(B(x,y)-1)+hx^2yB(x,y). \end{align*} It follows that \begin{align*} B(x,y)&=\frac{1+x-ex}{1-ex-xy-hx^2y}=\frac{1+x-ex}{1-ex}\frac{1}{1-y\frac{x+hx^2}{1-ex}}. \end{align*} Thus, $$D(e,h)=(d(x),h(x))=\left(\frac{1+x-ex}{1-ex},\frac{x+hx^2}{1-ex}\right).$$ Then $$(S(e,h))^{-1}=(1,-x)D(e,h)(1,-x)= (d(-x),-h(-x))=\left(\frac{1-x+ex}{1+ex},\frac{x-hx^2}{1+ex}\right),$$ since $S(e,h)=(1,-x)D^{-1}(e,h)(1,-x)$ and \eqref{multi}. From \eqref{inverse} and \eqref{AZ} , we have $${A}^{\ast}(x)=\frac{x}{-h(-x)}=\frac{1+ex}{1-hx};\quad {Z}^{\ast}(x)=\frac{1}{-h(-x)}\left(1-d(-x)\right)=\frac{1}{1-hx},$$ where ${A}^{\ast}(x)$ and ${Z}^{\ast}(x)$ are the generating functions of $A$-sequence and $Z$-sequence of $S(e,h)$, respectively. Next we construct a class of Riordan arrays by expanding the $A$-sequence of $S(e,h)$ and have the following result. \begin{lemma}\label{az} Let $A(x)$ and $Z(x)$ be the generating functions of $A$-sequence and $Z$-sequence of Riordan array $R$. Suppose that $Z(x)=\frac{1+ux}{1-hx}$ and $A(x)=Z(x)(1+ex)$, where $e,h,u\geq 0$. Then $R$ is TP. \end{lemma} \begin{proof} The first few rows of the coefficient matrix of $R$ are as follows: $$J(R)= \left[ \begin{array}{cccccc} 1 & 1 & & \\ u+h & e+h+u &1 & \\ (u+h)h & ue+eh+uh+h^2 & e+h+u & 1 \\ (u+h)h^2 &(ue+eh+uh+h^2)h & ue+eh+uh+h^2 & e+h+u \\ \vdots & \vdots & & \cdots & & \ddots\\ \end{array} \right].$$ A Riordan array is totally positive if its coefficient matrix is TP \cite{CLW-EuJC}. That means our next task is to show the total positivity of $J(R)$. Let $$H= \left[ \begin{array}{ccccc} 1 & & & \\ h &1 & & \\ h^2 & h & 1 & \\ h^3 & h^2 & h & 1 \\ \vdots & & \cdots & & \ddots \\ \end{array} \right], \quad Q= \left[ \begin{array}{cccccc} 1 & 1 & & & \\ u & e+u &1 & & \\ & eu &e+u & 1 & \\ & & eu & e+u & 1 \\ & & & & \ddots & \ddots \\ \end{array} \right].$$ Then $J(R)$ is obtained from $Q$ by adding $h$ times each row to the succeeding row. It follows that $J(R)=HQ$. Note that the product of two totally positive matrices is TP. Hence, it suffices to show that $H$ and $Q$ are TP. The coefficient matrix of $H$ is $$J(H)= \left[ \begin{array}{ccccc} h & 1 & & \\ & 0& 1 & \\ & & 0&1 \\ & & & & \ddots \\ \end{array} \right].$$ Thus $H$ is TP since $J(H)$ is TP. Note that $$Q= \left[ \begin{array}{cccccc} 1 & & & & \\ u & 1 & & & \\ & u&1 & & \\ & & u& 1 & \\ & & & \ddots & \ddots & \\ \end{array} \right] \left[ \begin{array}{cccccc} 1 & 1 & & & \\ & e &1 & & \\ & &e & 1 & \\ & & & e & 1 \\ & & & & \ddots & \ddots \\ \end{array} \right].$$ Clearly, $Q$ is TP if $e,u\geq 0$. \end{proof} Therefore, $S(e,h)$ is TP by the case of $u=0$ in Lemma \ref{az}, and so $D(e,h)$ is, too. \section{Remarks}\label{remark} \hspace*{\parindent} There are various total positivity properties of Riordan arrays. For example, the Pascal triangle $P$ is a totally positive matrix and each row of $P$ is a P\'{o}lya frequency sequence. We now consider similar properties of Delannoy-like triangles. An infinite sequence $(a_n)_{n\geq 0}$ is called a {\it P\'{o}lya frequency sequence} (or shortly, a {\it PF} sequence) if its Toeplitz matrix $[a_{i-j}]_{i,j\geq 0}$ is TP. P\'{o}lya frequency sequences often arise in combinatorics \cite{Bre89}. A fundamental representation theorem of Schoenberg and Edrei states that a sequence $(a_n)_{n\geq 0}$ of real numbers is PF if and only if its generating function has the form $$\sum_{n\geq 0}a_nz^n=\frac{\prod_{j\geq 1}(1+\alpha_jz)}{\prod_{j\geq 1}(1-\beta_jz)}e^{\gamma z}$$ in some open disk center at the origin, where $\alpha_j, \beta_j, \gamma \geq 0$ and $\sum_{j\geq 1}(\alpha_j+\beta_j)<+\infty$ (see Karlin \cite[p.\ 412]{Kar68}, for instance). Aissen, Schoenberg and Whitney showed that a finite sequence of nonnegative numbers is PF if and only if its generating function has only real zeros \cite[p.\ 399]{Kar68}. We let ${r_n(x)}$ denote the $n$th row generating function $\sum_{k\geq0}d_{n,k}x^{k}$ of a Delannoy-like triangle $D(e,h)$. Then ${r_n(x)}$ satisfies the recurrence $$r_0(x)=1,\ r_1(x)=e+x,\ r_n(x)=(e+x)r_{n-1}+hxr_{n-2}(x).$$ It is easy to check that $r_n(x)$ has only real zeros \cite[Theorem 2.1]{LW07}. Hence each row of a Delannoy-like triangle is a PF sequence. Moreover, let ${m_n(x)}$ denote the $n$th diagonal generating function $\sum_{k\geq0}d_{n+k,k}x^{k}$ of $D(e,h)$. Then ${m_n(x)}$ satisfies the recurrence $$m_n(x)=\frac{e+hx}{1-x}m_{n-1}(x),$$ where $m_0(x)=1/(1-x)$, and we have $$m_n(x)=\frac{(e+hx)^{n-1}}{(1-x)^n}.$$ This means that each diagonal of Delannoy-like triangles is also a PF sequence. Thus we have the following result: \begin{theorem} Each row and diagonal of Delannoy-like triangles form PF sequences. \end{theorem} In addition, the generating function of the $n$th column of $D(e,h)$ is $$g(x)f^{n}(x)=\frac{(1+x-ex)(x+hx^2)^n}{(1-ex)^{n+1}}.$$ Hence each column of a Delannoy-like triangle is a PF sequence if $e=0,1$. It follows that each column of the Delannoy triangle, the Pascal triangle and the Fibonacci triangle is a PF sequence. However, not all lines of every Delannoy-like triangle are PF sequences. For example, the central Delannoy numbers, the central coefficient of the Delannoy triangle, is a log-convex sequence \cite{Ben11}. \section{Acknowledgments} The authors would like to thank the anonymous referees for their careful reading and helpful comments which have hopefully led to a clearer paper. \begin{thebibliography}{99} \bibitem{BS05} C. Banderier and S. Schwer, Why Delannoy numbers?, {\it J. Statist. Plann. Inference} {\bf 135} (2005), 40--54. \bibitem{Ben11} G. Bennett, Hausdorff means and moment sequences, {\it Positivity} {\bf 15} (2011), 17--48. \bibitem{B75} N. Bicknell, A primer on the Pell sequence and related sequence, {\it Fibonacci Quart.} {\bf 13} (1975), 345--349. \bibitem{Bre89} F. Brenti, Unimodal, log-concave and P\'olya frequency sequences in combinatorics, {\it Mem. Amer. Math. Soc.} {\bf 413} (1989). \bibitem{Bre95} F. Brenti, Combinatorics and total positivity, {\it J. Comb. Theory Ser. A} {\bf 71} (1995), 175--218. \bibitem{CLW-EuJC} X. Chen, H. Liang, and Y. Wang, Total positivity of Riordan arrays, {\it European J. Combin.} {\bf 46} (2015), 68--74. \bibitem{C74} L. Comtet, {\it Advanced Combinatorics}, D. Reidel Publishing Co., 1974. \bibitem{Good58} I. J. Good, Legendre polynomials and trinomial random walks, {\it Proc. Cambridge Philos. Soc.} {\bf 54} (1958), 39--42. \bibitem{HS09} T. X. He, R. Sprugnoli, Sequence characterization of Riordan arrays, {\it Discrete Math.} {\bf 309} (2009), 3962--3974. \bibitem{Kar68} S. Karlin, {\it Total Positivity}, Volume 1, Stanford University Press, 1968. \bibitem{Law52} D. F. Lawden, On the solution of linear difference equations, {\it Math. Gazette} {\bf 36} (1952), 193--196. \bibitem{LW07} L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, {\it Adv. in Appl. Math.} {\bf 38} (2007), 542--560. \bibitem{Pin10} A. Pinkus, {\it Totally Positive Matrices}, Cambridge University Press, 2010. \bibitem{SGWW91} L. W. Shapiro, S. Getu, W. J. Woan, and L. C. Woodson, The Riordan group, {\it Discrete Appl. Math.} {\bf 34} (1991), 229--239. \bibitem{oeis} N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}. \bibitem{Spr94} R. Sprugnoli, Riordan arrays and combinatorial sums, {\it Discrete Math.} {\bf 132} (1994), 267--290. \bibitem{TCN03} A. Torres, A. Cabada, and J. J. Nieto, An exact formula for the number of alignments between two DNA sequences, {\it DNA Sequence} {\bf 14} (2003), 227--430. \bibitem{YZYH13} S. L. Yang, S. N. Zheng, S. P. Yuan, and T. X. He, Schr\"oder matrix as inverse of Delannoy matrix, {Linear Algebra Appl.} {\bf 439} (2013), 3605--3614. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A20; Secondary 05B36, 15A45. \\ \noindent \emph{Keywords: } Delannoy number, Schr\"oder number, totally positive matrix. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001850}, \seqnum{A007318}, \seqnum{A008288}, \seqnum{A026729}, and \seqnum{A132372}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received June 29 2016; revised version received December 20 2016. Published in {\it Journal of Integer Sequences}, December 26 2016. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .