Home

Fast q-binomials in Mathematica

Wed, 06/10/2009 - 21:33 — arminstraub

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}<br /> n\\<br /> k<br /> \end{array} \right)_q = \prod_d \Phi_d (q) $$

where the product is taken over those 2 ≤ d ≤ 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) =<br /> \prod_{d = 2}^n \Phi_d (q)^{\left\lfloor n / d \right\rfloor} $$

and

$$ \left( \begin{array}{c}<br /> n\\<br /> k<br /> \end{array} \right)_q = \frac{[n]_q !}{[k]_q ! [n - k]_q !} = \prod_{d =<br /> 2}^n \Phi_d (q)^{\left\lfloor n / d \right\rfloor - \left\lfloor k / d<br /> \right\rfloor - \left\lfloor (n - k) / d \right\rfloor} . $$

Finally, note that

$$ \left\lfloor n / d \right\rfloor - \left\lfloor k / d \right\rfloor -<br /> \left\lfloor (n - k) / d \right\rfloor \in \{0, 1\}. $$

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.