2
$\begingroup$

Define $N_c=[\dfrac{1}{2}n\log n+cn]$ where $[.]$ denotes the greatest integer function, and $c$ is any arbitrary fixed real constant. Also, let $M={n\choose 2}$.

Then prove, for large $n$, the following inequalities:

$$\large{n\choose s}\dfrac{{{M - s(n-s)}\choose N_c}}{M\choose N_c}\leq \dfrac{e^{(3-2c)s}}{s!}\space\space\space\space\text{for } s\leq\dfrac{n}{2}$$

and $$\large{n\choose s}\dfrac{{{M - s(n-s)}\choose N_c}}{M\choose N_c}\leq \dfrac{e^{(3-2c)(n-s)}}{(n-s)!}\space\space\space\space\text{for } s\geq\dfrac{n}{2}$$

Here, $s$ is a positive integer such that $s<n-\dfrac{2N_c}{n}$.

I admit, these inequalities are a bit strange. But, I am convinced that these are simply estimates. The paper I am referring to, simply says, "by some elementary estimations, we get...", but do not mention how they get these.

I think Stirling's formula has been used although I could not really get these. Any help is appreciated.

EDIT: I "believe" Stirling's Approximation has been used, repeatedly, along with some other crude estimates. I am particularly having some problem figuring out how those estimates have been used.

I observe that for large $n$, by applying Stirling's Approximation, $${n\choose s}\sim \dfrac{e^{-s}n^{n+1/2}}{(n-s)^{n-s+1/2}s!}---(1)$$

$${{M-s(n-s)}\choose N_c}\sim \dfrac{e^{-N_c}{(M-s(n-s))}^{M-s(n-s)+1/2}}{{(M-s(n-s)-N_c)}^{M-s(n-s)-N_c+1/2}N_c!}---(2)$$

$${M\choose N_c}\sim \dfrac{e^{-N_c}M^{M+1/2}}{(M-N_c)^{M-N_c+1/2}}---(3)$$

Then, $(1)\times (2)/(3)$ is something, whose bound I want to make equal to the bounds given.

But things are getting too complicated by now. Please remember that $M={n\choose 2}$.

$\endgroup$
  • $\begingroup$ I deleted the link to the paper because it is really of no connection to solving this particular problem. The writer of that paper simply uses these estimates but does not mention how they are obtained. I would like these two inequalities to be solved only. $\endgroup$ – Landon Carter Dec 22 '15 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.