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<d<n (proper divisors)).

The other side is ln(f(x)) which after expansion needs terms like (sum(f[n]*(x^n)/n!, n=1..infty))^m
(exponential also known as binomial convolutions) which are rewritten with the multinomial formula involving 
the M_3 numbers for any partition of n.

(sum(f[n]*(x^n)/n!, n=1..infty))^m = m!*sum(((x^n)/n!)*B(n,m), n=m..infty) with 

B(n,m) := sum(M3(n;vec(e))*(f[1]^e_1)*(f[2]^e_2)*...*(f[n]^e_n), p=(1^e_1,...,n^e_n) from P(n,m)). 
P(n,m) is the set of partitions of n with m parts written in the exponent version explained above in 
recurrence I.

Now the two summations are (formally) interchanged: instead of m=1..infty and n=m..infty one uses 
n=1..infty and m=1..n to obtain sum(C(n)*(x^n)/n!,n=1..infty) with 
C(n):= sum(((-1)^(m-1))*(m-1)!*B(n,m), m=1..n). 

Comparing coefficients of (x^n)/n!, i.e., puting A(n) = C(n), produces the following 
recurrence II:

b[1]=f[1], 
b[n] = -(n-1)!*(f[1]^n + sum((d*(b[d]/d!)^(n/d), d|n with 1<d<n)) + sum(((-1)^(m-1))*(m-1)!*B(n,m), m=1..n), 
with B(n,m) = sum(M3(n;vec(e))*(f[1]^e_1)*(f[2]^e_2)*...*(f[n]^e_n), p=(1^e_1,...,n^e_n) from P(n,m)), n>=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<d<n) + sum(((-1)^(m-1))*(m-1)!*B(n,m), m=1..n-1), 
with B(n,m) = sum(M3(n;vec(e))*(f[1]^e_1)*(f[2]^e_2)*...*(f[n]^e_n), p=(1^e_1,...,n^e_n) from P(n,m)), n>=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<d<n)) + C(n),

with the sequence C(n) generated exponentially by ln(f(x)) (or (n+1)*C(n+1) is exponentially generated by 
(ln(f(x)))' = f'(x)/f(x)). One could include the first b[1]^n term in the sum for d=1.
No partitions are needed here, providing a formula for the rapid calculation of b[n].

##############################################

Example 1:  f(x)=exp(x), f[j]=1, for all j. 
b[1]= 1 and B(n,m)= sum(M3(n;vec(e)), vec(e)=(e_1,...,e_n) taken from every p=(1^e_1,...,n^e_n) from P(n,m)) 
= S2(n,m), the Stirling numbers of the second kind (A008277). Because  sum(((-1)^(m-1))*(m-1)!*S2(n,m),
m=1..n) = 0 (a comparison of this recurrence II with recurrence I could serve as an alternative proof for 
this identity) one finds    

b[n] = -(n-1)!*(1 + sum((d*(b[d]/d!)^(n/d), d|n with 1<d<n)).

This recurrence leads to A137852 (P. D. Hanna) but with different signs. The example 1 for the recurrence I 
above.

E.g., b[p] = -(p-1)! for primes. b[4] = -6*(1+2*(-1/2)^2 ) = -9. 

Using the e.g.f. of the C(n) sequence ln(f(x)) = x shows also that C(n) = 0 for n>=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<d<n)) + sum(((-1)^(m-1))*(m-1)!*b(n,m), m=1..n), 
with b(n,m) = sum(M2(n,vec(e)),vec(e)=(e_1,...,e_n) taken from every p=(1^e_1,...,n^e_n) from P(n,m)), n>=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<d<n)) + A089064(n),

with A089064(n)= sum(((-1)^(m-1))*|S1(n,m)|, m=1..n) = [1,0,1,1,8,26,194,1142,9736,...], n>=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<d<n))/n + sum(((-1)^(m-1))*(1/m)*G0(n,m), m=1..n), 
with G0(n,m):= sum(M0(n;vec(e))*(g[1]^e_1)*(g[2]^e_2)*...*(g[n]^e_n), p=(1^e_1,...,n^e_n) from P(n,m)), n>=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<d<n) + sum(((-1)^(m-1))*(1/m)*G0(n,m), m=1..n-1), 
with G0(n,m):= sum(M0(n;vec(e))*(g[1]^e_1)*(g[2]^e_2)*...*(g[n]^e_n), p=(1^e_1,...,n^e_n) from P(n,m)), n>=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<d<n))/n + B(n)/n, n>=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<n) - B(n))/n, n>=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<d<n)/n, n>=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<d<n) + sum(((-1)^(m-1))*(1/m)*G0F(n,m), m=1..n-1), with
G0F(n,m):= sum(M0(n;vec(e))*(F(2)^e_1)*(F(3)^e_2)*...*(F(n+1)^e_n), p=(1^e_1,...,n^e_n) from P(n,m)), n>=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. ############################################################