A157162 W. Lang, Mar 31 2009 Series <-> (reciprocal product) transformation of sequences. (see also the WL link under A147542) A) For unital exponential generating functions (e.g.f.s), i.e., f(x) = 1 + sum(f[k]*(x^k)/k!, k=1..infty) (as formal power series) one asks for the sequence b[j], j>=1, which satisfies f(x) = 1/product(1 - b[j]*(x^j)/j!, j=1..infty) (also in the formal sense). If successful, this will map the sequence {f[k]},k=0,1,.., (with f[0]=1) to the sequence {b[j]},j=0,1,... (with b[0]=0). The author likes to thank P. D. Hanna (March 2009) for an explanation of the recurrence II below involving divisors. V. Jovovic (March 2009) gave the simplification of recurrence II below for similar cases. Recurrence I: A direct comparison of the coefficients of x^n leads to: x^0: 1 = 1 , x^1: b[1] = f[1], and for x^n with n>=2, f[n] = sum(sum(M1(n;vec(e))*b[1]^e_1*... *b[n]^e_n, vec(e)=(e_1,e_2,...,e_n) from P(n,m)),m=1...n), where P(n,m) is the set of partitions of n with m parts. The partition of n is written as p=(1^e_1,...,n^e_n) with sum(j*e_j, j=1..n)=n and sum(e_j,j=1..n)=m, with all e_j >=0. If e_j=0 then the part j does not appear. E.g., P(5,2) is a set of two elements namely the partitions (1,4)=(1^1,4^1) and (2,3)= (2^1,3^1). Both have vec(e)=(1,1). That the multinomial numbers M1(n,vec(e):=n!/product(j!^e_j,j=1..n) appear is clear. These numbers are found in Abramowitz-Stegun (A-St), p.831-2, and as array Sloane's OEIS A036038 for the partitions for n=1..10. This f[n] eq. is now rewritten as a recurrence for b[n] by splitting the m=1 term in the first (outer) sum: m=1 has always one partition (n)(which is the sole member of P(1,1)) with M1 number 1. Therefore the recurrence I is: b[n] = f[n] - sum(sum(M1(n;vec(e))*b[1]^e_1*... *b[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m)), m=2..n), n>=2, with input b[1]=f[1]. Example 1: f(x)=exp(x), f[j]=1, for all j. b[1]= 1 and b[n] = 1 - sum(sum(M1(n;vec(e))*b[1]^e_1*... *b[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m)),m=2..n), n>=2. Thus, b[2]= 1- 2*b[1]^2 = -1; b[3] = 1 - 3*b[1]*b[2] -6*b[1]^3 = 1+3-6 = -2; b[4] = 1- 4*b[1]*b[3] - 6*b[2]^2 - 12*b[1]^2*b[2] - 24*b[1]^4 = 1-4*(-2)-6-12*(-1) - 24 = -9; etc. This becomes, up to signs, sequence A137852 (P. D. Hanna), viz, [1, -1, -2, -9, -24, -130, -720, -8505, -35840, -412776, -3628800, -42030450, -479001600, -7019298000, -82614884352,...]. Example 2: f(x)= 1 - ln(1-x) = 1 + sum((k-1)!*(x^k)/k!, k=1..infty), f[k]=(k-1)!. a[1]= 1 = a[2] and b[n] = (n-1)! - sum(sum(M1(n;vec(k))*b[1]^e_1*... *b[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m), m=2..n), n>=2. Thus, b[2] = 1- 2*b[1]^2 = -1; b[3] = 2 - 3*b[1]*b[2] -6*b[1]^3 = 2+3-6 = -1; b[4] = 6- 4*b[1]*b[3] - 6*b[2]^2 - 12*b[1]^2*b[2] - 24*b[1]^4 = 6-4*(-1)-6-12*(-1) - 24 = -8; etc. This becomes sequence A157164 = [1,-1,-1,-8,-16,-74,-526,-6768,-30024,-291072,-2805408,-29134896, -374664720,-5276228736,...]. ####################################### Note: The inverse problem, to find the sequence f[n] from the sequence b[n] uses the same formula. In this case it is an explicit formula, namely: f[1] = b[1], (one may add f[0] = 1) and f[n] = sum(sum(M1(n;vec(k))*b[1]^e_1*... *b[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m)), m=1..n), n>=2. Example 3: b[j]=1, j>=1, gives the sequence f[k], k>=1: A005651(k+1)= [1,3,10,47,246,1602,11481,95503, 871030,8879558,98329551,1191578522,...], the total sum over the M1 numbers for given n. ######################################## Another derivation, called recurrence II, uses the log on both sides of the initial problem and one expands with the help of multinomials M_3 (A-St Handbook p. 823, pp. 831-2 and array A036040). Here we write M3. (Paul Hanna explained this to me (Feb 28 2009 by email) for the example f(x)=exp(x). Here it is generalized for any unital f(x).) On the product side this is, after expansion of -ln(1-b[j]*(x^j)/j!) and collecting coefficients for (x^n)/n!, sum(((x^n)/n!)*A(n), n=1..infty) with A(n) := n!*sum(((b[d]/d!)^(n/d))*(d/n),d|n (all divisors d of n)). If the improper divisors d=1 and d=n are taken separately, this becomes A(n) = (n-1)!(b[1])^n + b[n]) + (n-1)!*sum(d*(b[d]/d!)^(n/d), d|n with 1=2. Note that the m=n term in the B(n,m) sum cancels the first -(n-1)!*f[1]^n term. Hence one can also use b[1]=f[1], b[n] = -(n-1)!*sum(d*(b[d]/d!)^(n/d), d|n with 1=2. vec(e)=(e_1,e_2,...,e_n) and M3(vec(n);n):=n!/product((e_j)!*j!^e_j,j=1..n). ############################################## Note (in reply to an e-mail by V. Jovoviv, Mar 10 2009, observing simplification of the recurrence in the later treated o.g.f. case for the Fibonacci example): B(n,m) is an exponential convolution triangle (see the paper by D. E. Knuth, Convolution polynomials, Mathematica J., 2 (1992) 67-78) also called number triangle of the Jabotinsky type. This means that the e.g.f. of the m-th column sequence is ((f(x)-1)^m)/m!. The e.g.f. C(x):=sum(C(n)*(x^n)/n!) for the sequence C(n) = sum(((-1)^(m-1))*(m-1)!*B(n,m), m=1..n) can now be computed (interchanging the two summations) to reproduce C(x)= ln(f(x)). This result is clear from the start because ln(f(x)) has been expanded to obtain the multinomial M_3 formula. Therefore one can also write recurrence II as b[1]=f[1], b[n] = -(n-1)!*(b[1]^n + sum((d*(b[d]/d!)^(n/d), d|n with 1=2. Example 2: f(x)= 1 - ln(1-x) = 1 + sum((k-1)!*x^k ,k=1..infty), f[k]=(k-1)!. b[1]= 1 and because M3(n;vec(e))*product((j-1)!^e[j],j=1..n) = M2(n;vec(e)):=n!/product(e[j]!,j=1..n) one has b[n] = -(n-1)!*(1 + sum(d*(b[d]/d!)^(n/d), d|n with 1=2. The array M2 is found under A036039. Because b(n,m)= |S1(n,m)|, the unsigned Stirling numbers of the first kind (tables |A008275| or with offset 0 |A048994|), the final recurrence is b[n] = -(n-1)!*(1 + sum(d*(b[d]/d!)^(n/d), d|n with 1=1. E.g., b[4] = -6*(1+2*((-1/2)^2) + 1 = -9 + 1 = -8. Using the e.g.f. of the C(n) sequence, namely ln(f(x))= ln(1 - ln(1-x)), this shows also that C(n)=A089064(n). ########################################################################################################### B) For unital ordinary generating functions (o.g.f.s), i.e., G(x) = 1 + sum(g[k]*x^k, k=1..infty) (as formal power series) one asks for the sequence a[j], j>=1, which satisfies G(x) = 1/product(1 + a[j]*x^j,j=1..infty) (also in the formal sense). If successful, this will map the sequence {g[k]},k=0,1,.., (with g[0]=1) to the sequence {a[j]},j=0,1,... (with b[0]=0). Note: Such products appear in the context of Witt rings. See also the paper "Witt Vectors and the Algebra of Necklaces" by N. Metropoulos and Gian-Carlo Rota, Adv. Maths. 50 (1983) 95-125, Theorem 1, p.114. In this paper our G(x) is called unital series associated to the (infinite dimesional) Witt vector (a[1],a[2],...). Sometimes the map {a[j]}_{j=1..infty} to {g[k]}_{j=1..infty} is called Somos transformation. One can derive the two recurrences from the above given ones by puting f[k]=k!*g[k] and b[j]=j!*a[j] everywhere. Recurrence I. With M1(n;vec(k))*(k_1)!*... *(k_n)! = n! recurrence I from part A becomes a[1]=g[1], a[n] = g[n] - sum(sum(a[1]^e_1*...*a[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m)), m=2..n), n>=2. Example 3: G(x)=1/(1-x), g[j]=1, j>=1; a[1]=1, a[n] = 1 - sum(sum(a[1]^e_1*...*a[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m)), m=2..n), n>=2. E.g., a[2] = 1 - a[1]^2 = 0, a[3] = 1 - a[1]*a[2] - a[1]^3 = 0, a[4] = 1 - a[1]*a[3] - a[2]^2 - a[1]^2*a[2] - a[1]^4 = 0 , etc. This produces a[n] = 1 if n=1, and 0 else. This corresponds to the obvious solution G(x) = 1/(1-x) = 1/(1-1*x). Example 4: G(x)=1/(1-x-x^2), g[j]=F(j+1), the Fibonacci numbers A000045(n+1). a[1]=F(2)=1, a[n] = F(n+1) - sum(sum(a[1]^e_1*...*a[n]^e_n, p=(1^e_1,...,n^e_n) from P(n,m)), m=2..n), n>=2. E.g., a[2]= 2 - a[1]^2 = 1; a[3] = 3 - a[1]*a[2] - a[1]^3 = 1 , a[4] = 5 - a[1]*a[3] - a[2]^2 - a[1]^2*a[2] - a[1]^4 = 1, etc. This produces A157162 = [1,1,1,1,2,2,4,5,8,10,18,24,40,52,88,125,210,286,492,702,1144,1638,2786,...]. ################ Note: The inverse problem, to find the sequence g[n] from the sequence a[n] uses the same formula. In this case it is an explicit formula, namely: g[1] = a[1], (one may add g[0] =1) and g[n] = a[n] + sum(sum((a[1]^e_1)*...*(a[n]^e_n), p=(1^e_1,...,n^e_n) from P(n,m)),m=2..n), n>=2, Example 5, as a test: a[j]=1, j>=1, gives the sequence g[k] = A000041(k), k>=1, with A000041 = [1,2,3,5,7,11,15,22,30,42,56,...] (number of partitions of n). Example 6: a[j]=F(j)=A0000 (Fibonacci), j>=1, gives the sequence g[k], [1, 3, 6, 15, 29, 69, 133, 296, 585, 1237, 2417, 5069, 9804, 19937, 38856] ################ Recurrence II. Using M3(n;vec(e))*product(j!^e[j], j=1..n)= (n!/m!)*M0(n;vec(e)) with M0(n;vec(e)):=m!/product(e[j]!, j=1..n) and the number of parts m=sum(e[j], j=1..n) one finds a[1]=g[1], a[n] = -(g[1]^n + sum(d*(a[d])^(n/d), d|n with 1=2. Again, the m=n term in the G0(n,m) can be written separately. Thus one may also use a[1]=g[1], a[n] = -((1 + (-1)^n)/n)*g[1]^n - sum((d/n)*(a[d])^(n/d), d|n with 1=2. Note (in reply to an e-mail by V. Jovoviv, Mar 10 2009, observing simplification of the recurrence in similar cases): G0(n,m) is an ordinary convolution triangle of the Bell type (see the paper by Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan, Leon C. Woodson, The Riordan group, Discrete Applied Mathematics, 34, p.229-239). This means that the o.g.f. of the m-th column sequence is (G(x)-1)^m. This knowledge allows the computation of the o.g.f. G0(x) of the sequence A(n):= sum(((-1)^(m-1))*(1/m)*G0(n,m), m=1..n) with the result G0(x)=ln(G(x)). This is obvious from the original expansion which led to the M0 numbers in the first place. Therefore the recurrence II can also be written as a[1]=g[1], a[n] = -(g[1]^n + sum(d*(a[d])^(n/d), d|n with 1=2. where B(n)= n*A(n) is generated by x*ln(G(x))' =x*G'(x)/G(x). The g[1]^n term can be included in the sum as the d=1 term, thus a[1]=g[1], a[n] = -(sum(d*(a[d])^(n/d), d|n with 1<=d=2. No partitions are needed here which provides a formula for the rapid calculation of a[n]. ############################################################# Example 3: G(x)=1/(1-x), g[j]=1, j>=1. Here sum(M0(n;vec(e)), vec(e)taken from every p=(1^e_1,...,n^e_n) from P(n,m)) = binomial (n-1,m-1) (cf. J. Riordan, Combinatorial Identities, p. 183, 2nd eq. line) and sum(((-1)^(m-1))*(1/m)*binomial(n-1,m-1), m=1..n) = sum(((-1)^(m-1))*binomial(n,m), m=1..n)/n = 1/n. Therefore, a[1]=1, a[n] = -sum(d*(a[d])^(n/d), d|n with 1=2. E.g., a[p]= 0 for every prime p; a[4] = -2*(a[2])^2)/4 = 0, a[6]= 0, etc. This produces b[n]=1 if n=1 and 0 else, confirming the trivial solution G(x) = 1/(1-x) = 1/(1-1*x). The B(n) sequence is generated by x*ln(1/(1-x))' = x*(-ln(1-x))'= x/(1-x), hence B(n) = 1, n>=1, (providing another proof of the binomial identities used above). Example 4: G(x)=1/(1-x-x^2), g[j]=F(j+1), the Fibonacci numbers A000045(n+1). a[1]=F(2)=1, a[n] = -(1 + (-1)^n)/n - sum((d/n)*(a[d])^(n/d), d|n with 1=2. E.g., a[2]= -1 - 0 + 2 = 1; a[4] = -1/2 -(2/4)*(a[2])^2 + 1*1*F(5)^1 -(1/2)*(2*F(2)*F(4)+1*F(3)^2) + (1/3)*3*(F(2)^2)*F(3) = -1/2 -1/2 + 5-(2*3+2^2)/2+2 = 1. The B(n) sequence is generated by x*(-ln(1-x-x^2))' = x*(1+2*x)/(1-x-x^2) which generates the Lucas numbers L(n)=A000032(n) or A000204(n), n>=1. This simplification of this recurrence has been noticed by V. Jovovic (email to WL from Mar 10 2009). a[4] = -(1 + 2*a[2]^2 - L(4)/4 = -(1+2-7)/4 =1. ###################################### e.o.f. ############################################################