Total positivity of Riordan arrays Xi Chen, Huyile Liang and Yi Wang ∗ 6 School of Mathematical Sciences, Dalian University of Technology, Dalian 116024,PR China 1 0 2 n Abstract a J We present sufficient conditions for total positivity of Riordan arrays. As appli- 1 cations we show that many well-known combinatorial triangles are totally positive 2 and many famous combinatorial numbers are log-convex in a unified approach. ] O MSC: 05A20; 15B36; 15A45 Keywords: Riordan array; Totally positive matrix; Log-convex sequence; Log- C concave sequence . h t a m 1 Introduction [ 1 Riordan arrays play an important unifying role in enumerative combinatorics [18]. v A (proper) Riordan array, denoted by (g(x),f(x)), is an infinite lower triangular matrix 7 3 whose generating function of the kth column is xkfk(x)g(x) for k = 0,1,2,..., where 6 g(0) = 1 and f(0) = 0. A Riordan array R = [r ] can also be characterized by two 5 6 n,k n,k≥0 0 sequences (an)n 0 and (zn)n 0 such that . ≥ ≥ 1 0 r = 1, r = z r , r = a r (1.1) 0,0 n+1,0 j n,j n+1,k+1 j n,k+j 6 Xj 0 Xj 0 1 ≥ ≥ : v for n,k 0 (see [6, 10, 14, 20] for instance). Call (a ) and (z ) the A- and Z- n n 0 n n 0 i ≥ ≥ ≥ X sequences of R respectively. r Many triangles in combinatorics are Riordan arrays with simple A- and Z-sequences. a For example, the Pascal triangle with Z = (1,0,...) and A = (1,1,0,...), the Cata- lan triangle with Z = (2,1,0...) and A = (1,2,1,0,...) [17], the Motzkin triangle with Z = (1,1,0,...) and A = (1,1,1,0,...) [1], the ballot table with Z = A = (1,1,1,...)[2], the large Schro¨der triangle with Z = (2,2,2,...) and A = (1,2,2,...) [6], and the little Schro¨der triangle with Z = A = (1,2,2,...) [6]. Such triangles arise often in the enumer- ation of lattice paths, e.g., the Dyck paths, the Motzkin paths, and the Schro¨der paths and so on [6, 14, 18]. The 0th column of such an array counts the corresponding lattice paths, including the Catalan numbers, the Motzkin numbers, the large and little Schro¨der numbers. There have been quite a few papers concerned with combinatorics of Riordan arrays (see [6, 10, 14, 16, 18, 20] for instance). Our concern in the present paper is total positivity of Riordan arrays. ∗Email address: [email protected] (Y. Wang) 1 Following Karlin [11], an infinite matrix is called totally positive of order r (or shortly, TP ), if its minors of all orders r are nonnegative. The matrix is called TP if its r ≤ minors of all orders are nonnegative. Let (a ) be an infinite sequence of nonnegative n n 0 ≥ numbers. It is called a P´olya frequency sequence of order r (or shortly, a PF sequence), r if its Toeplitz matrix a 0  a a  1 0 [ai j]i,j 0 =  a2 a1 a0  − ≥  a a a a   3 2 1 0   ... ...   ···  is TP . It is called PF if its Toeplitz matrix is TP. We say that a finite sequence r a ,a ,...,a is PF (PF, resp.) if the corresponding infinite sequence a ,a ,...,a ,0,... 0 1 n r 0 1 n is PF (PF, resp.). A fundamental result of Aissen, Schoenberg and Whitney states that r a finite sequence of nonnegative numbers is PF if and only if its generating function has only real zeros (see [11, p. 399] for instance). For example, the sequence (r,s,t) of non- negative numbers is PF if and only if s2 4rt. We say that a nonnegative sequence (a ) n ≥ is log-convex (log-concave, resp.) if a a a a (a a a a , resp.) for 0 i < j. i j+1 i+1 j i j+1 i+1 j ≥ ≤ ≤ Clearly, the sequence (a ) is log-concave if and only if it is PF , i.e., its Toeplitz matrix n 2 [a ] is TP , and the sequence is log-convex if and only if its Hankel matrix [a ] i j i,j 0 2 i+j i,j 0 − ≥ ≥ is TP [4]. 2 There are often various total positivity properties in a Riordan array. For example, the Pascal matrix is TP [11, p. 137] and each row of it is log-concave (see [22] for more information), the Catalan numbers, the Motzkin numbers, the large and little Schro¨der numbers form a log-convex sequence respectively [13]. However, there is no systematic study of total positivity of Riordan arrays. The object of this paper is to study various positivity properties of Riordan arrays, including the total positivity of such a matrix, the log-convexity of the 0th column and the log-concavity of each row. The paper is organized as follows. In the next section, we present sufficient conditions for total positivity of Riordan arrays. As applications, we show that many well-known combinatorial triangles are totally positive and many famous combinatorial numbers are log-convex in a unified approach. In Section 3, we propose some problems for further work. 2 Main results and applications We first present a basic result about total positivity of Riordan arrays. Let R = [r ] be a Riordan array defined by the recursive system (1.1). Call n,k n,k 0 ≥ z a 0 0  z a a  1 1 0 J(R) =  z2 a2 a1 a0 .  z a a a a   3 3 2 1 0   ... ... ...   ···  the coefficient matrix of the Riordan array R. 2 Theorem 2.1. Let R be a Riordan array defined by (1.1). (i) If the coefficient matrix J(R) is TP (TP, resp.), then so is R. r (ii) If R is TP and all z 0, then the 0th column (r ) of R is log-convex. 2 n n,0 n 0 ≥ ≥ To prove Theorem 2.1, we need two lemmas. The first is direct by definition and the second follows from the classic Cauchy-Binet formula. Lemma 2.2. A matrix is TP (TP, resp.) if and only if its leading principal submatrices r are all TP (TP, resp.). r Lemma 2.3. If two matrices are TP (TP, resp.), then so is their product. r Proof of Theorem 2.1. (i) It suffices to show that J(R) is TP implies R is TP . Let r r r 0,0  r r  1,0 1,1 Rn =  r2,0 r2,1 r2,2   .. ..   . .     rn,0 rn,1 rn,2 rn,n   ···  be the nth leading principal submatrix of R. Then by Lemma 2.2, it suffices to show that R is TP for n 1. We proceed by induction on n. Assume that R is TP . By (1.1), n r n r ≥ we have r 1 1 0,0  r r   0 r  z a  1,0 1,1 0,0 0 0  ... ...  =  ... ... ...  ... ... ... ,       rn+1,0 rn+1,1 rn+1,n+1   0 rn,0 rn,n  zn an a0   ···   ···  ···  or briefly, 1 O 1 O R = , (2.1) n+1 (cid:20) O R (cid:21)(cid:20) ζ (cid:21) n n n A where ζ = [z ,z ,...,z ] and = [a ] . By the induction hypothesis, R is n 0 1 n ′ n i j 0 i,j n n A − ≤ ≤ TP , so is the first matrix on the right hand side of (2.1). On the other hand, [ζ , ] is r n n A TP since it is a submatrix of the TP matrix J(R), so is the second matrix on the right r r hand side of (2.1). It follows from Lemma 2.3 that the product R is TP . Thus the n+1 r matrix R is TP . r (ii) Note that r r r 1 z 0,0 1,0 0,0 0  r r   r r  0 z  1,0 2,0 1,0 1,1 1 = . (2.2) r r r r r 0 z  2,0 3,0   2,0 2,1 2,2  2   ... ...   ... ...  ... ...       Clearly, the second matrix on the right hand side of (2.2) is TP since all z are nonneg- 2 n ative. Now R is TP by the assumption. Hence the matrix on the left hand side of (2.2) 2 is TP by Lemma 2.3. In other words, the sequence (r ) is log-convex. 2 n,0 n 0 ≥ 3 In the sequel we consider applications of Theorem 2.1 to two classes of special inter- esting Riordan arrays. The first are recursive matrices introduced by Aigner [1, 2]. Let a,b,s,t be four nonnegative numbers. Define a Riordan array R(a,b;s,t) = [r ] by n,k n,k 0 ≥ r = 1, r = ar +br , r = r +sr +tr . 0,0 n+1,0 n,0 n,1 n+1,k n,k 1 n,k n,k+1 − Following Aigner [1, 2], the numbers C (a,b;s,t) = r are called the Catalan-like num- n n,0 bers. Many well-known triangles are recursive matrices. For example, the Pascal triangle, the Catalantriangleandthe Motzkin triangleare R(1,0;1,0),R(2,1;2,1)andR(1,1;1,1) respectively. Also, theCatalan-likenumbersunifymanyfamouscountingcoefficients, such as the Catalan numbers C (2,1;2,1), the Motzkin numbers C (1,1;1,1), the central bi- n n nomial coefficients C (2,2;2,1), and the large Schro¨der numbers C (2,2;3,2). See [2] for n n details. Theorem 2.4. Let a,b,s,t be four nonnegative numbers. (i) If as b and s2 t, then the sequence (r ) is log-convex. n,0 n 0 ≥ ≥ ≥ (ii) If s2 4t and as+√s2 4t b, then the matrix R(a,b;s,t) is totally positive. − ≥ 2 ≥ Remark 2.5. From Theorem 2.4 it follows immediately that the Pascal triangle and the Catalan triangle are totally positive, and that the Catalan numbers, the Motzkin numbers, the central binomial coefficients, and the large Schro¨der numbers are log-convex respectively. Remark 2.6. Let r r r 0,0 1,0 2,0 ···  r r r  1,0 2,0 3,0 H(a,b;s,t) = [r ] = ··· n+m,0 n,m≥0  r2,0 r3,0 r4,0 ···   ... ... ... ...    be the Hankel matrix of the Catalan-like numbers r . Aigner [1, 2] computed the de- n,0 terminants of the leading principal submatrices of H. Aigner’s Fundamental Theorem in [2] gives H = RTR, where T = diag(1,t,t2,t3,...). So the total positivity of R implies ′ that of the Hankel matrix H. In particular, if s2 4t and as+√s2 4t b, then the Hankel − ≥ 2 ≥ matrix H(a,b;s,t) is totally positive. By Theorem 2.1, to prove Theorem 2.4, it suffices to prove that the coefficient matrix of R(a,b;s,t) a 1  b s 1  t s 1    t s 1     .. .. ..   . . .    is TP and TP under the conditions respectively. We do this by establishing the following 2 stronger result. 4 Proposition 2.7. Let a,b,r,s,t be five nonnegative numbers and the Jacobi matrix a r  b s r  J = t s r .    t s r     .. .. ..   . . .    Then (i) J is TP if and only if as br and s2 rt. 2 ≥ ≥ (ii) J is TP if and only if s2 4rt and a s+√s2 4rt /2 br. ≥ − ≥ (cid:0) (cid:1) Proof. (i) is obvious, and it remains to prove (ii). Clearly, the tridiagonal matrix J is TP if and only if all its principal minors containing consecutive rows and columns are nonnegative (see, e.g., [15, Theorem 4.3]), i.e., all determinants of forms s r  t s r  d = det t s ... n    ... ... r     t s   n n × and a r  b s r  D = det t s ... n    ... ... r     t s   (n+1) (n+1) × are nonnegative. Note that all d are nonnegative if and only if the Toeplitz matrix n r  s r  t s r    t s r     .. .. ..   . . .    isTP,i.e., thesequence (r,s,t)isPF.Hencealld 0ifandonlyifs2 4rt. Wecomplete n ≥ ≥ the proof of (ii) by showing that all D 0 if and only if (s+√s2 4rt)/2 br/a. n ≥ − ≥ Note that D = a and D = ad brd by expanding the determinant along the first 0 n n n 1 − − column, where d = 1 and d = s. Hence all D 0 if and only if all d /d br/a. We 0 1 n n n 1 next showthatthesequence d /d isnonincrea≥sing andconvergent to(s+−√s≥2 4rt)/2, n n 1 which means that all d /d b−r/a is equivalent to (s+ √s2 4rt)/2 br/a−, and so n n 1 all D 0 if and only if (s+− √≥s2 4rt)/2 br/a. − ≥ n ≥ − ≥ 5 Actually, we have by expanding the determinant along the first column d = sd rtd , d = 1,d = s. (2.3) n n 1 n 2 0 1 − − − Solving this linear recurrence relation we obtain n d = λkµn k, n − Xk=0 where s+√s2 4rt s √s2 4rt λ = − , µ = − − 2 2 are two roots of the characteristic equation x2 sx+rt = 0 of (2.3). − By (2.3), we have d d s rt d d n n+1 = − n−1 n . (cid:20) d d (cid:21) (cid:20) 1 0 (cid:21)(cid:20) d d (cid:21) n 1 n n 2 n 1 − − − It follows that d2 d d = rt(d2 d d ) = = (rt)n 1(d2 d d ) = (rt)n 0. Thus the sequennc−e dn/−d1 n+1is noninnc−r1ea−sinng−,2annd is·t·h·erefore −conv1er−gen0t.2 Let α be≥the n n 1 − limit. Rewrite (2.3) as d rt n = s . d − d /d n 1 n 1 n 2 − − − Take the limit to obtain α = s rt/α, i.e., α2 sα + rt = 0, so α = λ or µ. Now − − d /d = s λ. Assume that d /d λ. Then 1 0 n 1 n 2 ≥ − − ≥ d rt rt n = s s = λ. d − d /d ≥ − λ n 1 n 1 n 2 − − − Thus all d /d λ. It follows that the limit α = λ since λ µ, as desired. n n 1 − ≥ ≥ The second we concern about are Riordan arrays whose A- and Z-sequences are iden- tical or nearly so. Following [6], we say that a Riordan array R = [r ] is consistent n,k n,k 0 ≥ if A = Z. We say that R is a quasi-consistent Riordan array if A = (a ,a ,a ,...) and 0 1 2 Z = (a ,a ,...). In this case, we have 1 2 r = a r +a r +a r + n+1,k 0 n,k 1 1 n,k 2 n,k+1 − ··· for all n,k 0, where r = 0 unless 0 j n. For example, the little Schro¨der n,j ≥ ≤ ≤ triangle is consistent, the Pascal triangle, the Catalan triangle, the Motzkin triangle and the large Schro¨der triangle are quasi-consistent, and the ballot table is both consistent and quasi-consistent. The following theorem gives a unified settle for the total positivity of these well-known triangles. Theorem 2.8. Let R be a consistent or quasi-consistent Riordan array. Suppose that the A-sequence of R is PF (PF, resp.). Then R is TP (TP, resp.). In particular, if the r r A-sequence of R is log-concave, then the 0th column (r ) of R is log-convex, and each n,0 n 0 ≥ row (r ) of R is log-concave. n,k 0 k n ≤ ≤ 6 Proof. For a consistent or quasi-consistent Riordan array R, its coefficient matrix is a a a a 0 0 1 0  a a a   a a a  1 1 0 2 1 0 J(R) = or a a a a a a a a  2 2 1 0   3 2 1 0   ... ... ...   ... ... ...      respectively. Clearly, J(R) is TP if and only if the Toeplitz matrix [a ] of the r i j i,j 0 − ≥ sequence (a ) is TP , or equivalently, the sequence (a ) is PF . Thus it follows n n 0 r n n 0 r ≥ ≥ from Theorem 2.1 (i) that the Riordan array R is TP (resp., TP) if its A-sequence is r PF (resp. PF). r In particular, if (a ) is PF , then R is TP . It follows from Theorem 2.1 (ii) that n n 0 2 2 ≥ the sequence (r ) is log-convex. In what follows we show that each row of R is log- n,0 n 0 ≥ concave by induction. Denote s = r for 0 i n and t = r for 0 j n+1. i n,i j n+1,j ≤ ≤ ≤ ≤ We distinguish two cases. First consider the case that R is a consistent Riordan array. In this case, t = t and 0 1 t t = a (s s )+ +a (s s )+a s k k+1 0 k 1 k n k n 1 n n k+1 n − − − ··· − − − − for 1 k n. It follows that each row of R is nonincreasing by induction. On the other ≤ ≤ hand, t s a n+1 n 0  t t   s s  a a  n n+1 n 1 n 1 0  ... ... ...  =  ... − ... ...  ... ... ... . (2.4)       t1 t2 tn+1   s0 s1 sn  an an 1 a0   ···   ···  − ···  Suppose that the sequence (a ) is log-concave. Then its Toeplitz matrix = [a ] n n 0 i j i,j 0 ≥ A − ≥ is TP , and so are the leading principal submatrices of . Thus the second matrix on the 2 A right hand side of (2.4) is TP . If the nth row s ,s ,...,s of R is log-concave, then so is 2 0 1 n the reverse sequence s ,...,s ,s , which implies that the first matrix on the right hand n 1 0 side of (2.4) is TP . Thus the matrix on the left hand side of (2.4) is TP by Lemma 2.3, 2 2 or equivalently, the sequence t ,t ,...,t is log-concave, and so is the reverse sequence n+1 n 1 t ,...,t ,t . Note that t = t t . Hence the sequence t ,t ,t ,...,t is also 1 n n+1 0 1 2 0 1 2 n+1 ≥ log-concave. Thus each row of R is log-concave by induction. Next let R be a quasi-consistent Riordan array. Then s t n a n+1  s s  0  ...tn ...tn+1 ...  =  ...n−1 ...n ...  a...1 a...0 ... .  t0 t1 ··· tn+1   0s0 ss01 ··· ssnn 1 sn  an+1 an ··· a0   ··· −  Assume that the sequence s ,s ,...,s is log-concave. Then the first matrix on the right 0 1 n hand side is TP . It follows that the matrix on the left hand side is TP . In other 2 2 words, the sequence t ,t ,...,t ,t is log-concave. Thus each row of R is log-concave 0 1 n n+1 by induction. This completes the proof. 7 3 Further work It is known that sequences of binomial coefficients located in a ray or a transversal of the Pascal triangle have various positivity properties (see [22, 25] for instance). Similar problems naturally arise in a Riordan array. For example, in which case each row of such a Riordan array is PF, the corresponding linear transformation can preserve the PF property (the log-concavity, the log-convexity, resp.), and each column of the array is first log-concave and then log-convex? Aigner[2]gavecombinatorialinterpretationsforrecursivematricesintermsofweighted Motzkin paths. Cheon et al. [6] provided combinatorial interpretations for consistent Ri- ordan arrays in terms of weighted L ukasiewicz paths. It is not difficult to give a similar combinatorial interpretation for a quasi-consistent Riordan array. Brenti [5] gave combi- natorial proofs of total positivity of many well-known matrices by means of lattice path techniques. It is natural to ask for combinatorial proofs of Theorems 2.4 and 2.8. Acknowledgement This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 11071030, 11371078) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110041110039). References [1] M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999) 33–51. [2] M. Aigner, Catalan and other numbers — A recurrent theme, in: H. Crapo, D. Senato (Eds.), Algebraic Combinatorics and Computer Science, Springer Italian, Milan, 2001, 347–390. [3] M. Aigner, Enumeration via ballot numbers, Discrete Math. 308 (2008) 2544–2563. [4] F. Brenti, Unimodal, log-concave and Po´lya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 413 (1989). [5] F. Brenti, Combinatorics and total positivity, J. Combin. Theory Ser. A 71 (1995) 175–218. [6] G.-S. Cheon, H. Kim and L.W. Shapiro, Combinatorics of Riordan arrays with iden- tical A and Z sequences, Discrete Math. 312 (2012) 2040–2049. [7] S.M. Fallat and C.R. Johnson, Totally Nonnegative Matrices, Princeton University Press, Princeton, 2011. [8] S. Fomin and A. Zelevinsky, Total positivity: tests and parameterizations, Math. Intelligencer 22 (2000), 23-33. 8 [9] T.-X. He, Parametric Catalan numbers and Catalan triangles, Linear Algebra Appl. 438 (2013) 1467–1484. [10] T.-X. He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009) 3962–3974. [11] S. Karlin, Total Positivity, Volume 1, Stanford University Press, 1968. [12] L.L. Liu and Y. Wang, On the log-convexity of combinatorial sequences, Adv. in. Appl. Math. 39 (2007) 453–476. [13] L.L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, Adv. in Appl. Math. 38 (2007) 542–560. [14] D. Merlini, D.G. Rogers, R. Sprugnoli and M.C. Verri, On some alternative charac- terizations of Riordan arrays, Canad. J. Math. 49 (1997) 301–320. [15] A. Pinkus, Totally positive matrices, Cambridge University Press, Cambridge, 2010. [16] D.G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978) 301–310. [17] L.W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976) 83–90. [18] L.W. Shapiro, S. Getu, W.-J. Woan and L.C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991) 229–239. [19] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org. [20] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994) 267–290. [21] R. Sprugnoli, Combinatorial sums through Riordan arrays, J. Geom. 101 (2011) 195– 210. [22] X.-T. Su and Y. Wang, On unimodality problems in Pascal’s triangle, Electron. J. Combin., 15 (2008), Research Paper 113, 12 pp. [23] Y. Wang and Y.-N. Yeh, Polynomials with real zeros and Po´lya frequency sequences, J. Combin. Theory Ser. A 109 (2005) 63–74. [24] Y. Wang and Y.-N. Yeh, Log-concavity and LC-positivity, J. Combin. Theory Ser. A 114 (2007) 195–210. [25] Y. Yu, Conforming two conjectures of Su and Wang on binonmial coefficients, Adv. in Appl. Math. 43 (2009) 317–322. 9