I need to get approximations for partition functions in order to limit the expansion of the generating series used to work out the exact value.

The unrestricted partition function $ p(n) $ counts the number of partitions of the positive integer n, and satisfies the asymptotic formula :

$$ p(n) ∼ \frac{e^{c_0 \sqrt n}}{(4\sqrt 3)n} $$

where $$ c_0 = \pi \sqrt{\frac{2}{3}} $$

Ok no problem so far.. (can work out $ p(n) $ approximations from that).

Now, let $ p_A(n) $ denote the number of partitions of n into parts belonging to a finite set $A$, with $ gcd(A) = 1 $. For this function we are given the following (cf. Elementary Methods in Number Theory, p. 455-461) :

$$ p_A(n) = \left(\frac{1}{\prod_{a \in A}a}\right) \frac{n^{|A|-1}}{(|A|-1)!} + O\left(n^{|A|-2}\right) $$

The problem is that for a given integer n and a set of coprimes smaller than n, I always get values close to zero. I can't figure out how to get proper approximations from that. I don't know if I can safely ignore the big-O function, or what to do with it.

What did I miss ? Can the function $ p_A(n) $ defined above actually be used to get correct values or proper approximations for finding the number of partitions of $n$ into parts belonging to $A$, and if yes how ? Or if not, why ?

  • $\begingroup$ Where in the linked book can we find that expression? $\endgroup$
    – Servaes
    Commented Aug 21, 2021 at 17:40
  • 1
    $\begingroup$ It is page 456 (more generally pages 455 to 461). $\endgroup$ Commented Aug 21, 2021 at 18:07
  • 2
    $\begingroup$ Do note that this is an asymptotic result that holds for any fixed such set $A$, as $n$ increases. It seems that you are varying $A$ with $n$, i.e. your $A$ seems to depend on $n$. Then there is no reason to believe that the same asymptotic result will hold. $\endgroup$
    – Servaes
    Commented Aug 21, 2021 at 20:47
  • $\begingroup$ You're right, thank you I've completely missed that point and I didn't test increasing n using a fixed set, but still it seems I got non sense values so far.. I will give it another try tomorrow and update accordingly. $\endgroup$ Commented Aug 21, 2021 at 22:08

1 Answer 1


For the extreme case $A = \{ k \mid 1 \le k \le n \text{ with } \gcd(k,n) = 1 \}$, I don't think you'll be able to do better than the asymptotics of the unrestricted $p(n)$. Writing $p'(n)$ for these partitions into relatively prime parts, $p'(n) = p(n) - 1$ when $n$ is prime. But $p'(n)$ can also be much less than $p(n)$, e.g., $p'(12) = 6$ while $p(12) = 77$. My guess is that any useful approximations would need to include some measure of the "compositeness" of $n$. (By the way, the $p'(n)$ sequence is in the On-line Encyclopedia of Integer Sequences as A057562.) As per Servaes's comment, the cited result doesn't apply is $A$ is not fixed.

There are, though, some related cases with asymptotic results. For instance, A000837 counts partitions of $n$ into parts that are relatively prime to each other (so $3+1$, $2+1+1$, and $1+1+1+1$ are counted while $4$ and $2+2$ are not) and A000607 counts partitions into prime parts; both of these entries include asymptotic formulas.

  • $\begingroup$ Yes my issue was about approximating p'(n) using prime parts smaller than n, which can't work as A depends on n... $\endgroup$ Commented Aug 22, 2021 at 18:36
  • $\begingroup$ It's quite funny or absurd because I got A000607 early in the process and while working out its generating function, I was looking for a way to restrict the expansion of the corresponding generating series and power sequence at some point where we "know" (approximately) from the start which value (or not) to reach. So I ended up here while the formula I was looking for was just above the Gf. definition... : $$ a(n) = \frac{1}{n}\sum_{k=1}^n \operatorname{sopf}(k)*a(n-k) $$ where $ \operatorname{sopf}(n) $ is the sum of the distinct primes dividing n (A008472). $\endgroup$ Commented Aug 23, 2021 at 12:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .