Gaussian binomial coefficient

In mathematics, the Gaussian binomial coefficients (also called Gaussian coefficients, Gaussian polynomials, or q-binomial coefficients) are q-analogs of the binomial coefficients.

Contents

Definition

The Gaussian binomial coefficients are defined by

{m \choose r}_q = \begin{cases} \frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r%2B1})} {(1-q)(1-q^2)\cdots(1-q^r)} & r \le m \\ 0 & r>m \end{cases}

where m and r are non-negative integers. For r = 0 the value is 1 since numerator and denominator are both empty products. Although the formula in the first clause appears to involve a rational function, it actually designates a polynomial, because the division is exact in Z[q]. Note that the formula can be applied for r = m + 1, and gives 0 due to a factor 1 − q0 = 0 in the numerator, in accordance with the second clause (for even larger r the factor 0 remains present in the numerator, but its further factors would involve negative powers of q, whence explicitly stating the second clause is preferable). All of the factors in numerator and denominator are divisible by 1 − q, with as quotient a q number:

[k]_q=\frac{1-q^k}{1-q}=\sum_{0\leq i<k}q^i=1%2Bq%2Bq^2%2B\cdots%2Bq^{k-1};

dividing out these factors gives the equivalent formula

{m \choose r}_q=\frac{[m]_q[m-1]_q\cdots[m-r%2B1]_q}{[1]_q[2]_q\cdots[r]_q}\quad(r\leq m),

which makes evident the fact that substituting q = 1 into \tbinom mr_q gives the ordinary binomial coefficient \tbinom mr. In terms of the q factorial [n]_q!=[1]_q[2]_q\cdots[n]_q, the formula can be stated as

{m \choose r}_q=\frac{[m]_q!}{[r]_q!\,[m-r]_q!}\quad(r\leq m),

a compact form (often given as only definition), which however hides the presence of many common factors in numerator and denominator. This form does make obvious the symmetry \tbinom mr_q=\tbinom m{m-r}_q for r ≤ m.

Unlike the ordinary binomial coefficient, the Gaussian binomial coefficient has finite values for m\rightarrow \infty:

{\infty \choose r}_q = \lim_{m\rightarrow \infty} {m \choose r}_q = \frac{1}{[r]_q!\,(1-q)^r}

Examples

{0 \choose 0}_q = {1 \choose 0}_q = 1
{1 \choose 1}_q = \frac{1-q}{1-q}=1
{2 \choose 1}_q = \frac{1-q^2}{1-q}=1%2Bq
{3 \choose 1}_q = \frac{1-q^3}{1-q}=1%2Bq%2Bq^2
{3 \choose 2}_q = \frac{(1-q^3)(1-q^2)}{(1-q)(1-q^2)}=1%2Bq%2Bq^2
{4 \choose 2}_q = \frac{(1-q^4)(1-q^3)}{(1-q)(1-q^2)}=(1%2Bq^2)(1%2Bq%2Bq^2)=1%2Bq%2B2q^2%2Bq^3%2Bq^4

Properties

Like the ordinary binomial coefficients, the Gaussian binomial coefficients are center-symmetric i.e. invariant under the reflection r \rightarrow m-r :

{m \choose r}_q = {m \choose m-r}_q.

In particular,

{m \choose 0}_q ={m \choose m}_q=1 \, ,
{m \choose 1}_q ={m \choose m-1}_q=\frac{1-q^m}{1-q}=1%2Bq%2B \cdots %2B q^{m-1} \quad m \ge 1 \, .

The name Gaussian binomial coefficient stems from the fact that their evaluation at q = 1 is

{m \choose r}_1 = {m \choose r}

for all m and r.

The analogs of Pascal identities for the Gaussian binomial coefficients are

{m \choose r}_q = q^r {m-1 \choose r}_q %2B {m-1 \choose r-1}_q

and

{m \choose r}_q = {m-1 \choose r}_q %2B q^{m-r}{m-1 \choose r-1}_q.

There are analogs of the binomial formula, and of Newton's generalized version of it for negative integer exponents, although for the former the Gaussian binomial coefficients themselves do not appear as coefficients:

\prod_{k=0}^{n-1} (1%2Bq^kt)=\sum_{k=0}^n q^{k(k-1)/2} {n \choose k}_q t^k

and

\prod_{k=0}^{n-1} \frac{1}{(1-q^kt)}=\sum_{k=0}^\infty {n%2Bk-1 \choose k}_q t^k.

which, for n\rightarrow\infty become:

\prod_{k=0}^{\infty} (1%2Bq^kt)=\sum_{k=0}^\infty \frac{q^{k(k-1)/2}t^k}{[k]_q!\,(1-q)^k}

and

\prod_{k=0}^\infty \frac{1}{(1-q^kt)}=\sum_{k=0}^\infty \frac{t^k}{[k]_q!\,(1-q)^k} .

The first Pascal identity allows one to compute the Gaussian binomial coefficients recursively (with respect to m ) using the initial "boundary" values

{m \choose m}_q ={m \choose 0}_q=1

and also incidentally shows that the Gaussian binomial coefficients are indeed polynomials (in q). The second Pascal identity follows from the first using the substitution r \rightarrow m-r and the invariance of the Gaussian binomial coefficients under the reflection r \rightarrow m-r . Both Pascal identities together imply

{m \choose r}_q = {{1-q^{m}}\over {1-q^{m-r}}} {m-1 \choose r}_q

which leads (when applied iteratively for m, m − 1, m − 2,....) to an expression for the Gaussian binomial coefficient as given in the definition above.

Applications

Gaussian binomial coefficients occur in the counting of symmetric polynomials and in the theory of partitions. The coefficient of qr in

{n%2Bm \choose m}_q

is the number of partitions of r with m or fewer parts each less than or equal to n. Equivalently, it is also the number of partitions of r with n or fewer parts each less than or equal to m.

Gaussian binomial coefficients also play an important role in the enumerative theory of symmetric spaces defined over a finite field. In particular, for every finite field Fq with q elements, the Gaussian binomial coefficient

{n \choose k}_q

counts the number vn,k;q of different k-dimensional vector subspaces of an n-dimensional vector space over Fq (a Grassmannian). For example, the Gaussian binomial coefficient

{n \choose 1}_q=1%2Bq%2Bq^2%2B\cdots%2Bq^{n-1}

is the number of different lines in Fqn (a projective space).

In the conventions common in applications to quantum groups, a slightly different definition is used; the quantum binomial coefficient there is

q^{k^2 - n k}{n \choose k}_{q^2}.

This version of the quantum binomial coefficient is symmetric under exchange of q and q^{-1}.

Triangles

The Gaussian binomial coefficients can be arranged in a triangle for each q, which is Pascal's triangle for q=1.
Read line by line these triangles form the following sequences in the OEIS:

References