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.

Improve this question
$\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$
    – Michael Lugo
    Commented Sep 1, 2010 at 15:14

3 Answers 3

Reset to default
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.

Improve this answer
$\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)$?

Improve this answer
$\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$.

Improve this answer
$\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$
    – Richard Borcherds
    Commented 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
    Commented 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$
    – Richard Stanley
    Commented Sep 7, 2010 at 15:19

You must log in to answer this question.

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