2
$\begingroup$

Let $p(n,m)$ be the number of partitions of an integer $n$ into integers $\le m$, we have a well-known asymptotic expression:

For a fixed $m$ and $n\to\infty$, $$p(n,m)=\frac{n^{m-1}}{m!(m-1)!} (1+O(1/n)) $$

My question is: why the error $O(1/n)$ is independent of $m$? Or how can it be extended for $m$ growing slowly with $n$? Please help me to find the answer or the references. Thanks.

$\endgroup$
1
  • $\begingroup$ I think there's a derivation of this in George Andrews' book Theory of Partitions. At the very least you might check there. (This is a comment instead of an answer because I don't actually have the book in front of me to check.) $\endgroup$ Sep 1, 2010 at 15:14

3 Answers 3

4
$\begingroup$

I'm not entirely sure of what you are asking, but note that Erdos and Lehner proved here that $$p(n,m)\sim \frac{n^{m-1}}{m!(m-1)!}$$ holds for $m=o(n^{1/3})$. In generality for any finite set $A$, with $|A|=m$ and $p(n,A)$ denoting the number of partitions of $n$ with parts from $A$, one has $$p(n,A)=\frac{1}{\prod_{a\in A}a}\frac{n^{m-1}}{(m-1)!}+O(n^{m-2}).$$

Such estimations can be deduced from the generating function of $p$ by using methods that are described in many books, for example "Analytic Combinatorics" by Flajolet and Sedgewick.

$\endgroup$
2
$\begingroup$

Thank Robin Chapman very much for editing.

There is a nice asymptotic expression for partition $q(n,M)$ that denotes the number of partitions of $n$ with $M$ parts all distinct: As $n\to\infty$,

$$ q(n,M)\approx \frac{(n-1)!}{M!(M-1)!(n-M)!}\left( 1+O\left( \frac{M^{3}}{n} \right) \right)$$

Isn't there no similar asymptotic expression for partition $p(n,m)$?

$\endgroup$
2
$\begingroup$

G. Szekeres, Quart. J. Math. (Oxford) 4(2) (1953), 96-111, obtains an asymptotic formula for $p(n,m)$ valid uniformly for all $n$ and $m$.

$\endgroup$
3
  • 1
    $\begingroup$ His formula only seems to be valid for n at most a constant times m<sup>2</sup>. It also involves the solution of a quite nasty looking implicit equation, so I'm not sure how useful it is. $\endgroup$ Sep 2, 2010 at 4:23
  • 1
    $\begingroup$ Please be noted that in G. Szekeres' two papers in 1951 and 1953, the asymptotic formulae for $p(n,m)$ valid only under strong condition that $m$ is related to $n^2$. In physics, no asymptotic formula not useful unless $m \alpha n$ ($\alpha >0$ and as $m$ is large). $\endgroup$
    – QHLIU
    Sep 4, 2010 at 8:20
  • $\begingroup$ I am not an expert in this area, but see combinatorics.org/Volume_4/Abstracts/v4i2r06ab.html. Here Szekeres' asymptotic formula is given that is valid in the range $k\geq n^{1/6}$, and is valid uniformly in the entire range $k\geq 1$ by adding $1/k$ to the big-oh term. See also the article by Romik in Europ. J. Combinatorics 26 (2005), 1-17. As for whether the formula is useful, Szekeres uses it to prove that for $n$ sufficiently large, the sequence $p(n,1), p(n,2),\dots, p(n,n)$ is unimodal, the only known proof of this result. $\endgroup$ Sep 7, 2010 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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