10
$\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
  • 1
    $\begingroup$ I think that you need to define your normalizations before stating the question. What is your definition of $[n]_q?$ $\endgroup$ Mar 1, 2012 at 7:54

4 Answers 4

11
$\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$
1
  • $\begingroup$ Is it the answer? $\endgroup$ May 7, 2016 at 10:52
7
$\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$
3
  • $\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$ Mar 1, 2012 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$ Mar 1, 2012 at 12:36
  • $\begingroup$ The second one is the q-binomial theorem en.wikipedia.org/wiki/… evaluated at $t=q$. The first one is exercise 99 in the book "Integer Partitions" by Andrews and Eriksson, 2004, but no solution is given. Is there a similar conceptual approach? $\endgroup$
    – azimut
    Nov 20, 2023 at 14:16
7
$\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$
4
$\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$
4
  • $\begingroup$ Could you sketch a proof of this, or give a reference? $\endgroup$
    – aleph
    Feb 23, 2022 at 21:52
  • 2
    $\begingroup$ @aleph It was proved by Gauss in his "Summatio Quarumdam Serierum Singularium", section 6. Here is a link: eudml.org/doc/203313. $\endgroup$ Oct 1, 2023 at 21:01
  • $\begingroup$ @LucasCuller Many thanks for this reference! $\endgroup$ Oct 2, 2023 at 4:27
  • 1
    $\begingroup$ A proof is found on pages 71/72 in the book "Integer Partitions" by Andrews and Eriksson, 2004. They call it the "Gaussian formula". $\endgroup$
    – azimut
    Nov 15, 2023 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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