40.01.06 · combinatorics / enumeration-generating-functions

q-Analogues, Gaussian Binomial Coefficients, and the Combinatorics of Partitions

shipped3 tiersLean: none

Anchor (Master): Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.7-1.8 and §3 (the q-binomial as a rank-generating function of the subspace lattice, q-Vandermonde, Durfee squares); Andrews 1976 *The Theory of Partitions* Ch. 2, 7 (Jacobi triple product, Rogers-Ramanujan); Andrews-Eriksson 2004 *Integer Partitions* Ch. 7-8 (Durfee squares, Franklin, Glaisher); Cauchy 1843 *Comptes Rendus* 17 (the q-binomial theorem); Gauss 1808 (the Gaussian binomial coefficient)

Intuition Beginner

You already know the binomial coefficient: $(k n)$ counts the ways to choose $k$ things from $n$ , and it is the number on row $n$ , position $k$ of Pascal's triangle. This unit replaces each of those plain counts by a small polynomial in a bookkeeping letter $q$ . Setting $q = 1$ in the polynomial gives back the ordinary count, but for other values of $q$ the polynomial remembers extra structure that the plain number forgot. An object built this way is called a q-analogue: same shape as the original, with a $q$ that tracks finer information.

The simplest q-analogue is the q-integer. Instead of the number $n$ , you use $1 + q + q^{2} + \dots + q^{n - 1}$ . Add up its terms at $q = 1$ and you recover $n$ , since there are $n$ ones. Build a "q-factorial" by multiplying q-integers, and then a Gaussian binomial coefficient by the same recipe that makes the ordinary binomial from factorials. The remarkable fact is that this ratio always comes out as a polynomial in $q$ with whole-number coefficients that are never negative.

What do those coefficients count? They count partitions — ways of writing a number as a sum of pieces, drawn as rows of dots — that fit inside a fixed rectangle. So the Gaussian binomial is the one polynomial that displays, all at once, how many such partitions there are of each total size. The plain count "how many fit in the box" is the value at $q = 1$ ; the polynomial sorts them by area.

There is one more surprise waiting at the next tier. Over a finite number system with $q$ elements, the very same Gaussian binomial counts something completely different: the number of $k$ -dimensional flat subspaces sitting inside an $n$ -dimensional space. One polynomial, two unrelated-looking counting problems — that coincidence is the heart of the subject.

Visual Beginner

A partition is drawn as a Ferrers diagram: rows of dots, one row per part, longest on top. "Fits in a $k$ by $m$ box" means at most $k$ rows and each row at most $m$ dots wide. The Gaussian binomial $(k k + m)_{q}$ collects every such diagram, sorting them by how many dots they use: the coefficient of $q^{t}$ is the number of diagrams of exactly $t$ dots that fit in the box.

object	plain version	q-analogue (the polynomial)	value at $q = 1$
the number $n$	$n$	$1 + q + \dots + q^{n - 1}$	$n$
$2$ choose $1$	$2$	$1 + q$	$2$
$4$ choose $2$	$6$	$1 + q + 2 q^{2} + q^{3} + q^{4}$	$6$
a partition's diagram	a dot picture	weight $q^{(number of dots)}$	$1$

Reading the third row: the six partitions fitting in a $2$ by $2$ box have $0, 1, 2, 2, 3, 4$ dots, and grouping them by size gives the coefficients $1, 1, 2, 1, 1$ . The polynomial $1 + q + 2 q^{2} + q^{3} + q^{4}$ is the honest, size-aware version of the plain count $6$ .

Worked example Beginner

Let us build $(2 4)_{q}$ from scratch and check that its coefficients count partitions in a $2$ by $2$ box.

Step 1. Write the q-integers. $[1]_{q} = 1$ . $[2]_{q} = 1 + q$ . $[3]_{q} = 1 + q + q^{2}$ . $[4]_{q} = 1 + q + q^{2} + q^{3}$ .

Step 2. Form the pieces of the ratio. The recipe is $(2 4)_{q} = \frac{[ 4 ] _{q} [ 3 ] _{q}}{[ 2 ] _{q} [ 1 ] _{q}}$ — the q-analogue of $\frac{4 \times 3}{2 \times 1} = 6$ . So the numerator is $(1 + q + q^{2} + q^{3}) (1 + q + q^{2})$ and the denominator is $(1 + q) (1) = 1 + q$ .

Step 3. Divide. First, $(1 + q + q^{2} + q^{3}) \div (1 + q) = 1 + q^{2}$ , since $(1 + q) (1 + q^{2}) = 1 + q + q^{2} + q^{3}$ . So $(2 4)_{q} = (1 + q^{2}) (1 + q + q^{2}) = 1 + q + 2 q^{2} + q^{3} + q^{4}$ .

Step 4. Check by listing partitions in a $2$ by $2$ box. The diagrams with at most $2$ rows, each at most $2$ wide, are: the empty one ( $0$ dots); a single dot ( $1$ dot); a row of two ( $2$ dots); two single dots stacked ( $2$ dots); a row of two over a single dot ( $3$ dots); and the full square ( $4$ dots). Grouping by dot-count gives sizes $0, 1, 2, 2, 3, 4$ , hence coefficients $1, 1, 2, 1, 1$ — exactly the polynomial from Step 3.

What this tells us: the Gaussian binomial is genuinely a count, sorted by size. Adding its coefficients ( $1 + 1 + 2 + 1 + 1 = 6$ ) recovers the plain "how many fit", and the value at $q = 1$ does the adding automatically.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $q$ is an indeterminate (or a complex number with $∣ q ∣ < 1$ when an infinite product must converge). Standard q-series notation is introduced here and recorded in _meta/NOTATION.md: the q-Pochhammer symbol $(a; q)_{n} := \prod_{i = 0}^{n - 1} (1 - a q^{i})$ with $(a; q)_{\infty} := \prod_{i \geq 0} (1 - a q^{i})$ , the Euler function $(q; q)_{\infty} = \prod_{k \geq 1} (1 - q^{k})$ , and the q-binomial symbol $(k n)_{q}$ defined below.

