= Gaussian binomial coefficient
{c}
{title2=$\binom nk_t=\prod_{j=1}^k(1-t^{n-k+j})/(1-t^j)$}
{wiki}
= Gaussian polynomial
{c}
{synonym}
= q-binomial coefficient
{synonym}
A <Gaussian binomial coefficient> refines an ordinary <binomial coefficient> into a <polynomial> that remembers a size statistic. For <nonnegative integers> $n$ and $0\leq k\leq n$, write
$$
G_{n,k}(t)=\binom nk_t=\prod_{j=1}^k\frac{1-t^{n-k+j}}{1-t^j}.
$$
The product represents a <polynomial>; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The <Gaussian binomial coefficient recurrence> gives a way to compute it with only <addition> and <multiplication>. The <empty product> for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the <polynomial> recovers $\binom nk$.
For example,
$$
\boxed{G_{4,2}(t)=1+t+2t^2+t^3+t^4.}
$$
At $t=1$ this gives six objects, but its <coefficients> reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The <lattice-path interpretation of Gaussian binomial coefficients> makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded <areas> $0,1,2,2,3,4$.
\Image[/gaussian-binomial-paths-and-partitions.png]
{title=The six <lattice paths> counted by $G_{4,2}(t)$, weighted by the number of shaded cells}
{description=Original exact enumeration of paths with two north and two east steps. Reading shaded row lengths from top to bottom gives a <partition in a rectangle>. Equal-sized diagrams contribute to the same <coefficient>.}
This is useful because an aggregate count can hide the feature one actually wants. A <generating function> retains the distribution of a statistic, so <coefficient extraction> answers questions such as “how many allowed diagrams contain exactly two cells?” The <partition interpretation of Gaussian binomial coefficients> makes every <coefficient> a nonnegative <integer> without relying on cancellation in the product formula.
An unexpected second use comes from <linear algebra>. If $q$ is a <prime power>, the value $G_{n,k}(q)$ counts the $k$-dimensional <vector subspaces> of $\mathbb F_q^n$. Thus the same expression that counts six paths at $t=1$ counts \b[35 two-dimensional subspaces of $\mathbb F_2^4$] at $t=2$. The <Gaussian binomial coefficient counts finite-field subspaces> article explains why selecting a <vector subspace> differs from selecting a <subset> of coordinates. <Enumerative Combinatorics, Volume 1 (second-edition draft) by Richard Stanley>{ref}
This relationship illustrates a <q-analogue>: the parameter can encode a statistic in one interpretation and the size of a <finite field> in another. Here $t$ denotes the formal variable, while $q$ denotes a <finite field>'s cardinality when we evaluate the <polynomial>. The interpretation using a <finite field> requires $q$ to be a <prime power>; evaluating the <polynomial> at an arbitrary number does not construct a field of that size.
Back to article page
