2
$\begingroup$

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!} $$

$\endgroup$
2
  • 3
    $\begingroup$ Jacques Carette has provided a nice suggestion. However, unless you specify what sort of help you need, I and others are going to think this question unsuitable for MathOverflow. (It may be unsuitable after you provide motivation or explain your difficulty, but you may get more sympathetic treatment. Also, if you have trouble with Jacques answer, you may find it best to ask on math.stackexchange instead.) Gerhard "Ask Me About System Design" Paseman, 2011.12.02 $\endgroup$ Dec 2, 2011 at 18:42
  • 3
    $\begingroup$ You may also want to give a more precise reference: which Erdős paper? $\endgroup$
    – j.c.
    Dec 2, 2011 at 20:24

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I think you are allowed to ignore the floor function in your computation. Let's introduce some suitable $c_n$ such that $N=\frac{1}{2}n\log(n)+c_n n$. So $c_n=c+O(1/n)$, and since Stirling's formula also holds for $\Gamma$, your computation has to be correct with $c_n$ in place of $c$. Therefore it is also correct with $c$ as it is now -maybe with $O(n^{-2}\ln n)$ in place of $O(n^{-2})$. $\endgroup$ Dec 2, 2011 at 18:40
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Mathematica can do the limit automatically. Just define the function and use the Limit[ ] command. $\endgroup$ Dec 2, 2011 at 20:26
  • $\begingroup$ Yes, but I have no symbolic computation program. So if you could give me the result I would be delighted. $\endgroup$
    – Bob
    Dec 2, 2011 at 20:34
  • $\begingroup$ @David Harris: as per Brendan McKay's answer, unless Mathematica's answer is piecewise, then it is wrong. In other words, there is a phase transition depending on the exact value of c. $\endgroup$ Dec 3, 2011 at 2:21

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.