$$\binom{n}{2} = \frac{n!}{2!(n-2)!}$$

Using Stirling's approximation we have:

$$\frac{\sqrt{2 \pi n}(\frac{n}{e})^n}{[\sqrt{2 \pi 2}(\frac{2}{e})^2][\sqrt{2 \pi (n-2)}(\frac{(n-2)}{e})^{(n-2)}]}$$

Removing constants and simplifying:

$$\frac{(\frac{n}{e})^n}{(\frac{(n-2)}{e})^{(n-2)}} = \frac{n^n}{e^n} \times \frac{e^{n-2}}{(n-2)^{n-2}} = \frac{n^n}{(n-2)^{(n-2)}}$$

Not sure how to proceed.

  • 10
    $\begingroup$ $$\binom{n}2=\frac{n(n-1)}2$$ $\endgroup$ Jun 22 '15 at 21:21
  • $\begingroup$ Can you show me the derivation? $\endgroup$
    – Chris
    Jun 22 '15 at 21:22
  • 10
    $\begingroup$ Stirling's approximation to compute $n(n-1)$? Are you joking? $\endgroup$ Jun 22 '15 at 21:23
  • 1
    $\begingroup$ Funnily enough you nearly had it with your (rather convoluted) method: $$\frac{n^n}{(n-2)^{n-2}} \sim \frac{n^n}{n^{n-2}} = n^2$$ $\endgroup$ Jun 22 '15 at 21:42
  • 1
    $\begingroup$ Well $$\frac{n^n}{(n-2)^{n-2}} = \frac{n^n}{n^{n-2}} \cdot \left( \frac{n}{n-2} \right)^{n-2}$$ And $\left( \frac{n}{n-2} \right)^{n-2} \to e^2$ as $n \to \infty$, which is constant. (I probably abused the $\sim$ symbol, but you catch my drift.) $\endgroup$ Jun 22 '15 at 22:00

As pointed out in the comments a simplification obviates the need for Sterling's approximation:

$$\binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} = \mathcal{O}(n^2)$$


Your Answer

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

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