[seqfan] gf's for partitions into finite number of elements

[David Wilson]

Let S be a subset of N = {0, 1, 2, ...}

Let f be the generating function of the indicator (characteristic?
membership?) function of S, that is,

f(x) = SUM(n in S; x^n).

I have found a method to obtain generating functions for the number of
partitions of n into k elements of S.  Using this method, I have been able
to work out:

g.f. of partitions of n into 1 element of S = f(x).
g.f. of partitions of n into 2 elements of S = (f(x)^2 + f(x^2))/2.
g.f. of partitions of n into 3 elements of S = (f(x)^3 + 3f(x^2)f(x) +
2f(x^3))/6.
g.f. of partitions of n into 4 elements of S = (f(x)^4 + 6f(x^2)f(x)^2 +
3f(x^2)^2 + 8f(x^3)f(x) + 6f(x^4))/24.

as well as

g.f. of partitions of n into 1 distinct element of S = f(x).
g.f. of partitions of n into 2 distinct elements of S = (f(x)^2 - f(x^2))/2.
g.f. of partitions of n into 3 distinct elements of S = (f(x)^3 -
3f(x^2)f(x) + 2f(x^3))/6.
g.f. of partitions of n into 4 distinct elements of S = (f(x)^4 -
6f(x^2)f(x)^2 + 3f(x^2)^2 + 8f(x^3)f(x) - 6f(x^4))/24.

These could be used to prove g.f.s for various partition sequences.
For example, if f is the generating function of A010051 (the indicator
function of the primes), then the equations above give g.f.s for various
partitions sequences into primes, e.g:

A010051 = partitions into 1 prime.
A061348 = partitions into 2 primes.
A068307 = partitions into 3 primes.
A259194 = partitions into 4 primes.

A010051 = partitions into 1 distinct prime.
A117129 = partitions into 2 distinct primes.
A125688 = partitions into 3 distinct primes.
A219198 = partitions into 4 distinct primes.

I wrote a program to compute each of the above sequences via the generating
functions, employing the dumb O(n^2) convolution, and it was still much
faster than counting partitions.

The g.f. for partitions into k elements or into k distinct elements will
have A000041(n) terms in the numerator, each term corresponding to a
partition of k.  For example, in the g.f. for  partitions into 4 elements:

(f(x)^4 - 6f(x^2)f(x)^2 + 3f(x^2)^2 + 8f(x^3)f(x) - 6f(x^4))/24.

the A000041(4) = 5 terms in the numerator correspond rather obviously to the
partitions {1,1,1,1}, {2,1,1}, {2,2}, {3,1} and {4}, and the denominator is
obviously 4! = 24.

Unfortunately, I arrived at these results by a manual counting method for
which I could not obtain a formula. With some work, I could, for example,
determine the g.f.s for partitions into 5 or 6 elements, but I could not
give a general formula or algorithm for producing these g.f.s. 

I'm going to hope that this is all well-known stuff, in which case I can
drop it.  If not, I am willing to explain my methods to someone who might be
interested in finding a general formula or algorithm.