In mathematics, the Gaussian binomial coefficients (also called Gaussian coefficients, Gaussian polynomials, or q-binomial coefficients) are q-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as ${\displaystyle {\binom {n}{k))_{q))$ or ${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix))_{q))$, is a polynomial in q with integer coefficients, whose value when q is set to a prime power counts the number of subspaces of dimension k in a vector space of dimension n over ${\displaystyle \mathbb {F} _{q))$, a finite field with q elements; i.e. it is the number of points in the finite Grassmannian ${\displaystyle \mathrm {Gr} (k,\mathbb {F} _{q}^{n})}$.

Definition

The Gaussian binomial coefficients are defined by:^[1]

${\displaystyle {m \choose r}_{q}={\frac {(1-q^{m})(1-q^{m-1})\cdots (1-q^{m-r+1})}{(1-q)(1-q^{2})\cdots (1-q^{r})))}$

where m and r are non-negative integers. If r > m, this evaluates to 0. For r = 0, the value is 1 since both the numerator and denominator are empty products.

Although the formula at first appears to be a rational function, it actually is a polynomial, because the division is exact in Z[q]

All of the factors in numerator and denominator are divisible by 1 − q, and the quotient is the q-number:

${\displaystyle [k]_{q}=\sum _{0\leq i<k}q^{i}=1+q+q^{2}+\cdots +q^{k-1}={\begin{cases}{\frac {1-q^{k)){1-q))&{\text{for))&q\neq 1\\k&{\text{for))&q=1\end{cases)),}$

Dividing out these factors gives the equivalent formula

${\displaystyle {m \choose r}_{q}={\frac {[m]_{q}[m-1]_{q}\cdots [m-r+1]_{q)){[1]_{q}[2]_{q}\cdots [r]_{q))}\quad (r\leq m).}$

In terms of the q factorial ${\displaystyle [n]_{q}!=[1]_{q}[2]_{q}\cdots [n]_{q))$, the formula can be stated as

${\displaystyle {m \choose r}_{q}={\frac {[m]_{q}!}{[r]_{q}!\,[m-r]_{q}!))\quad (r\leq m).}$

Substituting q = 1 into ${\displaystyle {\tbinom {m}{r))_{q))$ gives the ordinary binomial coefficient ${\displaystyle {\tbinom {m}{r))}$.

The Gaussian binomial coefficient has finite values as ${\displaystyle m\rightarrow \infty }$:

${\displaystyle {\infty \choose r}_{q}=\lim _{m\rightarrow \infty }{m \choose r}_{q}={\frac {1}{(1-q)(1-q^{2})\cdots (1-q^{r})))={\frac {1}{[r]_{q}!\,(1-q)^{r))))$

Examples

${\displaystyle {0 \choose 0}_{q}={1 \choose 0}_{q}=1}$

${\displaystyle {1 \choose 1}_{q}={\frac {1-q}{1-q))=1}$

${\displaystyle {2 \choose 1}_{q}={\frac {1-q^{2)){1-q))=1+q}$

${\displaystyle {3 \choose 1}_{q}={\frac {1-q^{3)){1-q))=1+q+q^{2))$

${\displaystyle {3 \choose 2}_{q}={\frac {(1-q^{3})(1-q^{2})}{(1-q)(1-q^{2})))=1+q+q^{2))$

${\displaystyle {4 \choose 2}_{q}={\frac {(1-q^{4})(1-q^{3})}{(1-q)(1-q^{2})))=(1+q^{2})(1+q+q^{2})=1+q+2q^{2}+q^{3}+q^{4))$

${\displaystyle {6 \choose 3}_{q}={\frac {(1-q^{6})(1-q^{5})(1-q^{4})}{(1-q)(1-q^{2})(1-q^{3})))=(1+q^{2})(1+q^{3})(1+q+q^{2}+q^{3}+q^{4})=1+q+2q^{2}+3q^{3}+3q^{4}+3q^{5}+3q^{6}+2q^{7}+q^{8}+q^{9))$

Combinatorial descriptions

Inversions

One combinatorial description of Gaussian binomial coefficients involves inversions.

The ordinary binomial coefficient ${\displaystyle {\tbinom {m}{r))}$ counts the r-combinations chosen from an m-element set. If one takes those m elements to be the different character positions in a word of length m, then each r-combination corresponds to a word of length m using an alphabet of two letters, say {0,1}, with r copies of the letter 1 (indicating the positions in the chosen combination) and m − r letters 0 (for the remaining positions).

So, for example, the ${\displaystyle {4 \choose 2}=6}$ words using 0s and 1s are ${\displaystyle 0011,0101,0110,1001,1010,1100}$.

To obtain the Gaussian binomial coefficient ${\displaystyle {\tbinom {m}{r))_{q))$, each word is associated with a factor q^d, where d is the number of inversions of the word, where, in this case, an inversion is a pair of positions where the left of the pair holds the letter 1 and the right position holds the letter 0.

