arminstraub.com

Fast q-binomials in Mathematica

Recently, I have been doing experiments involving q-binomial coefficients in Mathematica. Starting with version 7, Mathematica is prepared for some q-business; in particular, there exists a function named QBinomial giving the q-analog of Binomial. However, this implementation turned out to not be fast enough for my needs. Here is an alternative approach which is not only way faster but provides a full factorization.

qn[n_, q_] := 
  Product[If[Mod[n, d] == 0, Cyclotomic[d, q], 1], {d, 2, n}];
qfactorial[n_, q_] := 
  Product[Cyclotomic[d, q]^Floor[n/d], {d, 2, n}];
qbinomial[n_, k_, q_] := 
  If[k > n, 0, 
   Product[If[Floor[n/d] == Floor[k/d] + Floor[(n - k)/d], 1, 
     Cyclotomic[d, q]], {d, 2, n}]];

The above code is based on the following well-known observations. Let \(\Phi_n\) be the \(n\)-th cyclotomic polynomial. Then $$ \left( \begin{array}{c} n\\ k \end{array} \right)_q = \prod_d \Phi_d (q) $$ where the product is taken over those \(2 \leqslant d \leqslant n\) for which \(\left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor - \left\lfloor (n - k) / d \right\rfloor = 1\). This follows from \([n]_q = \prod_{d|n, d > 1} \Phi_d (q) \), $$ [n]_q ! = \prod_{m = 1}^n \prod_{d|m, d > 1} \Phi_d (q) = \prod_{d = 2}^n \Phi_d (q)^{\left\lfloor n / d \right\rfloor} $$ and $$ \left( \begin{array}{c} n\\ k \end{array} \right)_q = \frac{[n]_q !}{[k]_q ! [n - k]_q !} = \prod_{d = 2}^n \Phi_d (q)^{\left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor - \left\lfloor (n - k) / d \right\rfloor} . $$ Finally, note that $$ \left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor - \left\lfloor (n - k) / d \right\rfloor \in \{0, 1\}. $$

Last change: 2009/06/10
2726 reads