7
$\begingroup$

Okay, this is one of those questions that I'm sure has a very simple answer I'm missing, and I'd appreciate any push in the right direction.

Consider a very large integer $N$. Stealing an example from Wikipedia, let $N=5$. Clearly, there are a number of ways to write this as an integer partition: $$P_5 = \{5, 4+1, 3+2, 3+1+1,2+2+1, 2+1+1+1,1+1+1+1+1\}$$ The cardinality of this set is given by the integer partition function, $|P_5| = p(5) = 7$.

It is known that there's a good asymptotic formula for $p(N)$ large $N$ (in my application, $N$ is greater than a billion, so it's very good indeed):

$$p(N)\approx \frac{1}{4N\sqrt3}e^{\pi \sqrt{\frac{2N}{3}}}$$

However, I'm not interested in finding the unrestricted partitions: I specifically want the number of partitions that do not repeat any number in the sum. In the above example, the partitions I'd be interested in are $P_5^*=\{5,4+1,3+2\}$, and $|P^*_5| = p^*(5) =3$. As another example, for $N=8$ you would have $P_8^*=\{8, 7+1,6+2,5+3,5+2+1,4+3+1\}$, $p^*(8) = 6$.

Obviously this grows quite a bit slower than $p(N)$, so here is my question: Is there a large-N asymptotic formula for $p^*(N)$, and if so, what is it?

Thank you for your replies.

$\endgroup$
  • 2
    $\begingroup$ There are some good results here , specifically (14) for an asymptotic. $\endgroup$ – Paul LeVan May 31 '17 at 5:58
3
$\begingroup$

The generating function of partitions with distinct parts is \begin{align*} \prod_{m=1}^\infty(1+z^m)&=1+z+z^2+2z^3+2z^4\\ &\qquad+\color{blue}{3}z^5+4z^6+5z^7+\color{blue}{6}z^8+8z^9+\cdots \end{align*}

The coefficients $p^\star(N)$ are asymptotically equal to \begin{align*} \color{blue}{p^\star(N) \sim \frac{3^{3/4}}{12N^{3/4}}\exp\left(\pi\sqrt{\frac{N}{3}}\right)} \end{align*}

See Figure I.9 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.

$\endgroup$
  • $\begingroup$ (+1) for the epic reference...i was looking for something like this for a long time $\endgroup$ – tired May 31 '17 at 19:30
  • 1
    $\begingroup$ @tired: This book is one of my treasures on my bookshelf. Even the reference list alone is superb. :-) $\endgroup$ – Markus Scheuer May 31 '17 at 19:45
  • $\begingroup$ my goal for the next months (my rare spare time makes this long time scale necessary), to understand the asymptotics of $p(n)$ and related functions, now becomes very realistic since i already have a strong background in saddle point calculations. Thanks again! $\endgroup$ – tired May 31 '17 at 20:55
  • $\begingroup$ @tired: You're welcome. Good decision. Have fun and much success in your studies. $\endgroup$ – Markus Scheuer Jun 1 '17 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.