How to simplify or approximate n^2 choose n

Question

I'm analyzing the runtime of an algorithm I wrote. I determined that there are

${{\frac{n(n-1)}{2}} \choose n}$ $\approx$ ${n^2 \choose n}$ = $\frac{n^2!}{n!(n^2-n)!}$ operations in the algorithm.

However I do not know how to simplify this further. I also could be completely off, as I do not have a math major.

Can someone help with this analysis?

Answer 1

You should use Stirling's approximation $k!\approx \frac {k^k}{e^k}\sqrt{2\pi k}$

Answer 2

Here is a routine derived from Wikipedia's article on Binomial Coefficient to calculate the exact value. This works pretty well, uses only exact integer arithmetic in Python, and is time complexity O(n). Remember that in Python, range(n) produces a list from 0 through n – 1.

def n_squared_choose_n(n):
    if n < 0:
        return 0
    nsqr = n * n
    c = 1
    for i in range(n):
        c = c * (nsqr - i) / (i + 1)
    return c

This is based on the "simplification"

$${n^2 \choose n}=\frac{n^2}{1}\cdot\frac{n^2-1}{2}\cdot\frac{n^2-2}{3}\cdot\cdots\frac{n^2-n+1}{n}$$

which may well be good enough for your purposes.

Answer 3

I would suggest that you do not make the approximation $$A_n=\binom{\frac{n(n-1) }{2} }{n}=\frac{\left(\frac{n(n-1) }{2} \right)! }{n! \,\left(\frac{n(n-3) }{2} \right)! }$$ Now, take logarithms and, as Ross Millikan suggested, use Stirling approximation $$\log(p!)=p (\log (p)-1)+\frac{1}{2} \left(\log (2 \pi )+\log \left({p}\right)\right)+\frac{1}{12 p}+O\left(\frac{1}{p^3}\right)$$ This would give $$\log(A_n)=n \left(\log \left({n}\right)+1-\log (2)\right)-\frac{1}{2} \left(\log \left({n}\right)+4+\log (2 \pi )\right)-\frac{5}{4 n}-\frac{4}{3 n^2}+O\left(\frac{1}{n^3}\right)$$ which is quite accurate as soon as $n >3$ as shown below $$\left( \begin{array}{ccc} n & \text{exact} & \text{approximation} \\ 4 & 2.70805 & 2.76467 \\ 5 & 5.52943 & 5.55446 \\ 6 & 8.51819 & 8.53149 \\ 7 & 11.6638 & 11.6717 \\ 8 & 14.9495 & 14.9546 \\ 9 & 18.3603 & 18.3638 \\ 10 & 21.8833 & 21.8858 \\ 11 & 25.5079 & 25.5097 \\ 12 & 29.2249 & 29.2263 \\ 13 & 33.0269 & 33.0280 \\ 14 & 36.9073 & 36.9082 \\ 15 & 40.8606 & 40.8613 \end{array} \right)$$