Definition (q-integer, q-factorial). For $n \geq 0$ the q-integer is $[n]_{q} := \frac{1 - q ^{n}}{1 - q} = 1 + q + q^{2} + \dots + q^{n - 1}$ (with $[0]_{q} = 0$ ), and the q-factorial is $[n]_{q}! := [1]_{q} [2]_{q} \dots [n]_{q}$ (with $[0]_{q}! = 1$ ). At $q = 1$ these specialise to $n$ and $n!$ .

Definition (Gaussian binomial coefficient). For $0 \leq k \leq n$ the Gaussian (q-)binomial coefficient is $$ \binom{n}{k}_q := \frac{[n]_q!}{[k]_q!,[n-k]_q!} = \frac{(q; q)n}{(q; q)k,(q; q){n-k}} = \prod{i=1}^{k}\frac{1 - q^{n-k+i}}{1 - q^{i}}, $$ with $(k n)_{q} = 0$ for $k < 0$ or $k > n$ . Although written as a ratio, it is a polynomial in $q$ (Key theorem below). At $q = 1$ it specialises to $(k n)$ . The symmetry $(k n)_{q} = (n - k n)_{q}$ is immediate from the factorial form, and corresponds to conjugating partitions across the box.

Definition (partition, Ferrers diagram, conjugate, rank). A partition $λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{r} > 0)$ of $∣ λ ∣ := \sum_{i} λ_{i}$ has Ferrers diagram the left-justified array of $λ_{i}$ cells in row $i$ . The conjugate $λ^{'}$ is obtained by transposing the diagram (rows become columns); $λ_{j}^{'} = # {i : λ_{i} \geq j}$ . We say $λ$ fits in the $k \times m$ box, written $λ \subseteq k \times m$ , when $r \leq k$ and $λ_{1} \leq m$ . The Durfee square of $λ$ is the largest $d \times d$ square fitting in the upper-left of the diagram, i.e. the largest $d$ with $λ_{d} \geq d$ ; this $d$ is the rank-of-the-Durfee-square statistic. The rank of $λ$ (in the partition-theory sense) is $λ_{1} - r$ , the largest part minus the number of parts.

Definition (box generating function). For the box $k \times m$ set $G_{k, m} (q) := \sum_{λ \subseteq k \times m} q^{∣ λ ∣}$ , the generating polynomial weighting each fitting partition by its size. The central identification, proved next, is $G_{k, m} (q) = (k k + m)_{q}$ .

Counterexamples to common slips Intermediate+

" $(k n)_{q}$ is the q-integer raised to a power, or some power of $q$ times $(k n)$ ." It is neither: it is a genuine polynomial of degree $k (n - k)$ whose coefficients are a non-constant sequence (e.g. $(2 4)_{q} = 1 + q + 2 q^{2} + q^{3} + q^{4}$ ). Only its value at $q = 1$ is $(k n)$ .
"The two q-Pascal recurrences are the same identity written twice." They are genuinely different decompositions — one splits partitions by whether the last column is full, the other by whether the last row is full — and produce the asymmetric factors $q^{k}$ versus $q^{n - k}$ . Their equality is the conjugation symmetry, not a tautology.
" $[n]_{q}!$ and $(k n)_{q}$ make sense to evaluate at $q = 1$ by substituting into the ratio." The ratio $\frac{1 - q ^{n}}{1 - q}$ is $\frac{0}{0}$ at $q = 1$ ; one must first simplify to the polynomial $1 + \dots + q^{n - 1}$ (or to the polynomial form of $(k n)_{q}$ ) before substituting. The limit exists, but the unreduced quotient is undefined there.
"Counting subspaces of $F_{q}^{n}$ works for any $q$ ." The subspace interpretation requires $q$ to be a prime power, so that $F_{q}$ exists. For general $q$ the same polynomial still counts box-partitions, but there is no field and no subspace lattice.

Key theorem with proof Intermediate+

The signature theorem is that the Gaussian binomial is simultaneously a polynomial with non-negative coefficients and the generating function for partitions in a box, with the two q-Pascal recurrences as the bijective engine.

Theorem (polynomiality and the box interpretation). For $0 \leq k \leq n$ and $m = n - k$ , the Gaussian binomial coefficient $(k n)_{q}$ is a polynomial in $q$ of degree $k m$ with non-negative integer coefficients, and $$ \binom{n}{k}q ;=; G{k,m}(q) ;=; \sum_{\lambda \subseteq k \times m} q^{|\lambda|}. $$ It satisfies the two q-Pascal recurrences $$ \binom{n}{k}_q = \binom{n-1}{k-1}_q + q^{k}\binom{n-1}{k}_q = q^{,n-k}\binom{n-1}{k-1}_q + \binom{n-1}{k}_q, $$ with the boundary values $(0 n)_{q} = (n n)_{q} = 1$ .

