On 2015-10-18 12:39, Warren D Smith wrote:

Following up on NJAS, who noted

The coefficient of x^n in G(x)^m tells you how many ways to express n as a sum (multiple orderings counted multiply, repeats allowed) of m elements of sequence S

I note:

You can also compute the number of sums with repeated elements of S disallowed, and not allowing multiple orderings of the same sum: for example with m=2 rather than using G(x)^2 use (G(x)^2-G(x^2))/2; with m=3 rather than G(x)^3 use (G(x)^3-G(x^2)*G(x)*3-G(x^3))/6 and similar tricks can be devised for any given m.

From rcs Wed Oct 14 11:50:42 1998 Return-Path: <owner-math-fun@baskerville.CS.Arizona.EDU> Received: from optima.cs.arizona.edu (optima.CS.Arizona.EDU [192.12.69.5]) by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) with ESMTP id LAA04966 for <math-fun@baskerville.cs.arizona.edu>; Wed, 14 Oct 1998 11:50:42 -0700 (MST) Received: from NEWTON.Macsyma.COM ([192.156.175.1]) by optima.cs.arizona.edu (8.9.1a/8.9.1) with SMTP id LAA24261 for <math-fun@OPTIMA.CS.ARIZONA.EDU>; Wed, 14 Oct 1998 11:50:22 -0700 (MST) Received: from SWEATHOUSE.Macsyma.COM by NEWTON.Macsyma.COM via INTERNET with SMTP id 419503; 14 Oct 1998 14:49:02-0400 Date: Wed, 14 Oct 1998 11:50-0700 From: Bill Gosper <rwg@[192.156.175.1]> Reply-To: rwg@NEWTON.Macsyma.COM Subject: integer sequences and partitions, [arcsines -> Mt. Ararat] To: math-fun@optima.CS.Arizona.EDU cc: njas@research.att.com, wilf@math.upenn.edu In-Reply-To: <19980828061701.1.RWG@[192.233.166.105]> Message-ID: <19981014185051.6.RWG@[192.233.166.105]> Yesterfortnight, I muttered Suppose h(t) has a powerseries with coefficients in {0,1}, and is thus the generating function of the characteristic function of an integer sequence. E.g., to characterize the positive squares, h(t) := (theta_3(t)-1)/2 = sum(t^n^2,n,1,inf). Then the coefficient of s^i t^j in inf ==== i i i \ (- 1) s h(t ) - > --------------- / i ==== i = 1 (d1100) %e =: f(s) is the number of ways to partition j into i distinct elements of the integer sequence. To relieve the distinctness constraint, take all signs positive. Expanding both versions at s=0 gives the generating functions for partitions into 0 members, 1 member, 2 members, ... of whatever set h characterizes (e.g., positive squares.) (c3232) taylor(1/subst(-s,s,d3226),s,0,4); /* allowing repetitions */ Time= 68 msec. 2 2 2 (h(t ) + h (t)) s (d3232)/T/ 1 + h(t) s + ------------------ 2 3 2 3 3 (2 h(t ) + 3 h(t) h(t ) + h (t)) s + ----------------------------------- 6 4 3 2 2 2 2 4 4 (6 h(t ) + 8 h(t) h(t ) + 3 h (t ) + 6 h (t) h(t ) + h (t)) s + -------------------------------------------------------------- 24 + . . . (c3226) taylor(d1100,s,0,4); /* distinct */ 2 2 2 (h (t) - h(t )) s (d3226)/T/ 1 + h(t) s + ------------------ 2 3 2 3 3 (h (t) - 3 h(t ) h(t) + 2 h(t )) s + ----------------------------------- 6 4 2 2 3 2 2 4 4 (h (t) - 6 h(t ) h (t) + 8 h(t ) h(t) + 3 h (t ) - 6 h(t )) s + -------------------------------------------------------------- 24 + . . . So, to count the ways in which n can be the square of a pythagorean hypotenuse, (c4530) subst([s = 1,h = lambda([x],sum(x^n^2,n,1,inf))], print(third(d3232))); 2 2 2 s (h(t ) + h (t)) ------------------ 2 inf inf ==== 2 ==== 2 \ 2 n \ n 2 > t + ( > t ) / / ==== ==== n = 1 n = 1 (d4530) -------------------------- 2 (c4533) taylor(d4530,t,0,50); Time= 688 msec. 2 5 8 10 13 17 18 20 25 26 29 (d4533)/T/ t + t + t + t + t + t + t + t + t + t + t 32 34 37 40 41 45 50 + t + t + t + t + t + t + 2 t + . . . I.e., 50 = 49 + 1 = 25 + 25. Or the number of ways n can be the square of the diagonal of a rectangular solid with three unequal sides, (c4537) subst([s=1,h=lambda([x],sum(x^n^2,n,1,inf))],print(fourth(d3226))); 3 3 2 3 s (2 h(t ) - 3 h(t) h(t ) + h (t)) ----------------------------------- 6 inf inf inf inf ==== 2 ==== 2 ==== 2 ==== 2 \ 3 n \ n \ 2 n \ n 3 2 > t - 3 ( > t ) > t + ( > t ) / / / / ==== ==== ==== ==== n = 1 n = 1 n = 1 n = 1 (d4537) -------------------------------------------------------- 6 (c4538) taylor(%,t,0,99); 14 21 26 29 30 35 38 41 42 45 (d4538)/T/ t + t + t + t + t + t + t + t + t + t 46 49 50 53 54 56 59 61 62 65 66 + t + t + t + t + t + t + t + t + 2 t + t + t 69 70 74 75 77 78 81 83 84 86 + 2 t + t + 2 t + t + 2 t + t + t + t + t + 2 t 89 90 91 93 94 98 + 2 t + 2 t + t + t + 2 t + 2 t + . . . I.e., 69 = 64 + 4 + 1 = 49 + 16 + 4 . (Is this in Generatingfunctionology? I couldn't find it.) Prof. Wilf points out that these are direct consequences of his eqn 3.16.4, p101. With minor variable renaming: Let R be the set of (positive) integers characterized by h, and let W be the allowable multiplicities when partitioning into members of R. (E.g., for distinct partitions, W = {0, 1}; for unlimited repetitions, W = {0, 1, 2, ...} = [0,inf).) Define p(j,i;W,R) := # partitions of n into i members of R with multiplicites in W. Then ==== /===\ ==== \ i n | | \ i i j > p(n, i; W, R) s t = | | > s t . / | | / ==== j in R ==== i, n i in W (Wilf classifies this as a (bivariate) opsgf (ordinary power series generating function), but it is clearly an IGF (insanely general formula).) The righthand Sum(s t^j) is merely 1 + s t^j for W = {0,1}, or 1/(1 - s t^j) for W = [0,inf). Now let b_j be the bits predicating membership in R, i.e., (c4540) h(t) = sum(b[j]*t^j,j,0,inf) inf ==== \ j (d4540) h(t) = > b t / j ==== j = 0 then we can rewrite inf /===\ /===\ b | | j | | j j | | Sum(s t ) = | | Sum (s t ) | | | | j in R j = 0 Then change the righthand product into exp(sum(b_j log(Sum(s t^j))), expand the log at s = 0, then interchanging sums renders the inner one to be h(t^j) (for either W), and d(1100) and its all-positive allomorph follow. [At this point I had the generalization W = {0,1,...,r}, i.e., allowing multiplicities up to r, so you could see how the signs disappeared from the gf. But after several months of continuous operation, and 2.5 weeks of no Net, I crashed my lisp machine just hours before my Net connection came back! I'll try to reconstruct the generalization when the dust settles.] ----------------- --rwg