2

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$?

piepie
  • 547
  • 1
    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)}$$ – Thomas Andrews Oct 08 '18 at 04:02
  • I need to calculate $\binom{n}{k}_q$ in $O(n)$ time. – piepie Oct 08 '18 at 05:12
  • 1
    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. – Thomas Andrews Oct 08 '18 at 05:19
  • Thanks. I got it :). yeah, I need to calculate modulo a prime, so it's ok. – piepie Oct 08 '18 at 05:36
  • @piepie Did You manage to compute it modulo a prime using the above formula? To me it seems one would have to get rid of the denominator, but I don't see an obvious pattern, how the "smaller" factors in the denominator cancel out against those of the nominator. – flonk Mar 20 '21 at 15:56
  • 1
    @flonk You have to use Modular multiplicative inverse. – piepie Mar 22 '21 at 03:31
  • @piepie I totally forgot about this concept, thanks for the hint! – flonk Mar 22 '21 at 19:46

1 Answers1

1

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$.

Claude Leibovici
  • 260,315