Dear Professor Zeilberger,

This email is in response to your recent post on the arxiv on the
number of partitions of n into distinct parts.  I believe I have a
proof that:
log(f(n)) ~ (6n)^{1/3} log(n)/3.

The basic idea is as follows.  A partition into parts with distinct
multiplicities can be specified by the following data:
* A non-negative m equal to the number of distinct sizes of parts
* A set P of positive integers of size m corresponding to the sizes of parts
* A set M of positive integers of size m corresponding to the
multiplicities of the parts
* A bijection pi: P -> M.
The partition has pi(p) parts of size p for each p in P.  Thus the
size of the total partition is sum p* pi(p).

It is not hard to see that m = O(n^{1/3}) since otherwise the size
would be forced to be too big.  It is also not hard to show that there
are only 2^{O(n^{1/3})} ways of picking  M and P so that is it
possible to obtain a partition of size at most n, thus we are left
with finding the maximum possible number of pi given a single P and M.
 It should be noted that the smallest possible partition for a given m
has m+1-k parts of size k and has total size m(m+1)(m+2)/6.  Thus m <=
(6n)^{1/3}, and the number of possible pi is at most [(6n)^{1/3}]!  On
the other hand we can show that if eps >0 and m < (6n)^{1/3}(1-eps)
then for P=M={1,2,...,m}, a reasonable fraction of the m! possible pi.
 In particular if |pi(k) + k - m| < delta m for all k and some small
delta, our partition should be small enough, but will leave about
(delta m)^m possible permutations, which gives the correct asymptotic
for log(f(n)).

I was puzzled for a while about why the numerical data seemed to
suggest the asymptotic of C sqrt(n).  I can point to two reasons why
the data for n <= 508 should fit this better than my asymptotic.
1) Considering the ratio  [ n^{1/3} log(n) ] / [ n^{1/2} ], we find
that it obtains and absolute maximum near n=400.  This means that the
ratio of the real asymptotic and sqrt(n) should be fairly flat around
this neighborhood.
2) I expect that my asymptotic has a relative error on the order of
log(n)^{-0.5}.  For n=500, this is about 0.6, certainly big enough to
account for the 20% discrepancy between log(f(508)) and the predicted
value.

-Daniel Kane