9
$\begingroup$

We all know that $\sum_{i=0}^{n}{n \choose i}=2^{n}$. Is there a similar result regarding the q-binomial coefficients? (a.k.a Gaussian binomial coefficients) - $\sum_{i=0}^{n}{n \choose i}_{q}=?$

$\endgroup$
  • 1
    $\begingroup$ I think that you need to define your normalizations before stating the question. What is your definition of $[n]_q?$ $\endgroup$ – Scott Carter Mar 1 '12 at 7:54
9
$\begingroup$

The identity $\prod_{i=0}^{n-1} (1+xq^i) = \sum_{k=0}^n x^k q^{{k\choose 2}}{n\choose k}_q$ is the $q$-binomial theorem. A combinatorial proof based on integer partitions is mentioned on page 68 of Enumerative Combinatorics, vol. 1, 2nd ed. There is also given a combinatorial proof based on finite fields. For the online version at http://math.mit.edu/~rstan/ec/ec1.pdf, see pages 74-75.

$\endgroup$
  • $\begingroup$ Is it the answer? $\endgroup$ – Alireza Abdollahi May 7 '16 at 10:52
5
$\begingroup$

There are many possibilities, e.g. $\sum_{i=0}^{n}q^i{n \choose i}_{q^2}=(1+q)(1+q^2)...(1+q^n)$

or

$\sum_{i=0}^{n}q^{i(i+1)/2}{n \choose i}_{q }=(1+q)(1+q^2)...(1+q^n).$

$\endgroup$
  • $\begingroup$ That's interesting. Do you know a bijective proof of these identities, based on the fact that the Gaussian binomial coefficient is the number of subspaces of dimension $i$ in $(\mathbb{Z}/q)^n$? $\endgroup$ – Neil Strickland Mar 1 '12 at 10:38
  • $\begingroup$ I know no direct bijective proofs of this sort. The second identity can be deduced from a polynomial identity which has a bijective proof in the setting of finite vector spaces, cf. Goldman - Rota, Finite vector spaces and Eulerian generating functions, Studies in Appl. Math. XLIX (3), 1970. $\endgroup$ – Johann Cigler Mar 1 '12 at 12:36
5
$\begingroup$

For Gaussian binomial coefficients we have $$ \sum_{k = 0}^n \binom nk_q = \sum_{m = 0}^\infty a_m q^m, $$ where $$ a_m = \sum_{\lambda\vdash m} \#\{k\in \mathbf Z_{\geq 0}\mid \lambda_1\leq n-k, \lambda'_1\leq k\}. $$ The notation $\lambda\vdash m$ signifies that $\lambda$ is an integer partition of $m$. Also $\lambda_1$ is the first (largest) part of $\lambda$ and $\lambda'_1$ is the number of positive parts in $\lambda$.

This follows from the following well-known fact about Gaussian binomial coefficients: $$ \binom nk_q = \sum_\lambda q^{|\lambda|}, $$ the sum being over all partitions $\lambda$ where $\lambda_1\leq n-k$ and $\lambda'_1\leq k$ (see, for example Stanley's Enumerative Combinatorics, vol. 1, or Eq. (4) in my expository article titled Counting subspaces in a Finite Vector Space).

$\endgroup$
2
$\begingroup$

One more version - analog of $\sum_{i=0}^n(-1)^i\binom ni=0$: $$ \sum_{i=0}^n(-1)^i\binom ni_q=\begin{cases}0,&n=2k-1\\ \prod_{j=1}^k(1-q^{2j-1}),&n=2k\end{cases} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.