# Some Inverse Relations Determined by Catalan Matrices

Authors: Sheng-liang Yang
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

We use theA-sequence and Z-sequence of Riordan array to characterize the inverse relation associated with the Riordan array. We apply this result to prove some combinatorial identities involving Catalan matrices and binomial coefficients. Some matrix identities obtained by Shapiro and Radoux are all special cases of our identity. In addition, a unified form of Catalan matrices is introduced.


---

## Body

## 1. Introduction

The Catalan numbersCn have been widely encountered and investigated [1, 2]. They can be defined through binomial coefficients
(1)Cn=1n+1(2nn),forn≥0,
or by the generating function C(t)=∑n=0∞‍Cntn being
(2)C(t)=1-1-4t2t,
which satisfies the functional equation C(t)=1+tC(t)2. In [2], Stanley listed 66 enumerative problems which are counted by the Catalan numbers. Many number triangles related to the Catalan sequence have been introduced in the literature. In [3–5], Shapiro et al. introduced a Catalan triangle B with the entries given by
(3)Bn,k=k+1n+1(2n+2n-k),wheren≥k≥0.
The following identity is obtained in [6] in connection with the moment of the Catalan triangle:
(4)(10000⋯21000⋯54100⋯1414610⋯42482781⋯⋮⋮⋮⋮⋮⋱)(12345⋮)=(14424344⋮).
Another proof of the above identity is given by Woan et al. [7] while computing the areas of parallelo-polyominoes via generating functions. In [8], a combinatorial interpretation of the matrix identity (4) is also obtained.In [9], Radoux introduced a triangle of numbers
(5)cn,k=2k+1n+k+1(2nn-k),wheren≥k≥0,
and he presents the identity ∑k=0n‍(2k+1)cn,k=22n with n≥k≥0, which is equivalent to following matrix equation:
(6)(10000⋯11000⋯23100⋯59510⋯14282071⋯⋮⋮⋮⋮⋮⋱)(13579⋮)=(14424344⋮).
Deng and Yan [10] proved this identity by using the Riordan array method.Aigner [11] introduced a number triangle with the entries given by
(7)an,k=k+1n+1(2n-kn-k),wheren≥k≥0.
This array is also discussed in [12–14].We use theA-sequence and Z-sequence of Riordan array to characterize the inverse relation associated with the Riordan array. We apply this result to prove some combinatorial identities involving Catalan matrices and binomial coefficients, which are generalizations of (4) and (6). In addition, a unified form of Catalan matrices is introduced.


## 2. Riordan Arrays