Proof. First establish the recurrences from the box generating function $G_{k, m} (q)$ , which manifestly has non-negative coefficients. A partition $λ \subseteq k \times m$ either has fewer than $k$ rows or has exactly $k$ rows (a full last row of the box is not forced, but consider the last column). Split on whether the rightmost column $j = m$ is occupied to its full height — equivalently, whether $λ$ uses a part equal to $m$ in a way that leaves a $k \times (m - 1)$ sub-box once a full column is removed. Concretely, classify $λ \subseteq k \times m$ by its number of parts equal to $m$ versus its parts $< m$ : removing the leftmost full column (when present) decrements the width. This yields, after the standard accounting, the additive split $$ G_{k,m}(q) = G_{k,m-1}(q) + q^{m},G_{k-1,m}(q), $$ where the term $G_{k, m - 1}$ collects partitions with $λ_{1} \leq m - 1$ (no part of full width) and $q^{m} G_{k - 1, m}$ collects partitions with $λ_{1} = m$ : deleting that first row of width $m$ contributes $q^{m}$ and leaves a partition in the $(k - 1) \times m$ box. Writing $G_{k, m} = (k k + m)_{q}$ as a claim and translating, $G_{k, m - 1} = (k n - 1)_{q}$ and $G_{k - 1, m} = (k - 1 n - 1)_{q}$ , this is exactly the second q-Pascal recurrence $(k n)_{q} = (k n - 1)_{q} + q^{n - k} (k - 1 n - 1)_{q}$ . Conjugating the box ( $k \leftrightarrow m$ ) and repeating gives the first recurrence with the factor $q^{k}$ .

It remains to verify that the ratio $(k n)_{q} = (q; q)_{n} / ((q; q)_{k} (q; q)_{n - k})$ satisfies the same recurrence and boundary data, which forces equality with the polynomial $G_{k, m}$ . Compute directly: $$ \binom{n-1}{k-1}q + q^{k}\binom{n-1}{k}q = \frac{(q;q){n-1}}{(q;q){k-1}(q;q){n-k}}\Big( 1 + q^k \cdot \frac{1 - q^{n-k}}{1 - q^{k}}\Big)^{!*}, $$ where the bracket, after clearing the common factor $(q;q){n-1}/((q;q){k}(q;q){n-k}) $, e q u a l s$ \frac{(1 - q^{k}) + q^{k}(1 - q^{n-k})}{1} = 1 - q^{n} $u pt o t ha t f a c t or; m u l t i pl y in g ba c k g i v es$ \frac{(q;q)_{n-1}(1 - q^n)}{(q;q)k (q;q){n-k}} = \frac{(q;q)_n}{(q;q)k(q;q){n-k}} = \binom{n}{k}q $. (T h es t a r r e d s t e p i s t h ee l e m e n t a r y a l g e b r a$ (1-q^k) + q^k(1-q^{n-k}) = 1 - q^n $.) H e n ce t h er a t i oo b ey s t h e f i r s tq - P a sc a l r ec u r r e n ce, an d b y sy mm e t r y t h eseco n d; w i t h$ \binom{n}{0}q = \binom{n}{n}q = 1 = G{0,m} = G{k,0} $ma t c hin g, in d u c t i o n o n$ n $i d e n t i f i es t h er a t i o w i t h$ G{k,m} $, a p o l y n o mia l w i t hn o n - n e g a t i v e in t e g er coe f f i c i e n t s . I t s d e g r ee i s t h es i z e$ km $o f t h e f u l l b o x, a tt ain e d b y t h e u ni q u e ma x ima l p a r t i t i o n f i l l in g t h e$ k \times m $r ec t an g l e .$ \square$

Corollary (Gaussian unimodality). The coefficient sequence of $(k n)_{q}$ is symmetric ( $a_{t} = a_{k m - t}$ , from $λ \mapsto$ its complement in the box) and unimodal (rises then falls); the unimodality is a theorem of Sylvester, revisited at Master tier as a statement about the $sl_{2}$ -action on the subspace lattice.

Bridge. This theorem is the foundational reason a single polynomial answers two questions: it builds toward the subspace count of Advanced results, where $(k n)_{q}$ reappears as the number of $k$ -subspaces of $F_{q}^{n}$ , and the recurrence proved here is exactly the one the subspace count satisfies, so the two are forced equal. The box-partition reading generalises the ordinary $(k n)$ — set $q = 1$ and the diagram-area weighting collapses, leaving the plain count — and it is dual to conjugation: the symmetry $(k n)_{q} = (n - k n)_{q}$ is transposition of diagrams. Putting these together, the central insight is that the q-Pascal recurrence is the combinatorial atom from which polynomiality, positivity, the q-binomial theorem, and the subspace count all descend; this same recurrence appears again in the Durfee-square decomposition of the full partition generating function and in the finite-geometry incidence counts of 40.06.03.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the first q-Pascal recurrence $(k n)_{q} = (k - 1 n - 1)_{q} + q^{k} (k n - 1)_{q}$ bijectively, using partitions in a box.

Hint

$(k n)_{q}$ counts $λ \subseteq k \times (n - k)$ weighted by $q^{∣ λ ∣}$ . Split on whether $λ$ has a part equal to the full width $n - k$ in its first row, or equivalently on the height of the first column.

Answer

Let $m = n - k$ , so $(k n)_{q} = \sum_{λ \subseteq k \times m} q^{∣ λ ∣}$ . Classify each $λ$ by its number of rows. If $λ$ has fewer than $k$ rows, then $λ \subseteq (k - 1) \times m$ and these contribute $(k - 1 ( k - 1 ) + m)_{q} = (k - 1 n - 1)_{q}$ . If $λ$ has exactly $k$ rows, every row is $\geq 1$ , so subtract $1$ from each of the $k$ rows: this removes the leftmost full column of height $k$ , contributing a factor $q^{k}$ , and leaves a partition $μ \subseteq k \times (m - 1)$ , counted by $(k n - 1)_{q}$ . Summing, $(k n)_{q} = (k - 1 n - 1)_{q} + q^{k} (k n - 1)_{q}$ . Rubric: full credit for the split on first-column fullness, the $q^{k}$ from deleting a full column, and the identification of the two residual boxes.

Exercise 4 (medium, symbolic).

Prove the q-binomial theorem $i = 0 \prod n - 1 (1 + q^{i} x) = k = 0 \sum n q^{(2 k)} (k n)_{q} x^{k}$ by induction on $n$ .

Hint

