A147542 W. Lang, Mar 12 2009 (update Mar 31 2009) Series <-> Product Transformation of Sequences. 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 a[j], j>=1, which satisfies f(x) = product(1 + a[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 {a[j]},j=0,1,..., (with a[0]=0). W. L. was led to the following study by A137852 where the problem f(x)=exp(x) has been treated. The author likes to thank P. D. Hanna for an explanation of the recurrence involving divisors given there. A paper by Gottfried Helms also dealt with this subject: "A dream of a (number-)sequence ...", Feb 2009. Recurrence I: A direct comparison of the coefficients of x^n leads to: x^0: 1 = 1 , x^1: a[1] = f[1], x^2: a[2] = f[2] and for x^n, for n>=3, f[n] = sum(sum(M1(n;vec(k))*a[k_1]*... *a[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)),m=1..maxm(n)), where FP(n,m) are the partitions of n with m parts but only distinct parts appear. Such a partition of n is written as p=vec(k) with sum(k_j, j=1..m)=n with all k_j>0 and pairwise different. E.g., FP(5,2) is a set of two elements, the partitions (1,4) and (2,3). F(5,3) is empty, as is F(5,4) as well as F(5,5). Note added (Mar 12 2009): Partitions with distinct parts appear in L. Comtet, Advanced Combinatorics, on p.99 and Q(n,m)=|F(n,m)| = A008289(n,m). In general, the maximal m (number of parts) for such partitions of n is the index k of the largest triangular number T_k=k*(k+1)/2 which is smaller than or equal to n. This boils down to maxm(n) = floor((sqrt(1+8*n)-1)/2) = A003056(n). E.g., n=5 is in the range 2=T_2 and 6=T_6, hence maxm(5)=2. The author(WL) calls these partitions `fermionic' because the parts 1 to n are either absent (not occupied) or once occupied, like in physical Fermi systems the energy levels are empty or once occupied (Pauli principle). That the multinomial numbers M1(n;vec(k))= n!/product((k_m)!, j=1..m) appear is clear. These numbers are found as M_1 in Abramowitz-Stegun (A-St), p.831-2 for the partitions for n=1..10. They also appear as A036038. This f[n] eq. is now rewritten as a recurrence for a[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 FP(1,1)) with M1 number 1. Therefore the recurrence I is: a[n] = f[n] - sum(sum(M1(n;vec(k))*a[k_1]*...*a[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)), m=2..maxm(n)), n>=3, with inputs a[1]=f[1] and a[2]=f[2]. Example 1: f(x)=exp(x), f[j]=1, for all j. a[1]= 1 = a[2] and a[n] = 1 - sum(sum(M1(n;vec(k))*a[k_1]*...*a[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)),m=2..maxm(n)), n>=3. Thus, a[3] = 1 - 3*a[1]*a[2] = 1-3 = -2; a[4] = 1- 4*a[1]*a[3] = 1-4(-2) = 9; etc. This becomes sequence A137852 (P. D. Hanna) (see the WL comment there). 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 a[n] = (n-1)! - sum(sum(M1(n;vec(k))*a[k_1]*...*a[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)),m=2..maxm(n)), n>=3. Thus, a[3]= 2 - 3*a[1]*a[2] = -1; a[4] = 6- 4*a[1]*a[3] = 6 - 4(-1) = 10; etc. This becomes sequence A157159 = [1,1,-1,10,-16,126,-526,10312,-30024,453840,-2805408,45779328,-374664720, 7932770496,...]. #################### Note added (Mar 12 2009): The inverse problem, to find the sequence f[n] from the sequence a[n] uses the same formula. In this case it is an explicit formula, namely: f[1] = a[1], f[2] = a[2] (one may add f[0] =1) and f[n] = a[n] + sum(sum(M1(n;vec(k))*a[k_1]*...*a[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)), m=2..maxm(n)), n>=3. Example 3: a[j]=1, j>=1, gives the sequence f[k], k>=1: A007837 = [1, 1, 4, 5, 16, 82, 169, 541, 2272, 17966, ... ] ######################################## Another recurrence II derivation 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, OEIS 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+a[j]*(x^j)/j!) and collecting coefficients for (x^n)/n!, sum(((x^n)/n!)*A(n), n=1..infty) with A(n) := -sum((-a[d]/d!)^(n/d)*n!*(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)!(-a[1])^n - (-a[n]) - sum((-a[d]/d!)^(n/d)*n!*(d/n), d|n with 1=0 (if an exponent is zero, the part is not written) and sum(e_j,j=1..n)=m, sum(j*e_j,j=1..n)=n. vec(e):=(e_1,e_2,...,e_n) and M3(n;vec(e)):=n!/product((e_j)!*j!^e_j,j=1..n). 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: a[1]=f[1], a[n] = (n-1)!*(((-1)^n)*f[1]^n + sum(d*(-a[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)!*((-1)^n)*f[1]^n term. Hence one can also use a[1]=f[1], a[n] = (n-1)!*sum(d*(-a[d]/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 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 M3 formula. Therefore one can also write recurrence II as a[1]=f[1], a[n] = (n-1)!*(((-1)^n)*f[1]^n + sum((d*(-a[d]/d!)^(n/d), d|n with 1=2. 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 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 a[n] = (n-1)!*((-1)^n + sum(d*(-a[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 a[n] = (n-1)!*((-1)^n + sum(d*(-a[d]/d!)^(n/d), d|n with 1=1. E.g., a[4] = 6*(1+2*((-1/2)^2)) + 1 = 9 + 1 = 10. Using the e.g.f. for the C(n) sequence ln(f(x))= ln(1 - ln(1-x)) 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 b[j], j>=1, which satisfies G(x) = product(1 + b[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 {b[j]},j=0,1,... (with b[0]=0). Note added Mar 12 2009: See L. Comtet, Advanced Combinatorics, p.120, Exercise 16. One can derive the two recurrences from the above given ones by puting f[k]=k!*g[k] and a[j]=j!*b[j] everywhere. Recurrence I. With M1(n;vec(k))*(k_1)!*... *(k_n)! = n! recurrence I from part A becomes b[1]=g[1], b[2]=g[2], b[n] = g[n] - sum(sum(b[k_1]*...*b[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)), m=2..maxm(n)), n>=3, with maxm(n)=floor((sqrt(1+8*n)-1)/2) = A003056(n) = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4,...], and the 'fermionic' partitions of n with m distinct parts, FP(n,m) (see part A above). Example 4: G(x)=1/(1-x), g[j]=1, j>=1; b[1]=1, b[2]= 1, b[n] = 1 - sum(sum(b[k_1]*...*b[k_n], vec(k)=(k_1,k_2,...,k_n) from FP(n,m)), m=2..maxm(n)), n>=3. E.g., b[3] = 1 - b[1]*b[2] = 0, b[4] = 1 - b[1]*b[3] = 1, b[5] = 1 - (b[1]*b[4] + b[2]*b[3]) = 0, etc. This produces b[n] = 1 if n=2^k, k>=0, and 0 else. Thus one finds (in the formal sense) 1/(1-x) = product(1 + x^{2^j},j=0..infty). The coefficient of x^n is found by the reverse binary representation of n: if a factor in product(1+x^j, j=1..infty) is marked as 1 if it is present and 0 if it is absent, one obtains a binary sequence, like [1,1,0,1] for n=5 if one starts on the left with the j=1 factor. This is just the reversed binary representation of n. So the sequence b[n] is A036987(n-1), the characteristic sequence for the powers of 2. Example 5: G(x)=1/(1-x-x^2), g[j]=F(j+1), the Fibonacci numbers A000045(n+1). b[1]=F(2)=1, b[2]=F(3)=2, b[n] = F(n+1) - sum(sum(b[k_1]*...*b[k_n], vec(k)=(k_1,k_2,...,k_n) from FP(n,m)), m=2..maxm(n)), n>=3, E.g., b[3] = 3 - b[1]*b[2] = 1, b[4] = 5 - b[1]*b[3] = 4, b[5] = 8 - (b[1]*b[4] + b[2]*b[3]) = 2, etc. This produces [1, 2, 1, 4, 2, 1, 4, 18, 8, 8, 18, 17, 40, 50, 88, 396,... ] which is, up to the first term identical with A147542 (observation by V. Jovovic, Mar 08 2009). ################ Note added Mar 12 2009: The inverse problem, to find the sequence g[n] from the sequence b[n] uses the same formula. In this case it is an explicit formula, namely: g[1] = b[1], g[2] = b[2] (one may add g[0] =1) and g[n] = b[n] + sum(sum(b[k_1]*... *b[k_m], vec(k)=(k_1,k_2,...,k_m) from FP(n,m)), m=2..maxm(n)), n>=3, Example 6: b[j]=1, j>=1, gives the sequence g[k], k>=1: A000009 = [1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27,...], the number of partitions of n with distinct parts. Example 7: b[j]=F(j)=A000045(n) (Fibonacci), j>=1, gives the sequence g[k], k>=1: [1, 1, 3, 5, 10, 18, 35, 63, 123, 220, 411, 750, 1387, 2498, 4649,...] ################ 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 b[1]=g[1], b[n] = (((-1)^n)*g[1]^n + sum(d*(-b[d])^(n/d), d|n with 1=2. P(n,m) is the set of partitions p of n with m parts written in the exponent version explained above in part A, recurrence II. The number array M0 for partitions is found under A048996. Again, the m=n term in the G0(n,m) sum cancels the first term. Thus one may also use b[1]=g[1], b[n] = sum((d/n)*(-b[d])^(n/d), d|n with 1=2. Note on Witt vectors (see S. Lang, Algebra, 3rd ed., p.330, ex. 46): sum(d*x[d]^(n/d) , d|n) is also called x^(n), the n-th ghost component of the (infinite dimensional) ghost vector (x^(1),x^(2),...) of the Witt vector (x[1],x[2],...). 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): 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 b[1]=g[1], b[n] = (((-1)^n)*g[1]^n + sum(d*(-b[d])^(n/d), d|n with 1=2. where A(n) is generated by the o.g.f. ln(G(x)). Sometimes it is easier to use A(n)=B(n)/n with B(n) generated by x*(ln(G(x)))' = x*G'(x)/G(x), and reabsorbing the d=1 term one can also write b[1]=g[1], b[n] = (sum(d*(-b[d])^(n/d), d|n with 1<=d=2. ############################################################# Example 4: G(x)=1/(1-x), g[j]=1, j>=1. Here sum(M0(n;vec(e)),vec(e) exponents for p 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, b[1]=1, b[n] = ((-1)^n +1 + sum(d*(-b[d])^(n/d), d|n with 1=2. E.g., b[2]= 2/2 =1, b[4] = (2 + 2*(-b[2])^2)/4 = (2+2)/4 =1, b[5]= 0, etc. One can prove that b[n]=1 if n=2^k, k>=0, and 0 else, satisfies this recurrence using the finite geometric series. The A(n) sequence is generated by ln(1/(1-x)) = -ln(1-x), hence A(n) = 1/n (providing another proof of the binomial identities used above). Example 5: G(x)=1/(1-x-x^2), g[j]=F(j+1), the Fibonacci numbers A000045(n+1). b[1]=F(2)=1, b[n] = sum((d/n)*(-b[d])^(n/d), d|n with 1=2. E.g., b[4] = (2/4)*(-b[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) = 2+5-(2*3+2^2)/2+ 2 = 4. The A(n) sequence is generated by -ln(1-x-x^2). This means that B(n)=n*A(n) is generated by x*(-ln(1-x-x^2 )'= x*(1+2*x)/(1-x-x^2) which generates the Lucas numbers A000032(n) or A000204(n), n>=1. This simplification of this recurrence has been noted by V. Jovovic (email to WL from Mar 10 2009). ###################################### e.o.f. ############################################################