With the example above, there is one word with 0 inversions, ${\displaystyle 0011}$, one word with 1 inversion, ${\displaystyle 0101}$, two words with 2 inversions, ${\displaystyle 0110}$, ${\displaystyle 1001}$, one word with 3 inversions, ${\displaystyle 1010}$, and one word with 4 inversions, ${\displaystyle 1100}$. This is also the number of left-shifts of the 1s from the initial position.

These correspond to the coefficients in ${\displaystyle {4 \choose 2}_{q}=1+q+2q^{2}+q^{3}+q^{4))$.

Another way to see this is to associate each word with a path across a rectangular grid with height r and width m − r, going from the bottom left corner to the top right corner. The path takes a step right for each 0 and a step up for each 1. An inversion switches the directions of a step (right+up becomes up+right and vice versa), hence the number of inversions equals the area under the path.

Balls into bins

Let ${\displaystyle B(n,m,r)}$ be the number of ways of throwing ${\displaystyle r}$ indistinguishable balls into ${\displaystyle m}$ indistinguishable bins, where each bin can contain up to ${\displaystyle n}$ balls. The Gaussian binomial coefficient can be used to characterize ${\displaystyle B(n,m,r)}$. Indeed,

${\displaystyle B(n,m,r)=[q^{r}]{n+m \choose m}_{q}.}$

where ${\displaystyle [q^{r}]P}$ denotes the coefficient of ${\displaystyle q^{r))$ in polynomial ${\displaystyle P}$ (see also Applications section below).

Properties

Reflection

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

${\displaystyle {m \choose r}_{q}={m \choose m-r}_{q}.}$

In particular,

${\displaystyle {m \choose 0}_{q}={m \choose m}_{q}=1\,,}$

${\displaystyle {m \choose 1}_{q}={m \choose m-1}_{q}={\frac {1-q^{m)){1-q))=1+q+\cdots +q^{m-1}\quad m\geq 1\,.}$

Limit at q = 1

The evaluation of a Gaussian binomial coefficient at q = 1 is

${\displaystyle \lim _{q\to 1}{\binom {m}{r))_{q}={\binom {m}{r))}$

i.e. the sum of the coefficients gives the corresponding binomial value.

Degree of polynomial

The degree of ${\displaystyle {\binom {m}{r))_{q))$ is ${\displaystyle {\binom {m+1}{2))-{\binom {r+1}{2))-{\binom {(m-r)+1}{2))=r(m-r)}$.

q identities

Analogs of Pascal's identity

The analogs of Pascal's identity for the Gaussian binomial coefficients are:^[2]

${\displaystyle {m \choose r}_{q}=q^{r}{m-1 \choose r}_{q}+{m-1 \choose r-1}_{q))$

and

${\displaystyle {m \choose r}_{q}={m-1 \choose r}_{q}+q^{m-r}{m-1 \choose r-1}_{q}.}$

When ${\displaystyle q=1}$, these both give the usual binomial identity. We can see that as ${\displaystyle m\to \infty }$, both equations remain valid.

The first Pascal analog allows computation of the Gaussian binomial coefficients recursively (with respect to m ) using the initial values

${\displaystyle {m \choose m}_{q}={m \choose 0}_{q}=1}$

and also shows that the Gaussian binomial coefficients are indeed polynomials (in q).

The second Pascal analog follows from the first using the substitution ${\displaystyle r\rightarrow m-r}$ and the invariance of the Gaussian binomial coefficients under the reflection ${\displaystyle r\rightarrow m-r}$.

