DISCRETE MATHEMATICS ELSEWIER Discrete Mathematics 142 (1995) 213-233 Riordan arrays and the Abel-Gould identity Renzo Sprugnoli* Dipartimento di Sisiemi e Informatica, Via Lombroso 6117, Firenze, Italy Received 5 August 1993 Abstract We generalize the well-known identities of Abel and Gould in the context of Riordan arrays. This allows us to prove analogous formulas for Stirling numbers of both kinds and also for other quantities. 1. Introduction Recently, Shapiro et al. [S] have formally introduced the concept of a Riordan group; it corresponds to a set of infinite, low-triangular arrays charac- terized by two analytic functions: the first is invertible and the second has a compositional inverse. Even though the concept can be traced back to a paper by Rogers [6] on renewal arrays, the authors give a clear formulation of the theory of Riordan arrays and relate it to the l-umbra1 calculus, as described, for instance, by Roman [7]. We believe that Riordan arrays are particularly important not only theoretically but also because they constitute a practical device for solving combinatorial sums by means of generating functionasr.r aTyhse sea re precisely the class of objects that allow us to translate a sum CiZo dn,kfk into a suitable transformation of the generating functionf(t)=B,{fk)tEN= 9 {f ,} of the sequence {f k}fe N. In [9] we tried to give an accurated escription of this fact. Moreover, the concept of Riordan group is strictly related to the Lagrange inver- sion formula (LIF) which, in turn, is the natural device for inverting the elements in the group. In particular, many traditional applications of the LIF can be approached from a Riordan array point of view. In this paper, we focus our attention on the following two identities of Abel and Gould, respectively: (1.1) 0012-365X/95/%09.50 0 1995-Elsevier Science B.V. All rights reserved SSDI 0012-365X(93)E0220-X 214 R. S p r u g n o l i l Discrete M a t h e m a t i c s 1 4 2 ( 1 9 9 5 ) 2 1 3 - 2 3 3 ( 1 . 2 ) We show t h a t they are special cases of a general theorem w i t h i n the theory of Riordan arrays a n d t h i s theorem allows u s to prove s i m i l a r formulas for other quantities, such a s Stirling numbers of both k i n d s . In Section 2 we introduce the concept of the Lagrange group, whose properties are pre-requisite to the introduction of the Riordan group. In Section 3 we give our formulation of the Riordan array concept (which i s slightly different from Shapiro’s ) a n d prove our m a i n theorem on s u m s . The rest of the paper i s devoted to the applications of t h i s theorem. A s far a s our notations are concerned, we write [f(y) ( y = g(t)] instead of the more because the latter can become rather cumbersome when g(t) i s traditionalf(y)(,,,(,,, not simple. For example, we give the l a w explicitly: a s s o c i a t i v e Cf~Y~IY=C~~~~I~=~~~~ll=ECf~Y~IY=~~~~lI~=~~~~l in which both expression equalf(g(h(t))). 2 . The L a g r a n g e group Let 9 be the set of the formal power series on some indeterminate i.e. 9 = t, R[t]. Even though the set Iw of real numbers can be substituted by any field w i t h F 0 characteristics, here we are mainly interested in formal power series w i t h real coefficients. The of a formal power seriesf(t)EP i s the s m a l l e s t integer o(f(t)) o r d e r for which the coefficientf, of i s different from 0 . So we have w(O)=co. If 9 ,‘ denotes t k k the set of formal power series of order it i s well known t h a t a seriesf(t) i s invertible if k , a n d only iff(t)EPo. Two operations are defined in 9: the s u m , denoted by + , a n d the convolution or Cauchy product, denoted by or the simple juxtaposition. W i t h these operations, B i s - a n integrity domain (9, + , . ) . If then the convolution i s f(t)eF,,, f ( t ) g ( t ) = h ( t ) invertible in the sense t h a t knowing h(t), we can go back to In fact, by multiplying g ( t ) . both s i d e s byf(t)-‘, we obtain In particular, (PO,*) i s a group. g ( t ) = f ( t ) -‘h(t). Let u s now introduce the following operation, which we call L a g r a n g e p r o d u c t : (2.1) f ( t ) @ g ( G = _ f ( O g ( t _ f ( t ) ) f This product i s associative: f(t) @(g(t) 0 h@))=f(t) @ g(M(4J(~))=f(M~f(~)M_f(M~f(~))) =(f(Mtf(0)) 0 40=(f(t) @ g(t)) @ h(t); it h a s a n identity: f(t) 8 1 =f(t) = 1 @f(t) R. Sprugnolij Discrete Mathematics 142 (1995) 213-233 215 and can be distributed to the terms of a sum: J-(t)0 (s(t)+h(t))=f(t)(g(tf(t))+h(tf(t))) =f(t)g(tf(t))+f(t)h(tf(t))=f(t) 0 s@)+fO)0 W’ Again, (9, +, 8) is an integrity domain and iff(t)EFO, the Lagrange product can be inverted and we obtain f(t) C3s (~)=~(~)=f(M~f(O)> s(tf(Q)=“f(t)- ‘h(t). By now setting Y= tf(t), we find g(y)=Cf(t)-‘h(t)It=yf(t)-‘l. Whenf(t)EF,,, the hypotheses of the LIF are satisfied, so g(t) exists and is uniquely determined. In particular, (F,,, 0) is a group called the Lagrange group. The inverse of a seriesf’(t)Eq,, is denoted by f(Y)=C.f(VIt=Yf(V’l. (2.2) Some examples are now in order. First, let us consider f(t)=(l -t)-‘, and deter- mine f(y) by setting y=t/(l -t), i.e. t=y/(l +y). Hence we have J(y)= [l --t ) t= y/( 1 + y)] = l/( 1 + y). A more complex example isf(t) = l/m; in this case, too, we can find an explicit form for t, i.e., t=yJiGp-2y 2, from which we have T(t)= dm--2y. Finally, let us consider f(t)=e-‘; by (2.2) f(y)=[e’lt=ye’] and by a simple application of the LIF, f.=[y”][e’lt=ye’]=~[t”‘](De’)e” =; [yl] e~“+l~~=t’;~~:;ll=‘~+~i”-’ . Sincefo=f;’ = 1, this formula is valid for every n~fV, and hence: @+lI”-’ J(t)= f t”=&J(t). n. n=O This is a rather complicated expression and, as far as I know, it cannot be expressed in terms of elementary functions. It is not difficult to establish a number of elementary properties of the Lagrange product, and, therefore, of the Lagrange group, too. For example (CCEIR): M@ f(t)=@-(at), f(t) 0 tk =(rf(r))kf(t) 3 f(t) 0 (s(t)h(t))=f(t)_‘(f(t) 0 swKm 60 W) 216 R. Sprugnolil Discrete Mathematics 142 (1995) 213-233 and so on. However, it seems to us that the most important properties of the Lagrange product are its two identities, which we are now going to prove. Forf(t)E9,,, let us introduce the following notation: &/,(r)=Cg(Y)IY=V(Y)-‘l. Note thatf;&)=f(t)- ‘. Whenf(r) is fixed, the subscript (f) is understood. We now have &&f(O)= Kg(y) I Y =rf(~)-‘I I ~=cf(Ol =Cs(v)l~=~f(r)f(y)-‘l=Cg(y)Iyf(y)=rf(r)l=g(r) since when f(r) is invertible, i.e. f(r)&F,,, yf(y) = rf(r) implies y = r. We also find s(tf(r))=Cs(z)lZ=rCf(Y)-1Iy=rf(y)-111 =CC~~~~I~=~f~~~f~~~~‘lI~=~f~~~-11=C~~~~I~=~f~~~-1l=~o,~~~. Consequently, we can state formally the following result. Theorem 2.1. Iff(r) is invertible, in particular iff(r) and g(r) belong to the Lagrange group, then the two identities hold: &.&f(r)) =g(r) (2.3) As a simple example, let us consider g(r) = e’ andf(r) = e-‘; as we have already seen, f(r)=&(r)=&-,(r)=[eYIy=ret]. Hence, we have &(re-‘)=e’ exp(r&(r))= 6(r). 3. The Riordan group The set 9 of formal power series can be identified with the set of sequences Y={ {fn}nEN}o f real numbers. If {f,),,N ~9, the corresponding formal power series f(r)r# isf(r)=J-$,f,r”, and{(r) is called the generatingfunction of the sequence. We writef(O=%{fnJnaN =B{f”}, when there can be no confusion on the binding of n and r. Let Y be the set of linear operators on 9’. If AEY, A can be represented by an infinite, bidimensional array A={u”,~ I n, keN}, such that every row only contains a finite number of elements different from 0. IffeY, i.e.,f= {fn}neN,fis represented as a column vector, and if Af=g, then we have g. =CFzO a,,+&, but the sum is actually finite. The product of two linear operators A and B is denoted by AB or A * B and is defined by (AB)f= A(Bf), for everyfos. In the array representation, AB corresponds to the usual row-by-column product of the two arrays A and B. Hence, the product is R. Sprugnoli/ Discrete Mathematics 142 (1995) 213-233 211 associative and has the identity operator I as the only identity; moreover, the product can be distributed to the terms of a sum A + B, and some operators AEY have an inverse A- ’ such that AA- 1 = A- ‘A = I. Since for some A, BE 9 and different from 0, we can have AB=O, we conclude that (2, +, *) is a ring with zero divisors. An operator A = {Q ) n, kE N} can also be represented by its bivariate generating function A(t, w)=&~ ~,,~t”wI’,a nd we often refer to its column generating functions (C,?==,%k tn}kEN.A n important class of linear operators is defined in terms of Column generating functions. Let d(r),h(t) be two invertible formal power series, i.e., d(t),h(t)~~e. A Riordan array is an array D=(d(t),h(t))={d,,,(n,k~N}, whose kth column generating function is defined as d(t)(th(t))k. By this definition, it can be easily seen that D is a low-triangular bidimensional array and, therefore, it is a linear operator in 2. The following is a simple example, based on the Riordan array D=((l -t)-I,(1 -t)-‘); the element dnqk is defined as the nth coefficient in the kth column generating function for D, i.e. 1 tk dn,k=[t”l 1_t I_t =[t”-k] (l+k+l ( ) Hence D is the Pascal triangle. A basic property of Riordan arrays is the following one: let D=(d(t),h(t)) be a Riordan array and let f(t)=%{ f.} be the generating function of any sequence {fn)ncN ~9. We then have ~d~,,f,=~C~“ld(~)(~~(t))‘[y’lf(y) = CW(O~ C~~lf(~)(th(t))~=Ct”ld(t)f(ch(t)). (3.1) k This means that the sum Ck dnvkfk can be reduced to the extraction of the coefficient of t” from the function d(t)f(th(t)), which is a simple transformation of the generating functionf(t) and the two functions defining the Riordan array. For example is the well-known Euler transformation. In [9] we illustrated many applications of this result about Riordan arrays. Formula (3.1) can also be written as and the same argument can be extended to every array F whose column generating functionsf&)=xn f&” are known. In fact, we obtain (d(t), h(t)) *f(r, w)=~4Mo~(0)wk k 218 R. Sprugnoli / Discrete Mathematics 142 (1995) 213-233 and this corresponds to the row-by-column product D * F= DF. When F is a Riordan array, say F = (u(t), b(t)), we have fk(t) = a(t)(tb(~))~ and therefore (40, W) * (4th b(t))= f 40 C4Y)(YUYNk I Y = w01 Wk k=O 2 = d(t)u(th(t))(th(t)b(th(tk)W)) k=(d(t)u(th(t))h, (t)b(th(t))). k=O This is the proof that the product of two Riordan arrays is a Riordan array. Furthermore, since I=(l, 1) is a Riordan array, we obtain that the identity I is in the set R of Riordan arrays, and from: (d(t), h(t)) *(a(r), b(t)) =(4r)4&)), Nr)b(th(O)) =(I, 1) 3 we find that in the notations of the Lagrange group. Therefore, (d(t), h(t)) has an inverse and (W, *) is a group, called the Riordun group. Many properties of the Riordan group are described in [8,9]. In the present paper, we are primarily interested in the following result, which we call the Abel-Gould identity. Theorem 3.1. Let D=(d(t), h(t)) be a Riordun array and let f(t) be the generating fin_ction ofu sequence {fn}neNE9. Zf{i},,N is the sequence, whose generating function isJs(t)=[f(t)I t=yh(t)-‘1, then: 2 dnd=~f’]d(%f(~). (3.2) k=O Proof. By means of the elementary properties of the Riordan and Lagrange groups (see formulas (3.1) and (2.3)) we immediately find d,,kl=t : Ct”ld(r)f;,,(th(O)= Cc”1& )f(r). k=O The most common example of this is the Abel identity. Let D be the Riordan array (e”, e@) and let f(t) = e”, with p, q, rE (w.T hen we have (P+4k)"-k dn,k = [t”] e”(teqr)k= [tnmk] e(P+qkj=r (n-k)! ’ r (r-qk)‘-’ (r-qk)k-l =k (k-l)! =r k! ’ R. Sprugnoli/ Discrete Mathematics 142 (1995) 213-233 219 The theorem now gives b+4Wk r(r-4k)k-1=Ct.,eFe”=(P+r)” f (n-k)! k! n! ’ kZO which is usually written as k-l(p+qk)“_k=(p+r)“. (3.3) It is now sufficient to set r=u, q=-1, p=b+n to obtain (1.1). 4. The Abel identity Identities (2.1) and (3.3) are special cases of a more general identity. Let us re-examine the Riordan array D = (em, e@), with p, q E R, and let f(t) = Pe”. For k # 0, k 2 s, we have s (r-qk)‘-’ r(k-s) (r-qk)‘-’ r-qs (r-qk)k-s =k (k-s)! +k(r-qk) (k-s)! =- r-qk (k-s)! f For k=O we use the formula (see [4, p. 171): (4.1) When S-CO we find which coincides with the previous expression for Fk having k =O. Theorem 3.1 now gives m (p+qk)“-k r-qs (r-qk)k-‘=(p+r)n-s kzS (n-k)! r-qk (k-s)! (n-s)! and this can be written as (4.2) 2 2 0 R . S p r u g n o l i / D i s c r e t e M a t h e m a t i c s 1 4 2 ( 1 9 9 5 ) 2 1 3 - 2 3 3 Obviously, formula (3.3) i s obtained by setting s = O , a n d the constant can also r - q s be moved to the right-hand side. Form (4.2) i s usually preferred, because it emphasizes the fact t h a t the right-hand member does not depend on a n d t h i s may seem rather q , s u r p r i s i n g . If we s t a r t w i t h (4.2) a n d specialize the values of a n d s , a great number of p , q , r familiar identities can be obtained. For example, by setting p = 0 , 1 , q = - r = x , s = 0 , have w e which i s in [S, p . 9 7 1 . Analogously, for p = n + 1 , -1, r = O , s = 1 , we obtain q = kk-2(n-k+l)“_L(,+l)“-1. However, since by multiplying both members by n we find ( “ , I : ) = ( i ) k / n , l)“- k = n ( n + l)“-i k k -‘( n - k + a n d t h i s i s Problem 1 in [S, p . 1 1 6 1 . A third example, also taken from [S, p . 1 1 7 1 i s obtained for p = n , s = l : q = O , r = l , n-k_ kn”-k-l=(n+l)“-‘. n - It i s worth noting t h a t r = 2 gives the second identity in the same problem. The inverse relations are obtained for p = 0 , 1 , 1 , s = 0: q = - r = (-l)n+kkn-k(k+ l)k-’ = 1 , while for p = O , q = - 1 , r = 2 , s = O : Formula (4.2) generalizes these identities to every value of r . Another couple of inverse relations [S, p . 1 1 9 1 are obtained for p = 1 , n , q = 0 , r = - s = 1 a n d 1 , r = l , s = O : p = O , q = (-l)‘-‘n”-k (-l)k-lkn”-k-1=(,-1)“-‘, R. Sprugnoli/ Discrete Mathematics 142 (1995) 213-233 221 The following two examples are taken from [2, Exercises 2.4.2.~ and 2.4.2.a]. By setting p = x + n, q = - 1, r = c(, s = 0 and performing the transformation k-n - k, we have m L a(a+n-k)“-k-l(x+k)k=(x+n+a)n. zo k=O By isolating the term for k = n, which evaluates at (x + n)“, and by moving it to the right-hand member, we eventually find (a+n_k)“-k-l(x+k)k=(X+n+a)“-(x+n)”~ a Analogously, for p= n, q = -1, r=O, s= 1, we obtain We can now observe that (“,I:)=(“;‘)k/(n-k) except when k=n. By isolating the corresponding term and moving it to the right-hand member, we eventually obtain the identity desired: The applications of (4.2) are not always so direct. For instance, let us consider the Csorgo-Bhaskaranada identity (/.?# n): which is Exercise 2.4.2.b in [2]. By setting s =0 and n = n + 1, formula (4.2) becomes By isolating the term for k=n+ 1 and by moving it to the right-hand member, we observe that ( .;:!k)=(E)(n+l)/(n-k+l) except for k=n+l, and the identity he- comes cn (n ) F ~(‘_~k)k-l(p+qk)“+l-k=(p+l)ltl~~((r_q--qn)”. kc0 k n-k+1 We can now perform the substitution k-m-k and set q=- 1: r”+‘-r(r+l+n)” k+l(l+n-k)“-kml(p-n+k)k+l=(p’ ) n+l 2 2 2 R. S p r u g n o l i l D i s c r e t e Mathematics 1 4 2 ( 1 9 9 5 ) 2 1 3 - 2 3 3 Finally, we set a = p - n , B = a n d obtain r + n , _ ( a + B )“‘L;jP: (kn)& l)“( b - 4 . (yfo (,+k)k+l(p+n-k-l (4.3) By u s i n g formula (4.2) a g a i n w i t h s = O , -1, we find q = The substitution now gives k - m - k n l r ( r + n - k ) “ - k - l ( p - n + k ) k = ( p + r ) ” + k = O a n d by setting a g a i n , we obtain a = p - n , B = r + n ( a + k ) k ( j ? - k ) n - k - l = ( a + / I ) n . (@)jo (3 A t t h i s point, we s u b s t r a c t t h i s formula from (4.3), perform a l l possible simplifications a n d eventually obtain the Csorgo-Bhaskaranada identity. From the basic relation (4.2), we can obtain some other interesting identities. For example, let u s call S, the s u m in (4.2); then we have I I - 1 c (n-s)S,_1= (n-s) k = s = ( n - s ) ( p + r ) “ - “ - I . We can now observe t h a t (n-s)! (n-s) = ( n - k ) ! ( k - s ) ! = which i s also valid for can extend the s u m in to a n d s u m k = n . S o w e ( n - s ) S , _ 1 k = n t h a t quantity to, or s u b s t r a c t it from S,: =(p+r)“-“-‘( p + r + ( n - s ) ) . ( 4 . 4 ) Here we give two applications of formula (4.4). We first examine the case having p = O , q = l , a n d the s i g n + : r = n , s = O