# Asymptotic behavior of unique integer partitions

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.

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

## 1 Answer

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.

• (+1) for the epic reference...i was looking for something like this for a long time – tired May 31 '17 at 19:30
• @tired: This book is one of my treasures on my bookshelf. Even the reference list alone is superb. :-) – Markus Scheuer May 31 '17 at 19:45
• 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! – tired May 31 '17 at 20:55
• @tired: You're welcome. Good decision. Have fun and much success in your studies. – Markus Scheuer Jun 1 '17 at 7:31