Multiply the $n - 1$ case by the new factor $(1 + q^{n - 1} x)$ and collect the coefficient of $x^{k}$ . You will need a q-Pascal recurrence and the identity $(2 k) = (2 k - 1) + (k - 1)$ .

Answer

Base case $n = 0$ : both sides are $1$ . Assume $\prod_{i = 0}^{n - 2} (1 + q^{i} x) = \sum_{k} q^{(2 k)} (k n - 1)_{q} x^{k}$ . Multiply by $(1 + q^{n - 1} x)$ . The coefficient of $x^{k}$ on the left is $$ q^{\binom{k}{2}}\binom{n-1}{k}_q + q^{n-1},q^{\binom{k-1}{2}}\binom{n-1}{k-1}_q. $$ Using $(2 k) = (2 k - 1) + (k - 1)$ , the second term is $q^{(2 k)} q^{(n - 1) - (k - 1)} (k - 1 n - 1)_{q} = q^{(2 k)} q^{n - k} (k - 1 n - 1)_{q}$ . Factoring out $q^{(2 k)}$ , the bracket is $(k n - 1)_{q} + q^{n - k} (k - 1 n - 1)_{q} = (k n)_{q}$ by the second q-Pascal recurrence. Hence the coefficient of $x^{k}$ is $q^{(2 k)} (k n)_{q}$ , completing the induction. Rubric: full credit for the inductive multiplication, the exponent bookkeeping $(2 k) = (2 k - 1) + k - 1$ , and the application of q-Pascal.

Exercise 6 (medium, symbolic).

Prove the Durfee-square identity $n \geq 0 \sum p (n) q^{n} = d \geq 0 \sum \frac{q ^{d^{2}}}{( ( q ; q ) _{d} ) ^{2}}$ , where $p (n)$ is the unrestricted partition function.

Hint

Every partition has a unique Durfee square of some side $d$ . The $d \times d$ square contributes $q^{d^{2}}$ ; the region to its right is a partition with at most $d$ rows, and the region below is a partition with parts $\leq d$ . Each such region has generating function $1/ (q; q)_{d}$ .

Answer

Fix a partition $λ$ and let $d$ be the side of its Durfee square (the largest $d$ with $λ_{d} \geq d$ ). The diagram splits into three pieces: the $d \times d$ square of size $d^{2}$ contributing $q^{d^{2}}$ ; to the right of the square, the cells in rows $1, \dots, d$ beyond column $d$ form a partition $μ$ with at most $d$ parts (rows), whose generating function is $\sum_{μ : ℓ (μ) \leq d} q^{∣ μ ∣} = \prod_{j = 1}^{d} (1 - q^{j})^{- 1} = 1/ (q; q)_{d}$ ; below the square, the cells in columns $1, \dots, d$ beyond row $d$ form a partition $ν$ with parts $\leq d$ , with the conjugate generating function, also $1/ (q; q)_{d}$ . Since $d$ , $μ$ , $ν$ are independent and determine $λ$ , summing over $d$ gives $\sum_{n} p (n) q^{n} = \sum_{d \geq 0} q^{d^{2}} / ((q; q)_{d})^{2}$ . Rubric: full credit for the unique three-way Durfee decomposition, the two box-bounded generating functions $1/ (q; q)_{d}$ , and the independence giving the product.

Exercise 7 (hard, symbolic).

Prove the q-Vandermonde identity $(k m + n)_{q} = j = 0 \sum k q^{(k - j) (m - j)} (j m)_{q} (k - j n)_{q}$ .

Hint

Count partitions $λ \subseteq k \times (m + n - k)$ , or equivalently $k$ -subsets in a q-weighted sense. Split a $k$ -element selection from an $(m + n)$ -set into $j$ from the first $m$ and $k - j$ from the last $n$ , tracking the area/inversion weight $q^{(k - j) (m - j)}$ created by the interleaving.

Answer

Use the lattice-path / box reading: $(k m + n)_{q}$ is the generating function $\sum q^{area}$ over monotone lattice paths from $(0, 0)$ to $(k, m + n - k)$ taking unit east/north steps, where the area is the number of cells below the path inside the bounding box (this area statistic is the partition $∣ λ ∣$ ). Cut the box by the vertical line after the column corresponding to the first $m$ of the $m + n$ steps. A path crosses this line at some height $k - j$ from the top, having taken $j$ of its $k$ "choose" (north) steps in the left block of width $m$ and $k - j$ in the right block of width $n$ . The left portion is a path counted by $(j m)_{q}$ (area $\subseteq j \times (m - j)$ ) and the right by $(k - j n)_{q}$ . The rectangle of the left block lying below the right portion's selected rows contributes the cross term: it is a $(k - j) \times (m - j)$ rectangle of full cells, weight $q^{(k - j) (m - j)}$ . Summing over the splitting index $j$ gives $(k m + n)_{q} = \sum_{j} q^{(k - j) (m - j)} (j m)_{q} (k - j n)_{q}$ . At $q = 1$ this is the ordinary Vandermonde $(k m + n) = \sum_{j} (j m) (k - j n)$ . Rubric: full credit for the path/area model, the split at width $m$ , the cross-rectangle weight $q^{(k - j) (m - j)}$ , and the $q = 1$ check.

Exercise 8 (hard, symbolic).

Prove that the number of $k$ -dimensional subspaces of $F_{q}^{n}$ ( $q$ a prime power) equals $(k n)_{q}$ , by counting ordered bases.

Hint

Count ordered linearly independent $k$ -tuples in $F_{q}^{n}$ two ways: directly, and as (number of subspaces) $\times$ (number of ordered bases of a fixed $k$ -space).

Answer