In the recent literature, one may find that Riordan arrays have attracted the attention of various authors from many points of view, and many examples and applications can be found (see, e.g., [13, 15–21]). An infinite lower triangular matrix D=(dn,k)n,k≥0 is called a Riordan array if its column k has generating function g(t)f(t)k, where g(t) and f(t) are formal power series with g0=1, f0=0, and f1≠0. The Riordan array is denoted by D=(g(t),f(t)). Thus, the general term of Riordan array D=(g(t),f(t)) is given by
(8)dn,k=[tn]g(t)f(t)k,
where [tn]h(t) denotes the coefficient of tn in power series h(t). Suppose we multiply the array D=(g(t),f(t)) by a column vector (b0,b1,b2,…)T and get a column vector (a0,a1,a2,…)T. Let b(t) be the ordinary generating function for the sequence (b0,b1,b2,…)T. Then it follows that the ordinary generating function for the sequence (a0,a1,a2,…)T is g(t)b(f(t)). If we identify a sequence with its ordinary generating function, the composition rule can be rewritten as
(9)(g(t),f(t))b(t)=g(t)b(f(t)).
This is called the fundamental theorem for Riordan arrays, and this leads to the multiplication rule for the Riordan arrays:
(10)(g(t),f(t))(h(t),l(t))=(g(t)h(f(t)),l(f(t))).
The set of all Riordan arrays forms a group under ordinary multiplication. The identity is (1,t). The inverse of (g(t),f(t)) is
(11)(g(t),f(t))-1=(1g(f¯(t)),f¯(t)),
where f¯(t) is compositional inverse of f(t).Lemma 1 (see [22, 23]).
LetD=(dn,k) be an infinite lower triangular matrix. Then D is a Riordan array if and only if d0,0=1 and there exist two sequences A=(ai)i≥0 and Z=(zi)i≥0 with a0≠0 and z0≠0 such that
(12)dn+1,k+1=a0dn,k+a1dn,k+1+a2dn,k+2+…,n,k=0,1,…,dn+1,0=z0dn,0+z1dn,1+z2dn,2+…,n=0,1,….
Such sequences are called the A-sequence and the Z-sequence of the Riordan array D=(g(t),f(t)), respectively.Lemma 2 (see [22, 23]).
LetD=(g(t),f(t)) be a Riordan array, and let A(t) and Z(t) be the generating functions for the corresponding A- and Z-sequences, respectively. Then we have
(13)g(t)=11-tZ(f(t)),f(t)=tA(f(t)).
If the inverse of D=(g(t),f(t)) is D-1=(d(t),h(t)). Then
(14)A(t)=th(t),Z(t)=1-d(t)h(t).Example 3.
(a)   It is well known that the Pascal matrixP=((ij))i,j≥0 can be expressed as the Riordan array (1/(1-t),t/(1-t)), and the generating functions of its A- and Z-sequences are A(t)=1+t,Z(t)=1. More generally, it is easy to show that the generalized Pascal array P[x]=(xi-j(ij))i,j≥0 can be expressed as the Riordan matrix (1/(1-xt),t/(1-xt)) and the generating functions of its A- and Z-sequences are A(t)=1+xt, and Z(t)=x.
(b)  For nonnegative integers, the Pascal functional s-eliminated matrix Ps was introduced in [24] by Ps=(xi-j(i+sj+s))i,j≥0. We have Ps=(1/(1-xt)s+1,t/(1-xt)), and the generating functions of its A- and Z-sequences are A(t)=1+xt, Z(t)=((1+xt)s+1-1)/(t(1+xt)s). We also have Ps-1=(1/(1-xt)s+1,t/(1-xt))-1=(1/(1+xt)s+1,t/(1+xt)).Definition 4.
Let(rn(x))n≥0 be a sequence of polynomials, where rn(x) is of degree n and rn(x)=∑k=0n‍rn,kxk. We say that (rn(x))n≥0 is a polynomial sequence of Riordan type if the coefficient matrix (rn,k)n,k≥0 is an element of the Riordan group; that is, there exists a Riordan array (g(t),f(t)) such that (rn,k)n,k≥0=(g(t),f(t)). In this case, we say that (rn(x))n≥0 is the polynomial sequence associated to the Riordan array (g(t),f(t)).If(rn(x))n≥0 is the polynomial sequence associated to a Riordan array (g(t),f(t)), and let r(t,x)=∑n=0∞‍rn(x)tn be its generating function, then by (9), we have
(15)(g(t),f(t))11-xt=r(t,x).
Thus, r(t,x)=g(t)/(1-xf(t)). The notion of the polynomial sequence of Riordan type was introduced in [25], and it has been studied by [26]. In this paper, by studying the polynomial sequence of Riordan type related to some Catalan type matrices, we obtain some interesting identities and inverse relations.Theorem 5.
LetD=(g(t),f(t)) be a Riordan array, and let A(t) and Z(t) be the generating functions of its A-sequence and Z-sequence. If B(t)=(A(t)-tZ(t))/(A(t)-xt), then
(16)(g(t),f(t))B(t)=11-xt,
where x is any real number.Proof.
LetB(t)=(A(t)-tZ(t))/(A(t)-xt); then (g(t),f(t))B(t)=g(t)B(f(t))=(1/(1-tZ(f(t))))((A(f(t))-f(t)Z(f(t)))/(A(f(t))-xf(t)))=(1/(1-tZ(f(t))))((f(t)-tf(t)Z(f(t)))/(f(t)-xf(t)))=1/(1-xt).Corollary 6.
LetD=(g(t),f(t)) be a Riordan array. If A(t) and Z(t) are the generating functions of its A-sequence and Z-sequence, respectively, and if (φn(x))n≥0 is the polynomial sequence associated to the Riordan array D-1=(1/g(f¯(t)),f¯(t)), then
(17)∑n=0∞‍φn(x)tn=A(t)-tZ(t)A(t)-xt.Proof.
By the theorem, we have(18)(g(t),f(t))A(t)-tZ(t)A(t)-xt=11-xt.
Hence,
(19)(g(t),f(t))-111-xt=A(t)-tZ(t)A(t)-xt.
The result then follows from identity (15).Corollary 7.
LetD=(dn,k) be a Riordan array. If A(t) and Z(t) are the generating functions of its A-sequence and Z-sequence, respectively, and if (φn(x))n≥0 is the polynomial sequence associated to the Riordan array D-1, then
(20)∑k=0n‍dn,kφk(x)=xn,∑k=0n‍d¯n,kxk=φn(x),
where d¯n,k is the (n,k)-element of D-1. In matrix form, we have
(21)(d0,00000⋯d1,0d1,1000⋯d2,0d2,1d2,200⋯d3,0d3,1d3,2d3,30⋯d4,0d4,1d4,2d4,3d4,4⋯⋮⋮⋮⋮⋮⋱)(φ0(x)φ1(x)φ2(x)φ3(x)φ4(x)⋮)=(1xx2x3x4⋮).Example 8.
The lower triangular matrix in (4) may be represented as
(22)(C(t)2,tC(t)2)=(1-2t-1-4t2t2,1-2t-1-4t2t).
The generating functions of its A- and Z-sequence are A(t)=1+2t+t2,Z(t)=2+t. Because (A(t)-tZ(t))/(A(t)-4t)=1/(1-t)2=∑n=0∞‍(n+1)tn, from Theorem 5, we have
(23)(C(t)2,tC(t)2)1(1-t)2=11-4t.
This is exactly the matrix identity (4).Example 9.
The lower triangular matrix in (6) can be written as
(24)(C(t),tC(t)2)=(1-1-4t2t,1-2t-1-4t2t).
The generating functions of its A- and Z-sequence are A(t)=(1+t)2,Z(t)=1+t. Since (A(t)-tZ(t))/(A(t)-4t)=(1+t)/(1-t)2=∑n=0∞‍(2n+1)tn, from Theorem 5, we have
(25)(C(t),tC(t)2)1+t(1-t)2=11-4t.
This is exactly the matrix identity (6).


