5
$\begingroup$

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$?

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

1 Answer 1

5
$\begingroup$

I will illustrate a bijection from

  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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .