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

[Olivier Gerard]

Dear David,

The coefficients for your formulas correspond to multinomial coefficients,
A036039 (reversed), which decompose permutations according to the
partitions of n. You will have A000041(n) distinct coefficients.

This will allow you to generalise your formula to any order.

This, combined with Inclusion/Extension seems to be the background
of what you found out, since the coefficient of x^k in the resulting
function
is composed of every way of reaching the k-th degree from multiplication
between f(x) and its powers.

For instance, at order 4, the correspondance between  partitions
and algebraic terms will be

f(x)^4 ...  1111
f(x^2)f(x)^2 ...  211
f(x^2)^2 ... 22
f(x^3)f(x) ... 31
f(x^4)) ... 4



Olivier


On Sat, 3 Dec 2016 at 06:56 David Wilson <davidwwilson at comcast.net> wrote:

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.


--
Seqfan Mailing list - http://list.seqfan.eu/