## 3.    Inverse Relations Determined by Catalan Matrices

Leta, b be integer numbers, and let r be arbitrary parameter. We define the generalized Catalan matrix C[a,b;r] to be the Riordan array
(26)C[a,b;r]=(C(rt)a,tC(rt)b),
where C(t) is the generating function of Catalan sequence defined in (2). From [27], we have C(t)a=∑n=0∞‍(a/(2n+a))(2n+an)tn for any integer number a. Hence [tn]C(rt)a(tC(rt)b)k=[tn-k]C(rt)a+bk=((a+bk)/(2n-2k+a+bk))(2n-2k+a+bkn-k)rn-k. Therefore, by (8), the generic element of the generalized Catalan matrix C[a,b;r] is given by
(27)C[a,b;r]n,k=a+bk2n-2k+a+bk(2n-2k+a+bkn-k)rn-k.
Denote C[a,b]=C[a,b;1]=(C(t)a,tC(t)b). For 0≤a, b≤2, the corresponding matrices C[a,b] are widely studied by many authors [5, 12, 14, 15, 28, 29]. For example,  C[1,0]=(C(t),t)=((1-1-4t)/2t,t), C[0,1]=(1,tC(t)), C[2,0]=(C(t)2,t), and C[0,2]=(1,tC(t)2)=(1,C(t)-1). The matrix C[1,1]=(C(t),tC(t)) is the Catalan triangle introduced by Aigner [11] and studied in [6, 12, 13]. The matrix C[2,2]=(C(t)2,tC(t)2) is the Catalan triangle defined by Shapiro [5]; see also (4). The matrix C[1,2]=(C(t),tC(t)2) is the Catalan matrix defined by Radoux [9]; see also (6).Theorem 10.
Let{Fn(x,r)} be the polynomial sequence associated to the Riordan array C[1,1;r]-1=(C(rt),tC(rt))-1. Then, the identities
(28)∑k=0n‍k+1n+1(2n-kn-k)rn-kFk(x,r)=xn,∑k=0n‍(k+1n-k)xk(-r)n-k=Fn(x,r),
hold for every n∈ℕ.Proof.
From generic term given in (27) with a=1 and b=1, we have the generic term of Catalan matrix C[1,1;r]=(C(rt),tC(rt)) which is C[1,1;r]n,k=((1+k)/(2n-2k+1+k))(2n-2k+1+kn-k)rn-k, and by simplifying we obtain C[1,1;r]n,k=((k+1)/(n+1))(2n-kn-k)rn-k. Using (11) and (14), we get C[1,1;r]-1=(1-rt,t(1-rt)), and the generating functions of its A- and Z-sequences are A(t)=1/(1-rt) and Z(t)=r/(1-rt). By Corollary 6, ∑n=0∞‍Fn(x,r)tn=(A(t)-tZ(t))/(A(t)-xt)=(1-rt)/(1-xt+xrt2). Therefore, F0(x,r)=1, F1(x,r)=x-r, and Fn(x,r)=xFn-1(x,r)-xrFn-2(x,r), for n≥2. Solving this recurrence relation, we have Fn(x,r)=∑k=0n‍(k+1n-k)xk(-r)n-k. From Corollary 7, we get the results.For the caser=1, x=4, we have ∑n=0∞‍Fn(4,1)tn=(1-t)/(1-4t+4t2)=(1-t)/(1-2t)2=∑n=0∞‍2n-1(n+2)tn. Thus, Fn(4,1)=2n-1(n+2). By Theorem 10, we obtain
(29)∑k=0n‍(k+1n-k)4k(-1)n-k=2n-1(n+2),∑k=0n‍k+1n+1(2n-kn)2k-1(k+2)=4n.
The last identity is equivalent to the following matrix identity:
(30)(100000⋯110000⋯221000⋯553100⋯14149410⋯4242281451⋯⋮⋮⋮⋮⋮⋮⋱)(1382048112⋮)=(1442434445⋮).Theorem 11.
Let{un(x,r)} be the polynomial sequence associated to the Riordan array C[1,2;r]-1=(C(rt),tC(rt)2)-1. Then, for any nonnegative integer n, one has
(31)∑k=0n‍2k+12n+1(2n+1n-k)rn-kuk(x,r)=xn,∑k=0n‍(n+kn-k)xk(-r)n-k=un(x,r).Proof.
From generic term given in (27) with a=1 and b=2, we have the generic term of Catalan matrix C[1,2;r]=(C(rt),tC(rt)2) which is C[1,2;r]n,k=((2k+1)/(2n+1))(2n+1n-k)rn-k. Using (11), we obtain C[1,2;r]-1=(1/(1+rt),t/(1+rt)2). Hence, the generic term of C[1,2;r]-1 is [tn](1/(1+rt))(t/(1+rt)2)k=[tn-k](1/(1+rt))2k+1=(-r)n-k(n+kn-k). By Corollary 7, we obtain the desired results.SinceC[1,2;r]-1=(1/(1+rt),t/(1+rt)2), from Lemma 2, the generating functions of A- and Z-sequences of C[1,2;r] are A(t)=(1+rt)2 and Z(t)=r+r2t. Hence, ∑k=0n‍un(x,r)tn=(A(t)-tZ(t))/(A(t)-xt)=(1+rt)/(1-(x-2r)t+r2t2). For the case r=1 and x=4, we have ∑k=0n‍un(4,1)tn=(1+t)/(1-2t+t2)=(1+t)/(1-t)2=∑k=0n‍(2n+1)tn, and un(4,1)=2n+1. By Theorem 11, we have
(32)∑k=0n‍(-1)n-k(n+kn-k)4k=2n+1,∑k=0n‍2k+12n+1(2n+1n-k)(2k+1)=4n.
The last identity is equivalent to identity (6).For the caser=-1 and x=1, we have ∑k=0n‍un(1,-1)tn=(1-t)/(1-3t+t2)=∑k=0n‍F2n+1tn, and un(1,-1)=F2n+1, where {Fn}n≥0 is Fibonacci sequence with generating ∑k=0∞‍Fntn=t/(1-t-t2). By Theorem 11, we have
(33)∑k=0n‍(-1)n-k2k+12n+1(2n+1n-k)F2k+1=1,∑k=0n‍(n+kn-k)4k=F2n+1.Theorem 12.
Let{vn(x,r)} be the polynomial sequence associated to the Riordan array C[2,2;r]-1=(C(rt)2,tC(rt)2)-1. Then, one has
(34)∑k=0n‍k+1n+1(2n+2n-k)rn-kvk(x,r)=xn,∑k=0n‍(n+k+1n-k)xk(-r)n-k=vn(x,r),
for every n∈ℕ.Proof.
From generic term given in (27) with a=2 and b=2, we have the generic term of Catalan matrix C[2,2;r]=(C(rt)2,tC(rt)2) which is C[2,2;r]n,k=((k+1)/(n+1))(2n+2n-k)rn-k. Using (11), we obtain C[2,2;r]-1=(1/(1+rt)2,t/(1+rt)2). Hence, the generic term of C[2,2;r]-1 is [tn](1/(1+rt)2)(t/(1+rt)2)k=[tn-k](1/(1+rt))2k+2=(-r)n-k(n+k+1n-k). By Corollary 7, we obtain the desired results.The generating functions ofA- and Z-sequences of C[2,2;r] are A(t)=1+2rt+r2t2 and Z(t)=2r+r2t. Thus ∑n=0∞‍vn(x,r)tn=(A(t)-tZ(t))/(A(t)-xt)=1/(1-(x-2r)t+r2t2).For the caser=1 and x=2y+2, we have ∑n=0∞‍vn(2y+2,1)tn=1/(1-2yt+t2)=∑n=0∞‍Un(y)tn, where Un(y) are Chebyshev polynomials of the second kind (see [1]). Hence, by Theorem 13, we have
(35)∑k=0n‍(n+k+1n-k)(2y+2)k(-1)n-k=Un(y),∑k=0n‍k+1n+1(2n+2n-k)Uk(y)=(2y+2)n.
Substituting y=1 in the last identity, we get (4) again.Theorem 13.
Let{wn(x,r)} be the polynomial sequence associated to the Riordan array C[2,1;r]-1=(C(rt)2,tC(rt))-1. Then, one has identities
(36)∑k=0n‍k+2n+2(2n-k+1n-k)rn-kwk(x,r)=xn,∑k=0n‍(k+2n-k)xk(-r)n-k=wn(x,r).Proof.
Using (11), we obtain C[2,1;r]-1=(C(rt)2,tC(rt))-1=((1-rt)2,t-rt2). Hence, the generic term of C[2,2;r]-1 is [tn](1-rt)2(t-rt2)k=[tn-k](1-rt)k+2=(-r)n-k(k+2n-k). From generic term given in (27) with a=2 and b=1, we have the generic term of Catalan matrix C[2,1;r]=(C(rt)2,tC(rt)) which is  C[2,1;r]n,k=((2+k)/(2n-2k+2+k))(2n-2k+2+kn-k)rn-k, and by simplifying we obtain C[1,1;r]n,k=((k+2)/(n+2))(2n-k+1n-k)rn-k. From Corollary 7, we obtain the desired results.The generating functions for theA- and Z-sequences of C[2,1;r] are A(t)=1/(1-rt),Z(t)=(2r-r2t)/(1-rt), and ∑n=0∞‍wn(x,r)tn=(A(t)-tZ(t))/(A(t)-xt)=(1-rt)2/(1-xt+xrt2). For the case r=1 and x=4, we have ∑n=0∞‍wn(4,1)tn=(1-t)2/(1-4t+4t2)=(1-t)2/(1-2t)2=1+∑n=1∞‍(n+3)2n-2tn. By Theorem 13, we have
(37)∑k=0n‍(-1)n-k(k+2n-k)4k=(n+3)2n-2,n≥1,(38)2n+2(2n+1n+1)+∑k=1n‍k+2n+2(2n-k+1n+1)(k+3)2k-2=4n,n≥0.
The matrix form of the last identity is
(39)(10000⋯21000⋯53100⋯149410⋯42281451⋯⋮⋮⋮⋮⋮⋱)(1251228⋮)=(14424344⋮).



---

*Source: 528584-2013-09-24.xml*