An ordered linearly independent $k$ -tuple $(v_{1}, \dots, v_{k})$ is built by choosing $v_{1} \neq = 0$ ( $q^{n} - 1$ ways), then $v_{2}$ outside $⟨ v_{1} ⟩$ ( $q^{n} - q$ ways), and in general $v_{i + 1}$ outside the $i$ -dimensional span $⟨ v_{1}, \dots, v_{i} ⟩$ ( $q^{n} - q^{i}$ ways). So the number of ordered independent $k$ -tuples is $\prod_{i = 0}^{k - 1} (q^{n} - q^{i})$ . The same count equals (number $N$ of $k$ -subspaces) times (number of ordered bases of one fixed $k$ -space), and the latter is $\prod_{i = 0}^{k - 1} (q^{k} - q^{i})$ by the identical argument inside a $k$ -dimensional space. Therefore $$ N = \frac{\prod_{i=0}^{k-1}(q^n - q^i)}{\prod_{i=0}^{k-1}(q^k - q^i)} = \prod_{i=0}^{k-1}\frac{q^n - q^i}{q^k - q^i} = \prod_{i=0}^{k-1}\frac{q^{n-i}-1}{q^{k-i}-1} = \frac{(q^n-1)\cdots(q^{n-k+1}-1)}{(q^k-1)\cdots(q-1)} = \binom{n}{k}_q, $$ after cancelling the common power $q^{i}$ from each factor and rewriting via $q^{a} - 1 = (1 - q^{a}) \cdot (- 1)$ , which cancels in the ratio to give the standard $(k n)_{q}$ . Rubric: full credit for the ordered-independent-tuple count $\prod (q^{n} - q^{i})$ , the division by ordered bases of a fixed space, and the simplification to $(k n)_{q}$ .

Advanced results Master

The elementary theory of the Gaussian binomial opens onto three deeper strata: its role as the rank-generating function of the subspace lattice, the q-series identities (q-binomial theorem, Jacobi triple product, Rogers-Ramanujan) it sits beneath, and the bijective combinatorics of partitions (Euler, Glaisher, Franklin) that the same Ferrers-diagram calculus controls.

Theorem 1 (subspace lattice and Sylvester unimodality). For $q$ a prime power, $(k n)_{q}$ counts the $k$ -dimensional subspaces of $F_{q}^{n}$ , so the Gaussian binomial is the rank-generating function of the lattice $L_{n} (q)$ of all subspaces of $F_{q}^{n}$ : $\sum_{k} (k n)_{q}$ counts all subspaces, and the rank level $k$ contributes $(k n)_{q}$ ^{[Stanley §1.7]}. The symmetry $(k n)_{q} = (n - k n)_{q}$ is the orthogonal-complement duality of $L_{n} (q)$ . Sylvester's theorem — that the coefficient sequence of $(k n)_{q}$ is symmetric and unimodal — acquires here its conceptual proof: there is an order-raising operator $U$ and order-lowering operator $D$ on $⨁_{k} C {k -subspaces}$ realizing an $sl_{2}$ -representation, and unimodality follows from the representation theory of $sl_{2}$ (the Lefschetz property), exactly as for the Boolean-lattice unimodality of ordinary binomials.

Theorem 2 (q-binomial theorem and the two q-exponentials). As an identity in $q$ and $x$ , $$ \prod_{i=0}^{n-1}(1 + q^{i}x) = \sum_{k=0}^{n} q^{\binom{k}{2}}\binom{n}{k}q x^{k}, \qquad \frac{1}{\prod{i=0}^{n-1}(1 - q^{i}x)} = \sum_{k \ge 0}\binom{n+k-1}{k}q x^{k}, $$ the second being the "negative" companion (weak compositions). Letting $n \to \infty$ with $∣ q ∣ < 1$ gives Euler's two q-exponential identities $\sum{k} \frac{q^{\binom{k}{2}}}{(q;q)k}x^k = (-x; q)\infty $an d$ \sum_k \frac{x^k}{(q;q)k} = \frac{1}{(x; q)\infty} $[r e f : T O D O_{R} E F A n d r e w s 1976] . T h ese a r e t h e q - ana l o g u eso f$ e^x $, an d t h ey a r e t h e g e n er a t in g - f u n c t i o n so u r ceo f E u l e r^{'} s d i s t in c t - v er s u s - o dd i d e n t i t y :$ (-x;q)\infty $(d i s t in c tp a r t s) v er s u s$ 1/(x;q)\infty$ at the appropriate specialization.

Theorem 3 (Jacobi triple product and pentagonal specialization). The Jacobi triple product $$ \prod_{m \ge 1}(1 - q^{2m})(1 + q^{2m-1}z)(1 + q^{2m-1}z^{-1}) = \sum_{k \in \mathbb{Z}} q^{k^2} z^{k} $$ is the parent identity; the specialization $z = - 1$ , $q \mapsto q^{3/2}$ yields Euler's pentagonal number theorem $\prod_{k \geq 1} (1 - q^{k}) = \sum_{k \in Z} (- 1)^{k} q^{k (3 k - 1) /2}$ , whose combinatorial proof by Franklin's involution and whose analytic life as the Dedekind eta function are developed at 21.16.01. Within the present unit the triple product is the limit $n \to \infty$ of finite Gaussian-binomial sums; the analytic asymptotics of $p (n)$ via the circle method are out of scope and owned by 21.16.01.

Theorem 4 (Rogers-Ramanujan, combinatorial form). The two Rogers-Ramanujan identities $$ \sum_{k \ge 0}\frac{q^{k^2}}{(q;q)k} = \prod{m \ge 0}\frac{1}{(1 - q^{5m+1})(1 - q^{5m+4})}, \quad \sum_{k \ge 0}\frac{q^{k^2 + k}}{(q;q)k} = \prod{m \ge 0}\frac{1}{(1 - q^{5m+2})(1 - q^{5m+3})} $$ equate, combinatorially, partitions whose parts differ by at least $2$ (the sum side, where $q^{k^{2}} / (q; q)_{k}$ is the generating function for partitions into $k$ parts with minimal differences $2$ ) with partitions into parts congruent to $\pm 1$ (resp. $\pm 2$ ) modulo $5$ (the product side). The factor $q^{k^{2}}$ is the Durfee-square / staircase contribution; the identities sit beyond Euler's elementary toolkit and connect to affine Lie algebras and the hard-hexagon model, as noted at 21.16.01.

