2
$\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$
7
  • 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
    Commented Oct 8, 2018 at 4:02
  • $\begingroup$ I need to calculate $\binom{n}{k}_q$ in $O(n)$ time. $\endgroup$
    – piepie
    Commented Oct 8, 2018 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
    Commented Oct 8, 2018 at 5:19
  • $\begingroup$ Thanks. I got it :). yeah, I need to calculate modulo a prime, so it's ok. $\endgroup$
    – piepie
    Commented Oct 8, 2018 at 5:36
  • 1
    $\begingroup$ @flonk You have to use Modular multiplicative inverse. $\endgroup$
    – piepie
    Commented Mar 22, 2021 at 3:31

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .