# Gaussian binomial coefficients, lattice paths, and vector spaces

The Gaussian binomial coefficient $${n+k \choose k}_q$$ gives a probability generating function for the number of lattice paths from $$(0,0)$$ to $$(n,k)$$ enclosing an area $$a$$ in the upper-right quadrant i.e. this count is given by the coefficient of $$q^a$$ in the corresponding series expansion of $${n+k \choose k}_q$$.

For example, the number of lattice paths in the $$10 \times 10$$ box between the bottom left and top right corners is $${20 \choose 10}$$, and those which enclose an area of 8 is the coefficient of $$q^8$$ in the corresponding series $${20 \choose 10}_q = 1 + q + 2 q^2 + 3 q^3 + 5 q^4 + \dots +2 q^{98} + q^{99} + q^{100}$$ which happens to be 22.

The Gaussian coefficient $${n+k \choose k}_q$$ also counts the number of $$k$$-dimensional vector subspaces of an $$n+k$$-dimensional vector space over $$F_q$$.

What is the relation here? Is the vector space interpretation also somehow a generalisation of the notion of partitioning something under a set of constraints (here, into $$k$$ parts no larger than $$n$$)?

What, for example, does the lattice path generating function 'mean' when we set $$q \neq 1$$?

• It's just a generating function, not a probability generating function.
– anon
Mar 9, 2020 at 0:04

1. $$k$$-dimensional subspaces of $$F_q^n$$.
2. Monotone paths in an $$(n-k)\times k$$ box, where the cells above the path are each labeled with an element of $$F_q$$. [I hope it is apparent that these are counted by $$\binom{n}k_q$$.]
Every $$k$$-dimensional subspace of $$F_q^n$$ is the kernel of an $$n\times n$$ matrix with entries in $$F_q$$. Two matrices represent the same subspace iff they have the same reduced row echelon form (rref for short). Therefore, instead of counting subspaces, we may count rref matrices with exactly $$n-k$$ leading ones.
In an rref matrix of rank $$n-k$$, the leading ones will occur in the first $$n-k$$ rows. In each row, the entries to the right of each leading one, and not above any other leading one, are arbitrary elements of $$F_q$$. For example, when $$n=5$$ and $$k=2$$, an example for how the matrix might look is $$\begin{bmatrix} 1&*&0&0&* \\ 0&0&1&0&* \\ 0&0&0&1&* \\ 0&0&0&0&0 \\ 0&0&0&0&0 \end{bmatrix}$$ The $$*$$'s represent arbitrary elements of $$F_q$$. If we ignore the bottom $$k$$ rows of the matrix (which are always zero), and ignore all columns containing leading ones, the result is $$\begin{bmatrix} *&*\\ 0&*\\ 0&* \end{bmatrix}$$ Note that the boundary between the $$0$$'s and $$*$$'s is exactly a path in an $$(n-k)\times k$$ box where the cells above are labeled with entries of $$F_q$$. This is the bijection! I leave it to you to find the reverse map; basically, given a path with the cells above labeled with elements of $$F_q$$, you add a $$1$$ before each row of labels with a column of zeroes beneath.
Another example; when $$n=2$$ and $$k=1$$, a one dimensional subspace of $$F_q^2$$ is either the kernel of $$\begin{bmatrix} 1&*\\ 0&0 \end{bmatrix}\qquad \text{or}\qquad \begin{bmatrix} 0&1\\ 0&0 \end{bmatrix}$$ There are $$q$$ matrices in the form on the left, and $$1$$ matrix in the form on the right, for $$1+q$$ matrices, which is indeed $$\binom{2}1_q$$. The left matrix corresponds to the path in a $$1\times 1$$ box with an area of $$1$$, and the right corresponds to the path with an area of zero.