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

[David Wilson]

Thank you, that is very helpful.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Olivier
> Gerard
> Sent: Saturday, December 03, 2016 3:17 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: gf's for partitions into finite number of elements
> 
> 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/
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/