A limit from an Erdos paper - MathOverflow

A limit from an Erdos paper

2011-12-02T17:37:19Z

Hi,

I need help to prove that, for $ N = \big\lfloor \frac{1}{2}n\log(n)+cn \big\rfloor $ with $c \in \mathbb R $ and $0 \leq k \leq n: $

$$ \lim_{n\rightarrow +\infty} \dbinom{n}{k} \frac{\dbinom{\binom{n - k}{2}}{N} }{\dbinom{\binom{n}{2} }{N}} = \frac{e^{-2kc}}{k!} $$

Answer by Jacques Carette for A limit from an Erdos paper

2011-12-02T18:25:29Z

First note that $\binom{m}{2} = \frac{m(m-1)}{2}$ and use that to get rid of the nested binomials. Also, the floor function will not (here) make any difference, so ignore it.

Then convert all binomials to their $\Gamma$ equivalents, and use Stirling's formulas for each term. The next step is the messiest, as you'll have a lot of arithmetic to perform on the result, which will give you the result.

This is sufficiently mechanical that, using Maple, I can quickly derive that $$ \frac{e^{-2kc}}{k!} + \frac{-\frac{1}{2}e^{-2kc}((4c+k+1)\ln{n}+2kc+4c^2+\ln^2{n}-1+2c+k)}{n (k-1)!}+O(n^{-2})$$

Of course, that second term might not be quite right, since the previously ignored floor function might here contribute, I have not checked that.

Answer by Bob for A limit from an Erdos paper

2011-12-02T20:18:38Z

Hi,

thank you for your calculation, in fact I wanted to generalize the method to obtain the following limit:

for $ N' = \lfloor n^2 log(n)+cn^2 \rfloor $ with $c \in \mathbb R $ and $0 \leq k \leq n $

$$ \lim_{n\rightarrow +\infty} \dbinom{n}{k} \frac{\dbinom{3 \binom{n-k}{3} }{N'} }{\dbinom{3 \binom{n}{3} }{N'}} $$

but I think it's a little hard without Maple, so if you could give me the value of this limit with your method it would help me a lot.

Friendly.

Answer by Brendan McKay for A limit from an Erdos paper

2011-12-02T22:49:04Z

Note that the limit is not in general correct if $k$ is a function of $n$. I'll assume you meant us to assume it is constant or very slowly growing.

You don't need a computer. Just remember this one: $$ \binom{M}{t} = \frac{M^t}{t!} \exp\biggl( -\frac{t(t-1)}{2M} + O(t^3/M^2)\biggr), $$ as $M\to\infty$. The variable $t$ can be a function of $M$ provided $t^3/M^2$ is bounded. You can prove this using Stirling's formula, but it is easier to just take the logarithm of both sides and use the Taylor expansion of the logarithm.

Apply this to the three binomials in your problem and simplify. This will also tell you how fast $k$ can increase before the limit changes.

For your second problem $t^3/M^2$ doesn't go to zero, so you need the next term inside the exponential, which is $$ -\frac{t(t-1)(2t-1)}{12M^2} $$ and the error term is then $O(t^4/M^3)$. If you don't care about precise error terms, put this together and infer that whenever $t=o(M^{3/4})$, $$ \binom{M}{t} = \frac{M^t}{t!} \exp\biggl( -\frac{t^2}{2M} -\frac{t^3}{6M^2} + o(1)\biggr). $$