1
$\begingroup$

Is there any way to calculate the central q-Binomial coefficient efficiently.

For example, $$\binom{2n}{n}_1=\frac{(2n)!}{(n!)^2}$$ First few values of $\binom{2n}{n}_2$ are $1,3,35,1395,200787,109221651$

First few values of $\binom{2n}{n}_3$ are $1,4,130,33880,75913222,1506472167928,267598665689058580$

These can be calculated using the function $QBinomial[2n,n,q]$. But this function works for $n\le10^4$. Is there any property of central q-Binomial coefficient that allows fast calculation for larger $n$?

$\endgroup$
  • 1
    $\begingroup$ Well, to the extent that you can "efficiently" compute $\frac{(2n)!}{n!n!}$ then you have: $$\binom{n}{k}_q = \frac{(q^n-1)(q^{n-1}-1)\cdots (q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots(q-1)}$$ $\endgroup$ – Thomas Andrews Oct 8 '18 at 4:02
  • $\begingroup$ I need to calculate $\binom{n}{k}_q$ in $O(n)$ time. $\endgroup$ – Asif Oct 8 '18 at 5:12
  • 1
    $\begingroup$ Give. That the number of digits base $q$ of this value is $O(n^2),$ you can’t even output the result in $O(n)$ time. But just evaluation the above expression is $O(n)$ operations. $\endgroup$ – Thomas Andrews Oct 8 '18 at 5:19
  • $\begingroup$ Thanks. I got it :). yeah, I need to calculate modulo a prime, so it's ok. $\endgroup$ – Asif Oct 8 '18 at 5:36
1
$\begingroup$

It seems that an asymptotics could be $$\binom{2n}{n}_q \sim C_q\, q^{n^2}$$ Computing the coefficient for $n=1000$, the values are $$\left( \begin{array}{cc} q & C_q \\ 2 & 3.462746619 \\ 3 & 1.785312342 \\ 4 & 1.452353642 \\ 5 & 1.315213556 \\ 6 & 1.241175663 \\ 7 & 1.195035240 \\ 8 & 1.163594397 \\ 9 & 1.140822757 \\ 10 & 1.123582755 \\ 11 & 1.110084028 \\ 12 & 1.099231752 \\ 13 & 1.090319360 \\ 14 & 1.082870737 \\ 15 & 1.076553491 \\ 16 & 1.071128609 \\ 17 & 1.066419860 \\ 18 & 1.062294483 \\ 19 & 1.058650573 \\ 20 & 1.055408622 \end{array} \right)$$

Considering the last term in your lists, this would give $116190496$ and $267965804863721413$.

$\endgroup$

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.