Wolfdieter Lang, May 18 2007 Rationals r(n) = A006232(n)/A006233(n) e.g.f: 1/(ln(1+x)/x) r(n): n=0..30: [1, 1/2, -1/6, 1/4, -19/30, 9/4, -863/84, 1375/24, -33953/90, 57281/20, -3250433/132, 1891755/8, -13695779093/5460, 24466579093/840, -132282840127/360, 240208245823/48, -111956703448001/1530, 4573423873125/4, -30342376302478019/1596, 56310194579604163/168, -12365722323469980029/1980, 161867055619224199787/1320, -20953816286242674495191/8280, 4380881778942163832799/80, -101543126947618093900697699/81900, 192060902780872132330221667/6552, -1092286933245454564213092649/1512, 2075032177476967189228515625/112, -1718089509598695642524656240811/3480, 1092041494691940355778302728249/80] This sequence of signed rationals r(n) (called Cauchy numbers of the first kind in OEIS) coincides with the so called a-sequence (see below) for the Sheffer (in this case Jabotinsky) matrix Stirling2 A048993. This sequence r(n)=a(n) determines a recurrence relation for S2(n,m) using all entries in the previous row numbered n-1: S2(n,m)= (n/m)*sum(binomial(m-1+j,j)*a(j)*S2(n-1,m-1+j),j=0..n-m), n>-1, m>=1. E.g.: 3 = S2(3,2) = (3/2)*(1*1*1 + 2*(1/2)*1) = 3; 7 = S2(4,2) = (4/2)*(1*1*1 + 2*(1/2)*3 + 3*(-1/6)*1) = 7. ########################################################################################################## ########################################################################################################## Introduction to A- and Z- sequences for Riordan matrices and a- and z- sequences for Sheffer matrices (special lower triangular infinite matrices): The A- and Z-sequences for Riordan matrices are considered in the papers: D.G. Rogers, Pascal Triangles, Catalan Numbers and Renewal Arrays, Discrete Math. 22(1978)301-310, D. Merlini, D.G. Rogers, R. Sprugnoli and M.C. Verri, On some alternative charcterizations of Riordan arrays, Can. J. Math, 49(1997)301-320, R.Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132(1994)267-290. For Riordan matrices and the Riordan group see the paper: L.V. Shapiro, S. Getu. W.-J.Woan, and L. Woodson, The Riordan Group, Discrete Appl. Math. 34(1991)229-239. ########################################################################################################## Summary on A- and Z-sequences for Riordan matrices: A Riordan matrix R=(G,F) (in our notation) with an o.g.f. G(x) with G(0)=1 and an invertible o.g.f. F(x)=x*Fhat(x) with Fhat(0)=1 is defined by its matrix elements R(n,m):=[(x^n)] G_m(x) with the o.g.f. for column nr. m>=0 given by G_m(x) = G(x)*F(x)^m = G(x)*(x*Fhat(x))^m. The o.g.f. of the row polynomials R(n,x):= sum(R(n,m)*x^m,m=0..n) is R(z,x):= sum(R(n,x)*(z^n)) = G(z)/(1-x*z*Fhat(z)). A Riordan matrix (coefficient matrix of the polynomials) is infinite lower triangular: R(n,m)=0 if n=1; R(0,0):=1 (by convention). (b) For the columns m>=1: R(n,m) = sum(A(j)*R(n-1,m-1+j),j=0..n-m), n>=1, m>=1. The o.g.f.s for the Z- and A-sequences are obtained from G and F of the Riordan matrix as follows: A(y):=sum(a(j)*y^j,j=0..infty) = Fhat(Finv(y))= y/Finv(y) with F(x)=x*Fhat(x) and Finv is the compositional inverse of F. Z(y):=sum(z(j)*y^j,j=0..infty) = (1- 1/G(Finv(y)))/Finv(y). Conversely, the o.g.f.s G and F of the Riordan matrix R are determined from the o.g.f.s A(y) and Z(y) as follows. First, Fhat(x)=A(F(x)) is used to either find f(x) directly from a(y) or a corollary to Lagrange's inversion theorem is emplloyed to give F_j := [x^j]F(x) = diff(A(t)^n,t$(n-1)|_{t=0}, n>=1 and F(0):=0. Then G(x) is found from G(x)=1/(1-Z(F(x))). The proof works for both directions. See the quoted references and the hints given below for the Sheffer case. Example: Pascal's triangle A007318 R=P=(G(x)=1/(1-x),F(x)=x/(1-x)) with the A-sequence generated by A(y)= Fhat(Finv(y)) = 1+y and the Z-sequence generated by Z(y)=1. This leads to the obvious recurrences for P(n,m) and P(n,0). ########################################################################################################## ########################################################################################################## a- and z-sequences are the anloga of A- and Z-sequences for Sheffer matrices. For Sheffer matrices (polynomials) and the Sheffer group see the book: S. Roman, Umbral calculus, Academic Press, 1984. The notation (g=gR,f=fR) of this book translates as follows to our notation S=(g,f) for a Sheffer matrix: gR(t)= 1/g(finv(t))), fR(t)= finv(t), with the compositional inverse finv(t) of f(x). Conversely, g(x)=1/gR(fRinv(x)), f(x)=fRinv(x), with the compositional inverse fRinv(x) of fR(t). For the subgroup of the Sheffer group (1,f) called Jabotinsky subgroup, see the paper: D. E. Knuth, Convolution polynomials, The Mathematica J., 2(1992)67-78. ########################################################################################################## A Sheffer matrix S=(g,f) with e.g.f. g(x) with g(0):=1 and an invertible e.g.f. f(x) with f(0)=0 is defined by its matrix elements S(n,m):=[(x^n)/n!] g_m(x) with the e.g.f. for column nr. m>=0 given by g_m(x)=g(x)(f(x)^m/m!). The e.g.f. of the row polynomials s(n,x):=sum(S(n,m)*x^m,m=0..n) is s(z,x):= sum(s(n,x)*(z^n)/n!) = g(z)*exp(x*f(z)). A Sheffer matrix (coefficient matrix of the polynomials) is infinite lower triangular: S(n,m)=0 if n=1; S(0,0):=1 (by convention). (b) For the columns m>=1: S(n,m) = (n/m)*sum( binomial(m-1+j,m-1)*a(j)*S(n-1,m-1+j),j=0..n-m), n>=1, m>=1. The e.g.f.s for the z- and a-sequences are obtained from g and f of the Sheffer matrix as follows: a(y):=sum(a(j)*(y^j)/j!,j=0..infty) = fhat(finv(y)) = y/finv(y) with f(x)=x*fhat(x) and finv is the compositional inverse of f. z(y):=sum(z(j)*(y^j)/j!,j=0..infty) = (1- 1/g(finv(y)))/finv(y). Conversely, the e.g.f.s g and f of the Sheffer matrix S are determined from the e.g.f.s a(y) and z(y) as follows. First, f(x)=x*a(f(x)) is used to either find directly f(x) from a(y) or a corollary to Lagrange's inversion theorem is employed to give f_j := [(x^j)/j!]f(x) = diff(a(t)^n,t$(n-1)|_{t=0}, n>=1 and f(0):=0. Then g(x)=1/(1-z(f(x))). The proof works for both directions. (a) Insert the recurrence for S(n,0) into g(x)=1 + sum(S(n,0)*(x^n)/n!,n=1..infty), interchange the sums (formal power series here), building the e.g.f. g_j(x) and use its Sheffer structure. This produces g(x)= 1+x*g(x)z(f(x)). From this one finds g(x)=1/(1-x*z(f(x))) or z(y) = (1- 1/g(finv(y)))/finv(y). This argument can be reversed. (b) Insert the recurrence for S(n,m) into g_m(x)= 0 + sum(S(n,m)*(x^n)/n! ,n=1..infty), interchange the sums (formal power series), finding the e.g.f. g_{m-1+j}(x) and use its Sheffer structure. The factorials are rearranged to produce g_m(x)*(x*a(f(x)))/f(x). This shows that a(f(x))=fhat(x) with fhat(x)=f(x)/x. This argument can also be reversed. ######################################################################################################## Note: This recurrences (a) and (b) are not always the simplest one for S(n,m). E.g. Stirling2 = A048993, which has z(y)=0 from g(x)=1 (this is what one expects for the first m=0 column) but finv(y)=ln(1+y) leading to a(y)=1/(ln(1+y)/y), which generates the sequence A006232(n)/A006233(n). Hence all entries of the previous row stating with S2(n-1,m-1) are needed for S2(n,m). The usual recurrence used for S2(n,m) needs only to terms of the previous row. See the recurrence for Sheffer polynomials given as next item. ######################################################################################################## ######################################################################################################## There is also a recurrence for the row polynomials s(n,x):=sum(S(n,m)*x^m,m=0..n) for every Sheffer matrix S=(g,f). In the general case it uses formal series expansion employing a corollary of Legendre's inversion theorem. s(n,x) = (x+(ln(g(finv(t))))')/finv'(t)|_{t -> d_x} s(n-1,x), n>=1; s(0,x)=1. Here ' denotes derivative w.r.t. t, finv is the compositional inverse of f and d_x=d/dx is the derivative w.r.t. x (powers of t should to be replaced by powers of d_x). This formula is the rewritten version of S. Roman's book (op. cit.) p. 50, Corollary. The proof uses the fact that finv(d_x) s(z,x) =finv(f(z)) s(z,x) = z s(z,x) with the e.g.f. s(z,x) for the row polynomials given above, and d_x=d/dx is the derivative w.r.t. x. This folows from del_x^k s(z,x) = f(z)^k s(z,x) together with del_z s(z,x) = ( ln(g(z))' +x*f'(z))*s(z,x) with ' denoting differentiation w.r.t. z, and del_x, resp. del_z stands for the partial derivative w.r.t. x, resp. z. ############################################################################### In the Stirling2 case, with finv(t)=ln(1+t) and g(t)=1 this recurrence becomes S2(n,x) =x*(1 + d_x)*S2(n-1,x), n>=1, S2(0,x)=1, with the row polynomials S2(n,x):=sum(A048993(n,m),m=0..n). Comparing coefficients of powers of x leads to the known three term recurrence S2(n,m) = S2(n-1,m-1) + m*S2(n-1,m). The inputs are: S(0,0)=1, S(n,-1)=0 and S(n,m)=0 if n