q-binomial coefficients are generating functions for size of bounded young diagrams

Statement

{[\binom{n}{k}]}_{q} = \sum_{λ \subseteq k \times (n - k)} q^{| λ |}

where the left is q-binomial coefficient, $λ$ is a Young diagram fitting inside the $k \times (n - k)$ rectangle
Pasted image 20260307174751.png|400

as a corollary, generating function for size of young diagrams

(Note these can be viewed as a lattice path from $(0, 0) \to (k, n - k)$ )
Pasted image 20260307174627.png|400

Proof 1 (recurrence relation)

We show that the RHS satisfies the $q$ -Pascal recurrence relation. In other words, that

\sum_{λ \subseteq k \times (n - k)} q^{| λ |} = \sum_{λ \subseteq (k - 1) \times (n - k)} q^{| λ |} + q^{k} \sum_{λ \subseteq k \times (n - 1 - k)} q^{| λ |}

Let $λ \subseteq k \times (n - k)$ . Then, consider the following cases:

$λ_{k} = 0$ . This means the last row of the rectangle is empty. Then, $λ \subseteq (k - 1) \times (n - k)$
$λ_{k} \neq 0$ . This means in particular that every row has an element, so the first row is filled. We may remove the first column and so this new permutation fits in $k \times (n - k - 1)$ . By doing so, we remove $k$ boxes, so we add it back by multiplying $q^{k}$ .

Proof 2 (counting number of k-dim subspaces of n-dim space over F_q)

Recall:

if two rational functions are equal at infinitely many points, then they are equal.
for all $q = p^{r}$ , there exists a finite field of cardinality $q$ .

We shall prove this by showing that this is equal to $# Gr (k, n, F_{q})$ , the grassmannian (in our case, this is just the number of dimension $k$ linear subspaces of the vector space $F_{q}^{n}$ over $F_{q}$ . As these are finite fields, note that this would be a finite quantity). Then, we shall show that by counting another way, this is equal to the RHS.

Let $V$ be a $k$ -dimensional subspace of $F_{q}^{n}$ . It can be represented as the rowspace of a $k \times n$ matrix, $A$ . In particular, it is comprised of $k$ linearly independent $n$ -dimensional vectors $v_{1}, \dots, v_{k}$ . Let us see how many choices we have for each:

$v_{1}$ can be anything but the zero vector, so $q^{n} - 1$
$v_{2}$ can be anything not in the span of $v_{1}$ , so $q^{n} - q$
$v_{3}$ can be anything not in the span of the above two vectors, so $q^{n} - q^{2}$
and so on until $q^{n} - q^{k - 1}$
So there are $(q^{n} - 1) (q^{n} - q) \dots (q^{n} - q^{k - 1})$ possible choices for these vectors.

But different choices of vectors can yield the same rowspace, so we have to mod out by these. Rowspace is preserved under row operations, which corresponds to multiplying on the left by an invertible $k \times k$ matrix. We may use the same formula as we did above to get $(q^{k} - 1) (q^{k} - q) \dots (q^{k} - q^{k - 1})$ .

Taking the quotient, we note that

\frac{(q^{n} - 1) (q^{n} - q) \dots (q^{n} - q^{k - 1})}{(q^{k} - 1) (q^{k} - q) \dots (q^{k} - q^{k - 1})} = {[\binom{n}{k}]}_{q}

On the other hand, we can apply Gaussian elimination on $A$ to get it into RREF, which is unique. So, it suffices to show that there is a bijection between full rank $k \times n$ RREFs matrices and Young diagrams in $k \times (n - k)$ rectangle.

Note that in order for $A$ to be full rank, we require $k$ pivot columns. For everything to the left and in the same column as these pivots, there are zeros. Let us remove these columns, yielding a $k \times (n - k)$ matrix. Take the elements in this new matrix that used to be to the right of some pivot, and make that a box. Then, this is a Young diagram that starts on the right contained within this box.

On the other hand, given a Young diagram, we may right align it within a box and for each row, add a column to the left of it with 1 at the row. Then, within each box, we may fill it with any element of $q$ , thus giving us $q^{| λ |}$ . Thus, the total number of these subspaces is the sum over all shapes of this.

Pasted image 20260307174943.png