These identities have natural interpretations in terms of linear algebra. Recall that ${\displaystyle {\tbinom {m}{r))_{q))$ counts r-dimensional subspaces ${\displaystyle V\subset \mathbb {F} _{q}^{m))$, and let ${\displaystyle \pi :\mathbb {F} _{q}^{m}\to \mathbb {F} _{q}^{m-1))$ be a projection with one-dimensional nullspace ${\displaystyle E_{1))$. The first identity comes from the bijection which takes ${\displaystyle V\subset \mathbb {F} _{q}^{m))$ to the subspace ${\displaystyle V'=\pi (V)\subset \mathbb {F} _{q}^{m-1))$; in case ${\displaystyle E_{1}\not \subset V}$, the space ${\displaystyle V'}$ is r-dimensional, and we must also keep track of the linear function ${\displaystyle \phi :V'\to E_{1))$ whose graph is ${\displaystyle V}$; but in case ${\displaystyle E_{1}\subset V}$, the space ${\displaystyle V'}$ is (r−1)-dimensional, and we can reconstruct ${\displaystyle V=\pi ^{-1}(V')}$ without any extra information. The second identity has a similar interpretation, taking ${\displaystyle V}$ to ${\displaystyle V'=V\cap E_{n-1))$ for an (m−1)-dimensional space ${\displaystyle E_{m-1))$, again splitting into two cases.

Proofs of the analogs

Both analogs can be proved by first noting that from the definition of ${\displaystyle {\tbinom {m}{r))_{q))$, we have:

${\displaystyle {\binom {m}{r))_{q}={\frac {1-q^{m)){1-q^{m-r))}{\binom {m-1}{r))_{q))$

(1)

${\displaystyle {\binom {m}{r))_{q}={\frac {1-q^{m)){1-q^{r))}{\binom {m-1}{r-1))_{q))$

(2)

${\displaystyle {\frac {1-q^{r)){1-q^{m-r))}{\binom {m-1}{r))_{q}={\binom {m-1}{r-1))_{q))$

(3)

As

${\displaystyle {\frac {1-q^{m)){1-q^{m-r))}={\frac {1-q^{r}+q^{r}-q^{m)){1-q^{m-r))}=q^{r}+{\frac {1-q^{r)){1-q^{m-r))))$

Equation (1) becomes:

${\displaystyle {\binom {m}{r))_{q}=q^{r}{\binom {m-1}{r))_{q}+{\frac {1-q^{r)){1-q^{m-r))}{\binom {m-1}{r))_{q))$

and substituting equation (3) gives the first analog.

A similar process, using

${\displaystyle {\frac {1-q^{m)){1-q^{r))}=q^{m-r}+{\frac {1-q^{m-r)){1-q^{r))))$

instead, gives the second analog.

q-binomial theorem

There is an analog of the binomial theorem for q-binomial coefficients, known as the Cauchy binomial theorem:

${\displaystyle \prod _{k=0}^{n-1}(1+q^{k}t)=\sum _{k=0}^{n}q^{k(k-1)/2}{n \choose k}_{q}t^{k}.}$

Like the usual binomial theorem, this formula has numerous generalizations and extensions; one such, corresponding to Newton's generalized binomial theorem for negative powers, is

${\displaystyle \prod _{k=0}^{n-1}{\frac {1}{1-q^{k}t))=\sum _{k=0}^{\infty }{n+k-1 \choose k}_{q}t^{k}.}$

In the limit ${\displaystyle n\rightarrow \infty }$, these formulas yield

${\displaystyle \prod _{k=0}^{\infty }(1+q^{k}t)=\sum _{k=0}^{\infty }{\frac {q^{k(k-1)/2}t^{k)){[k]_{q}!\,(1-q)^{k))))$

and

${\displaystyle \prod _{k=0}^{\infty }{\frac {1}{1-q^{k}t))=\sum _{k=0}^{\infty }{\frac {t^{k)){[k]_{q}!\,(1-q)^{k))))$.

Setting ${\displaystyle t=q}$ gives the generating functions for distinct and any parts respectively. (See also Basic hypergeometric series.)

Central q-binomial identity

With the ordinary binomial coefficients, we have:

${\displaystyle \sum _{k=0}^{n}{\binom {n}{k))^{2}={\binom {2n}{n))}$

With q-binomial coefficients, the analog is:

${\displaystyle \sum _{k=0}^{n}q^{k^{2)){\binom {n}{k))_{q}^{2}={\binom {2n}{n))_{q))$

Applications

Gauss originally used the Gaussian binomial coefficients in his determination of the sign of the quadratic Gauss sum.^[3]

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

${\displaystyle {n+m \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 projective spaces defined over a finite field. In particular, for every finite field F_q with q elements, the Gaussian binomial coefficient

${\displaystyle {n \choose k}_{q))$

counts the number of k-dimensional vector subspaces of an n-dimensional vector space over F_q (a Grassmannian). When expanded as a polynomial in q, it yields the well-known decomposition of the Grassmannian into Schubert cells. For example, the Gaussian binomial coefficient

${\displaystyle {n \choose 1}_{q}=1+q+q^{2}+\cdots +q^{n-1))$

is the number of one-dimensional subspaces in (F_q)ⁿ (equivalently, the number of points in the associated projective space). Furthermore, when q is 1 (respectively −1), the Gaussian binomial coefficient yields the Euler characteristic of the corresponding complex (respectively real) Grassmannian.

The number of k-dimensional affine subspaces of F_qⁿ is equal to

${\displaystyle q^{n-k}{n \choose k}_{q))$.

This allows another interpretation of the identity

${\displaystyle {m \choose r}_{q}={m-1 \choose r}_{q}+q^{m-r}{m-1 \choose r-1}_{q))$

as counting the (r − 1)-dimensional subspaces of (m − 1)-dimensional projective space by fixing a hyperplane, counting such subspaces contained in that hyperplane, and then counting the subspaces not contained in the hyperplane; these latter subspaces are in bijective correspondence with the (r − 1)-dimensional affine subspaces of the space obtained by treating this fixed hyperplane as the hyperplane at infinity.

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

${\displaystyle q^{k^{2}-nk}{n \choose k}_{q^{2))}$.

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