On the Total Positivity of Delannoy-Like Triangles

Lili Mu School of Mathematics Liaoning Normal University Dalian, 116029 PR China

                  lly-mu@hotmail.com

Sai-nan Zheng School of Mathematical Sciences Dalian University of Technology Dalian, 116024 PR China

              zhengsainandlut@hotmail.com

Abstract

Define an infinite lower triangular matrix D(e, h) = [d_{n,k}]_{n,k≥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 ≥ k ≥ 0. We call D(e, h) the 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 wellknown 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öder 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.

1 Introduction

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 [1] gave historical background on Delannoy numbers. There is a link between Legendre polynomials and Delannoy numbers [8, 11]. The Delannoy triangle D = [t_{n,k}]_{n,k≥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 ≥ k ≥ 0. The first few entries of D are as follows:

D = [ \begin{matrix}1 \\ 1 & 1 \\ 1 & 3 & 1 \\ 1 & 5 & 5 & 1 \\ 1 & 7 & 13 & 7 & 1 \\ 1 & 9 & 25 & 25 & 9 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ] .

An immediate calculation shows that the row sums of Delannoy triangle form the Pell sequence [3]. The unsigned inverse of D is the Schröder triangle (\underline{A132372}). The central coefficients t_{2n,n} are called the central Delannoy numbers (\underline{A001850}) and have appeared in several problems, such as the alignments between DNA sequences [17].

In this paper, we study the infinite lower triangular matrix D(e, h) = [d_{n,k}]_{n,k≥0} defined 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},  (1)

where e, h are both nonnegative and d_{n,k} = 0 unless n ≥ k ≥ 0. We call D(e, h) the Delannoy-like triangle. The first few rows of a Delannoy-like triangle are as follows:

D(e, h) = [ \begin{matrix}1 \\ 1 & 1 \\ e & 1 + e + h & 1 \\ e^{2} & e^{2} + 2e + eh + h & 1 + 2e + 2h & 1 \\ ⋮ & ⋮ & ⋮ & & ... \end{matrix} ] .

The special cases are Delannoy triangle D(1, 1), the Pascal triangle (\underline{A007318}) D(1, 0), and the Fibonacci triangle (\underline{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 generalized Schröder matrix [18].

S(e, h) = [ \begin{matrix}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 \\ ⋮ & ⋮ & ⋮ & & ... \end{matrix} ] .

Such matrices include the Catalan triangle (\underline{A033184}) with e = 0, h = 1, and Schröder triangle (\underline{A132372}) with e = 1, h = 1.

S(1, 1) = [ \begin{matrix}1 \\ 1 & 1 \\ 2 & 3 & 1 \\ 6 & 10 & 5 & 1 \\ 22 & 38 & 22 & 7 & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \end{matrix} ] .

The row sums of S(1, 1) are the large Schröder numbers [7].

An infinite matrix is called totally positive (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 [6, 13]. Brenti [5] showed the total positivity of the Delannoy square (\underline{A008288}) [d(n, k)]_{n,k≥0} 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.

Theorem 1. The Delannoy-like triangles defined by (1) are totally positive matrices.

We give the proof of this, our main theorem, by showing the total positivity of the generalized Schröder matrix S(e, h) in Section 2. It turns out that the Pascal triangle, the Fibonacci triangle, the Delannoy triangle, the Catalan triangle, and the Schröder triangle are all TP matrices.

In Section 3, we briefly consider the PF sequence (see Section 3 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.

2 Proof of Theorem 1

To prove the total positivity of Delannoy-like triangles D(e, h), it suffices to show that the generalized Schröder matrix S(e, h) is TP, because the unsigned inverse of a TP matrix is still TP [13, Prop. 1.6], 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 [9]. 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 2).

We let (g(x), f(x)) denote a Riordan array R = [r_{n,k}]_{n,k≥0} [14], and (g(x), f(x)) is an infinite lower triangular matrix whose generating function of the kth column is g(x)f^{k}(x) for k = 0, 1, 2, …, where g(x) and f(x) are formal power series with g(0) = 1 and f(0) = 0, f′(0) ≠ 0. Suppose we multiply the array (g(x), f(x)) by a column vector (b_{0}, b_{1}, b_{2}, …)^{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

(g(x), f(x))b(x) = g(x)b(f(x)).  (2)

This is called the fundamental theorem for Riordan arrays and this lead to the multiplication rule for the Riordan arrays (see Shapiro et al. [14]):

(g(x), f(x)) (d(x), h(x)) = (g(x)d(f(x)), h(f(x))) .  (3)

The inverse of (g(x), f(x)) is

(g(x), f(x))^{−1} = (1/g(f̄(x)), f̄(x)),  (4)

where f̄(x) is the compositional inverse of f(x), such that f(f̄(x)) = 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 (2).

A Riordan array R = [r_{n,k}]_{n,k≥0} can also be characterized by two sequences (a_{n})_{n≥0} and (z_{n})_{n≥0} such that

r_{0,0} = 1, r_{n+1,0} = ∑_{j≥0} z_{j}r_{n,j}, r_{n+1,k+1} = ∑_{j≥0} a_{j}r_{n,k+j}

for n, k ≥ 0 (see [16] for instance). Call (a_{n})_{n≥0} and (z_{n})_{n≥0} the A- and Z-sequences of R, respectively. Following [6], call

J(R) = [ \begin{matrix}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} \\ ⋮ & ⋮ & & ⋯ & & ... \end{matrix} ]

the 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

A(x) = \frac{x}{f̄(x)};  Z(x) = \frac{1}{f̄(x)} (1 − \frac{1}{g(f̄(x))}) .  (5)

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 (1), we have

B(x, y) = ∑_{n=0}^{∞} ∑_{k=0}^{∞} d_{n,k}x^{n}y^{k}

= 1 + x + xy + ∑_{n=2}^{∞} ∑_{k=0}^{∞} d_{n,k}x^{n}y^{k}

= 1 + x + xy + ∑_{n=2}^{∞} ∑_{k=0}^{∞}(d_{n−1,k−1} + ed_{n−1,k} + hd_{n−2,k−1})x^{n}y^{k}

= 1 + x + xy + xy(B(x, y) − 1) + ex(B(x, y) − 1) + hx^{2}yB(x, y).

It follows that

B(x, y) = \frac{1 + x − ex}{1 − ex − xy − hx^{2}y} = \frac{1 + x − ex}{1 − ex} \frac{1}{1 − y \frac{x+hx^{2}}{1−ex}} .

Thus,

D(e, h) = (d(x), h(x)) = (\frac{1 + x − ex}{1 − ex}, \frac{x + hx^{2}}{1 − ex} ) .

Then

(S(e, h))^{−1} = (1, −x)D(e, h)(1, −x) = (d(−x), −h(−x)) = (\frac{1 − x + ex}{1 + ex}, \frac{x − hx^{2}}{1 + ex} ) ,

since S(e, h) = (1, −x)D^{−1}(e, h)(1, −x) and (3). From (4) and (5) , we have

A^{∗}(x) = \frac{x}{−h(−x)} = \frac{1 + ex}{1 − hx}; Z^{∗}(x) = \frac{1}{−h(−x)} (1 − d(−x)) = \frac{1}{1 − hx},

where A^{∗}(x) and Z^{∗}(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.

Lemma 2. 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 ≥ 0. Then R is TP.

Proof. The first few rows of the coefficient matrix of R are as follows:

J(R) = [ \begin{matrix}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 \\ ⋮ & ⋮ & & ⋯ & ... \end{matrix} ] .

A Riordan array is totally positive if its coefficient matrix is TP [6]. That means our next task is to show the total positivity of J(R). Let

H = [ \begin{matrix}1 \\ h & 1 \\ h^{2} & h & 1 \\ h^{3} & h^{2} & h & 1 \\ ⋮ & & ⋯ & & ... \end{matrix} ] , Q = [ \begin{matrix}1 & 1 \\ u & e + u & 1 \\ & eu & e + u & 1 \\ & & eu & e + u & 1 \\ & & & & ... & ... \end{matrix} ] .

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) = [ \begin{matrix}h & 1 \\ & 0 & 1 \\ & & 0 & 1 \\ & & & & . & . & . \end{matrix} ] .

Thus H is TP since J(H) is TP. Note that

Q = [ \begin{matrix}1 \\ u & 1 \\ & u & 1 \\ & & u & 1 \\ & & & ... & ... \end{matrix} ] [ \begin{matrix}1 & 1 \\ & e & 1 \\ & & e & 1 \\ & & & e & 1 \\ & & & & ... & ... \end{matrix} ] .

Clearly, Q is TP if e, u ≥ 0.

Therefore, S(e, h) is TP by the case of u = 0 in Lemma 2, and so D(e, h) is, too.

3 Remarks

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ólya frequency sequence. We now consider similar properties of Delannoy-like triangles.

An infinite sequence (a_{n})_{n≥0} is called a Pólya frequency sequence (or shortly, a PF sequence) if its Toeplitz matrix [a_{i−j}]_{i,j≥0} is TP. Pólya frequency sequences often arise in combinatorics [4]. A fundamental representation theorem of Schoenberg and Edrei states that a sequence (a_{n})_{n≥0} of real numbers is PF if and only if its generating function has the form

∑_{n≥0} a_{n}z^{n} = \frac{∏_{j≥1}(1 + α_{j}z)}{∏_{j≥1}(1 − β_{j}z)}e^{γz}

in some open disk center at the origin, where α_{j}, β_{j}, γ ≥ 0 and ∑_{j≥1}(α_{j} + β_{j}) < +∞ (see Karlin [10, p. 412], 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 [10, p. 399].

We let r_{n}(x) denote the nth row generating function ∑_{k≥0} 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 [12, Theorem 2.1]. Hence each row of a Delannoy-like triangle is a PF sequence.

Moreover, let m_{n}(x) denote the nth diagonal generating function ∑_{k≥0} 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:

Theorem 3. Each row and diagonal of Delannoy-like triangles form PF sequences.

In addition, the generating function of the nth 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 [2].

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

References

[1] C. Banderier and S. Schwer, Why Delannoy numbers?, J. Statist. Plann. Inference 135 (2005), 40–54.

[2] G. Bennett, Hausdorff means and moment sequences, Positivity 15 (2011), 17–48.

[3] N. Bicknell, A primer on the Pell sequence and related sequence, Fibonacci Quart. 13 (1975), 345–349.

[4] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 413 (1989).

[5] F. Brenti, Combinatorics and total positivity, J. Comb. Theory Ser. A 71 (1995), 175– 218.

[6] X. Chen, H. Liang, and Y. Wang, Total positivity of Riordan arrays, European J. Combin. 46 (2015), 68–74.

[7] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Co., 1974.

[8] I. J. Good, Legendre polynomials and trinomial random walks, Proc. Cambridge Philos. Soc. 54 (1958), 39–42.

[9] T. X. He, R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), 3962–3974.

[10] S. Karlin, Total Positivity, Volume 1, Stanford University Press, 1968.

[11] D. F. Lawden, On the solution of linear difference equations, Math. Gazette 36 (1952), 193–196.

[12] L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, Adv. in Appl. Math. 38 (2007), 542–560.

[13] A. Pinkus, Totally Positive Matrices, Cambridge University Press, 2010.

[14] L. W. Shapiro, S. Getu, W. J. Woan, and L. C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[15] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[16] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[17] A. Torres, A. Cabada, and J. J. Nieto, An exact formula for the number of alignments between two DNA sequences, DNA Sequence 14 (2003), 227–430.

[18] S. L. Yang, S. N. Zheng, S. P. Yuan, and T. X. He, Schröder matrix as inverse of Delannoy matrix, Linear Algebra Appl. 439 (2013), 3605–3614.

2010 Mathematics Subject Classification: Primary 05A20; Secondary 05B36, 15A45. Keywords: Delannoy number, Schröder number, totally positive matrix.

(Concerned with sequences \underline{A001850}, \underline{A007318}, \underline{A008288}, \underline{A026729}, and \underline{A132372}.)

Received June 29 2016; revised version received December 20 2016. Published in Journal of Integer Sequences, December 26 2016.

Return to Journal of Integer Sequences home page.