Theorem 5 (Glaisher's bijection, structural form). Euler's theorem (partitions into distinct parts $=$ partitions into odd parts) is the case $d = 2$ of Glaisher's theorem: partitions of $n$ with no part divisible by $d$ are equinumerous with partitions of $n$ with no part repeated $d$ or more times, via the explicit bijection that writes each multiplicity in base $d$ and redistributes. At the generating-function level this is $\prod_{k \geq 1} (1 + q^{k} + \dots + q^{(d - 1) k}) = \prod_{d ∤ k} (1 - q^{k})^{- 1}$ ; the bijection makes the equality cell-by-cell, refining the GF proof of 21.16.01 into a concrete map on Ferrers diagrams.

Synthesis. Putting these together, the q-Pascal recurrence is the foundational reason the finite and the asymptotic theories of partitions are one subject: the Gaussian binomial $(k n)_{q}$ is at once a box-partition generating function, the rank-generating function of the subspace lattice $L_{n} (q)$ , and the finite truncation whose $n \to \infty$ limits are Euler's q-exponentials and, through the Jacobi triple product, the pentagonal and Rogers-Ramanujan identities. The central insight is that conjugation of Ferrers diagrams, the $sl_{2}$ -duality of the subspace lattice, and the symmetry $(k n)_{q} = (n - k n)_{q}$ are the same symmetry read three ways, and this is exactly why Sylvester unimodality, Franklin's involution, and Glaisher's redistribution are not separate tricks but instances of one diagram calculus. The box generating function generalises the ordinary binomial — $q = 1$ erases the area grading — and is dual to the subspace count under the substitution $q \mapsto$ prime power; the bridge is that the elementary identities proved here become, in the limit, the modular and Lie-theoretic structures of 21.16.01, so that this unit supplies the combinatorial bedrock on which the analytic partition theory and the finite-geometry incidence counts of 40.06.03 both stand. The Durfee-square decomposition is the hinge: it turns the unrestricted partition generating function into a sum of squared Gaussian-binomial limits, making the finite q-binomial the atom of the whole theory.

Full proof set Master

Proposition 1 (polynomiality and degree). For $0 \leq k \leq n$ , $(k n)_{q} \in Z_{\geq 0} [q]$ is a polynomial of degree $k (n - k)$ with constant term $1$ and leading coefficient $1$ .

Proof. By the Key theorem, $(k n)_{q} = \sum_{λ \subseteq k \times (n - k)} q^{∣ λ ∣}$ , a finite sum of monomials $q^{∣ λ ∣}$ with non-negative integer coefficients, hence a polynomial in $Z_{\geq 0} [q]$ . The empty partition gives the unique term of degree $0$ , so the constant term is $1$ ; the full $k \times (n - k)$ rectangle is the unique partition of maximal size $k (n - k)$ in the box, so the degree is $k (n - k)$ with leading coefficient $1$ . Non-negativity and integrality are automatic from the counting interpretation. $□$

Proposition 2 (q-binomial theorem). In $Z [q] [x]$ , $i = 0 \prod n - 1 (1 + q^{i} x) = k = 0 \sum n q^{(2 k)} (k n)_{q} x^{k}$ .

Proof. Induct on $n$ . For $n = 0$ both sides equal $1$ . Assume the identity for $n - 1$ and multiply both sides by $(1 + q^{n - 1} x)$ . The coefficient of $x^{k}$ in the product is $q^{(2 k)} (k n - 1)_{q} + q^{n - 1} q^{(2 k - 1)} (k - 1 n - 1)_{q}$ . Since $(2 k) - (2 k - 1) = k - 1$ , the second summand is $q^{(2 k)} q^{(n - 1) - (k - 1)} (k - 1 n - 1)_{q} = q^{(2 k)} q^{n - k} (k - 1 n - 1)_{q}$ . Factoring $q^{(2 k)}$ , the bracketed sum is $(k n - 1)_{q} + q^{n - k} (k - 1 n - 1)_{q}$ , which equals $(k n)_{q}$ by the second q-Pascal recurrence (Key theorem). Hence the coefficient of $x^{k}$ is $q^{(2 k)} (k n)_{q}$ , completing the induction. $□$

Proposition 3 (subspace enumeration). Let $q$ be a prime power. The number of $k$ -dimensional subspaces of $F_{q}^{n}$ is $(k n)_{q}$ .

Proof. The number of ordered linearly independent $k$ -tuples $(v_{1}, \dots, v_{k})$ in $F_{q}^{n}$ is $\prod_{i = 0}^{k - 1} (q^{n} - q^{i})$ : $v_{i + 1}$ must avoid the $q^{i}$ vectors of $⟨ v_{1}, \dots, v_{i} ⟩$ . Each ordered independent $k$ -tuple spans a unique $k$ -subspace $W$ , and a fixed $k$ -subspace $W ≅ F_{q}^{k}$ has $\prod_{i = 0}^{k - 1} (q^{k} - q^{i})$ ordered bases by the same count inside $W$ . Thus the number $N$ of $k$ -subspaces satisfies $N \cdot \prod_{i = 0}^{k - 1} (q^{k} - q^{i}) = \prod_{i = 0}^{k - 1} (q^{n} - q^{i})$ , so $$ N = \prod_{i=0}^{k-1}\frac{q^n - q^i}{q^k - q^i} = \prod_{i=0}^{k-1}\frac{q^{n-i} - 1}{q^{k-i}-1} = \frac{(q^n-1)(q^{n-1}-1)\cdots(q^{n-k+1}-1)}{(q^k - 1)(q^{k-1}-1)\cdots(q-1)} = \binom{n}{k}_q, $$ the middle equality cancelling the factor $q^{i}$ from numerator and denominator of each term, and the last equality being the definition of $(k n)_{q}$ rewritten with $1 - q^{a} = - (q^{a} - 1)$ (the $k$ sign factors cancel between numerator and denominator). $□$

Proposition 4 (Durfee-square identity). $n \geq 0 \sum p (n) q^{n} = k \geq 1 \prod (1 - q^{k})^{- 1} = d \geq 0 \sum \frac{q ^{d^{2}}}{( ( q ; q ) _{d} ) ^{2}} .$

Proof. Each partition $λ$ has a unique Durfee square of side $d = max {i : λ_{i} \geq i}$ , contributing the $d \times d$ block of size $d^{2}$ . Removing it leaves two independent partitions: the cells right of the square in rows $1, \dots, d$ form $μ$ with $\leq d$ parts, and the cells below in columns $1, \dots, d$ form $ν$ with all parts $\leq d$ . Partitions with at most $d$ parts have generating function $\prod_{j = 1}^{d} (1 - q^{j})^{- 1} = 1/ (q; q)_{d}$ (a part of size $j$ corresponds to incrementing one of $d$ rows), and partitions with parts $\leq d$ have the conjugate generating function, also $1/ (q; q)_{d}$ . The triple $(d, μ, ν)$ is in bijection with $λ$ via $∣ λ ∣ = d^{2} + ∣ μ ∣ + ∣ ν ∣$ , so $\sum_{λ} q^{∣ λ ∣} = \sum_{d \geq 0} q^{d^{2}} / ((q; q)_{d})^{2}$ . Equality with $\prod_{k} (1 - q^{k})^{- 1}$ is Euler's product (Proposition 1 of 21.16.01). $□$

Connections Master

The Gaussian binomial is the q-deformation of the ordinary binomial coefficient and the twelvefold-way counts of 40.01.01: setting $q = 1$ collapses every q-integer $[n]_{q}$ to $n$ and every $(k n)_{q}$ to $(k n)$ , so the entire q-Pascal triangle degenerates to ordinary Pascal. The box-partition reading refines the plain "choose $k$ " into a polynomial graded by diagram area, and the same refinement upgrades the inclusion-exclusion and surjection counts of 40.01.01 to their q-analogues.
The generating-function machinery this unit deploys — infinite products $(q; q)_{\infty}$ , the q-exponentials, and coefficient extraction from $\prod (1 + q^{i} x)$ — is exactly the ordinary/exponential generating-function calculus of 40.01.03 specialized to q-series, where the bookkeeping variable additionally tracks a size statistic. The q-binomial theorem is the q-lift of the binomial series, and Euler's two q-exponentials are the q-lifts of $e^{x}$ that 40.01.03 introduces in the $q \to 1$ classical limit.
The analytic and arithmetic theory of the partition function $p (n)$ — the pentagonal number theorem by Franklin's involution, the Jacobi triple product as parent identity, the Hardy-Ramanujan asymptotic, and the Ramanujan congruences — is owned by 21.16.01; this unit supplies the finite, bijective, q-binomial bedrock (Durfee squares, box partitions, Glaisher) on which that asymptotic theory rests, and cross-refs it for everything modular. The division of labour is exact: finite and combinatorial here, infinite and analytic there.
The subspace count $(k n)_{q}$ of $F_{q}^{n}$ is the entry point to finite projective and affine geometry: the lines and planes it enumerates are the points and flats of the projective space $PG (n - 1, q)$ , whose incidence structure underlies the symmetric designs and the perfect codes of 40.06.07 and the subspace-incidence counts developed at 40.06.03. The Gaussian binomial is thus the combinatorialist's bridge between partition theory and finite geometry. This material is co-produced with the q-series unit 40.01.05 and the poset/lattice-theoretic treatment of the subspace lattice in 40.03.02.

Historical & philosophical context Master

The Gaussian binomial coefficient is named for Gauss, who introduced the polynomials $(k n)_{q}$ around 1808 in his work on the determination of the sign of the quadratic Gauss sum ^{[Gauss 1808]}, where the identity $(k n)_{q} = (n - k n)_{q}$ and the q-Pascal recurrence appear as tools for manipulating sums of roots of unity. The q-binomial theorem in its general form is due to Cauchy (1843) ^{[Cauchy 1843]}, with closely related identities found independently by Heine in his development of the basic hypergeometric series $_{2} ϕ_{1}$ , the q-analogue of the Gauss hypergeometric function; Heine's q-Gauss summation is the q-Vandermonde of this unit.

The combinatorial reading of $(k n)_{q}$ as a partition generating function, and the systematic Ferrers-diagram calculus (conjugation, Durfee squares, Franklin's 1881 involution), were consolidated in the partition-theory tradition running from Sylvester's 1882 "constructive theory of partitions", where unimodality of the Gaussian coefficients was first asserted and attacked, through MacMahon's Combinatory Analysis (1915-16). The subspace interpretation over $F_{q}$ belongs to the finite-geometry and q-analogue tradition that treats $F_{q}^{n}$ as the " $q$ -deformation" of a finite set, with $q \to 1$ recovering set combinatorics — a viewpoint crystallized by Cohn and others under the slogan of the "field with one element". Sylvester's unimodality assertion was given its conceptual $sl_{2}$ -representation-theoretic proof only much later, by Proctor (1982), using the Lefschetz property of the order-raising operator on the subspace lattice.

Bibliography Master

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@book{andrews1976partitions,
  author    = {Andrews, George E.},
  title     = {The Theory of Partitions},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {2},
  publisher = {Addison-Wesley},
  year      = {1976}
}

@book{andrewseriksson2004,
  author    = {Andrews, George E. and Eriksson, Kimmo},
  title     = {Integer Partitions},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{kaccheung2002quantum,
  author    = {Kac, Victor and Cheung, Pokman},
  title     = {Quantum Calculus},
  series    = {Universitext},
  publisher = {Springer},
  year      = {2002}
}

@article{cauchy1843memoire,
  author  = {Cauchy, Augustin-Louis},
  title   = {M\'{e}moire sur les fonctions dont plusieurs valeurs sont li\'{e}es entre elles par une \'{e}quation lin\'{e}aire},
  journal = {Comptes Rendus de l'Acad\'{e}mie des Sciences (Paris)},
  volume  = {17},
  pages   = {523--531},
  year    = {1843}
}

@book{gauss1808summatio,
  author    = {Gauss, Carl Friedrich},
  title     = {Summatio quarumdam serierum singularium},
  publisher = {Commentationes Societatis Regiae Scientiarum Gottingensis},
  year      = {1808}
}

@article{sylvester1882constructive,
  author  = {Sylvester, James Joseph},
  title   = {A constructive theory of partitions, arranged in three acts, an interact and an exodion},
  journal = {American Journal of Mathematics},
  volume  = {5},
  pages   = {251--330},
  year    = {1882}
}

@article{proctor1982bruhat,
  author  = {Proctor, Robert A.},
  title   = {Solution of two difficult combinatorial problems with linear algebra},
  journal = {American Mathematical Monthly},
  volume  = {89},
  number  = {10},
  pages   = {721--734},
  year    = {1982}
}

Prerequisites

40.01.01
40.01.03

Tier anchors

beginner: Andrews-Eriksson 2004 *Integer Partitions* (Cambridge) Ch. 3, 6 (Ferrers diagrams, conjugation, partitions in a box and the q-binomial as their generating polynomial); Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.7 (the combinatorial reading of the Gaussian binomial)
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.7-1.8 (q-binomial coefficients, q-Pascal recurrences, the q-binomial theorem, partitions in a rectangle, subspaces of a finite vector space); Andrews 1976 *The Theory of Partitions* (Addison-Wesley) Ch. 1-3
master: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.7-1.8 and §3 (the q-binomial as a rank-generating function of the subspace lattice, q-Vandermonde, Durfee squares); Andrews 1976 *The Theory of Partitions* Ch. 2, 7 (Jacobi triple product, Rogers-Ramanujan); Andrews-Eriksson 2004 *Integer Partitions* Ch. 7-8 (Durfee squares, Franklin, Glaisher); Cauchy 1843 *Comptes Rendus* 17 (the q-binomial theorem); Gauss 1808 (the Gaussian binomial coefficient)

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 · Cambridge Studies in Advanced Mathematics 49, 2e (2012). §1.7 defines the q-integer $[n]_q = 1 + q + \cdots + q^{n-1}$, the q-factorial $[n]_q! = [1]_q[2]_q\cdots[n]_q$, and the Gaussian binomial coefficient $\binom{n}{k}_q = [n]_q!/([k]_q![n-k]_q!)$, proves it is a polynomial in $q$ of degree $k(n-k)$ with non-negative integer coefficients, and identifies it as the generating function $\sum_\lambda q^{|\lambda|}$ for partitions $\lambda$ fitting in a $k \times (n-k)$ box. The two q-Pascal recurrences $\binom{n}{k}_q = \binom{n-1}{k-1}_q + q^k\binom{n-1}{k}_q = q^{n-k}\binom{n-1}{k-1}_q + \binom{n-1}{k}_q$ are derived bijectively. §1.8 proves the q-binomial theorem $\prod_{i=0}^{n-1}(1 + q^i x) = \sum_k q^{\binom{k}{2}}\binom{n}{k}_q x^k$ and q-Vandermonde, and §1.7 gives the count $\binom{n}{k}_q$ of $k$-dimensional subspaces of $\mathbb{F}_q^n$ for $q$ a prime power.
Andrews, G. E. — The Theory of Partitions · Addison-Wesley, Encyclopedia of Mathematics and its Applications, Vol. 2 (1976; reissued Cambridge 1998). Chapters 1-3 develop Ferrers/Young diagrams, conjugation, the Gaussian polynomials and their generating-function role for partitions in a box, the q-binomial theorem (Cauchy), the q-analogue of Vandermonde, Euler's distinct-equals-odd theorem and Glaisher's bijection, Franklin's involution and the pentagonal number theorem, Durfee squares and the identity $\sum_n p(n)q^n = \sum_{k\ge0} q^{k^2}/((q;q)_k)^2$, the Jacobi triple product, and (Ch. 7) the Rogers-Ramanujan identities.
Andrews, G. E. & Eriksson, K. — Integer Partitions · Cambridge University Press (2004). An elementary, bijection-first account: Ferrers diagrams and conjugation (Ch. 3), the Gaussian binomial coefficient as the generating polynomial for partitions in a rectangle and the q-Pascal triangle (Ch. 6), Durfee squares and the rank (Ch. 7), Euler's theorem, Glaisher's bijection, and Franklin's involution (Ch. 8), with the Rogers-Ramanujan identities stated combinatorially as the closing chapters.
Kac, V. & Cheung, P. — Quantum Calculus · Springer Universitext (2002). Chapters 1-7 give the q-analogue dictionary at textbook level: the q-integer $[n]_q$, q-derivative and q-antiderivative, the Gauss binomial formula $(x + y)^n = \sum_k \binom{n}{k}_q q^{\binom{k}{2}} x^k y^{n-k}$ in the q-commuting setting $yx = qxy$, the q-binomial theorem, Heine's q-Gauss summation (a q-Vandermonde), and the Jacobi triple product, situating the Gaussian binomial inside the broader q-calculus.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m