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 |