Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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.) –  Michael Lugo Sep 1 '10 at 15:14

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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)$?

share|improve this answer

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$.

share|improve this answer
    
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. –  Richard Borcherds Sep 2 '10 at 4:23
    
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). –  QHLIU Sep 4 '10 at 8:20
    
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. –  Richard Stanley Sep 7 '10 at 15:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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