The recursive identity for building Pascal's triangle is

$$ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. \tag{$\circ$}$$

This has a simple combinatorial interpretation: every $k$-subset of $\{1,\cdots,n\}$ is either a $k$-subset of $\{1,\cdots,n-1\}$ or it's a $(k-1)$-subset of $\{1,\cdots,n-1\}$ with $\{n\}$ adjoined.

From Wikipedia there are two analogous identities for $q$-binomials:

$$ \left[\begin{array}{c} n \\ k \end{array}\right]_q = q^k\left[\begin{array}{c} n-1 \\ k \end{array}\right]_q + \left[\begin{array}{c} n-1 \\ k-1 \end{array}\right]_q, \tag{I}$$

$$ \left[\begin{array}{c} n \\ k \end{array}\right]_q=\left[\begin{array}{c} n-1 \\ k \end{array}\right]_q + q^{n-k} \left[\begin{array}{l} n-1 \\ k-1 \end{array}\right]_q. \tag{II}$$

(We interpret the $q$-binomial as the number of $k$-dimensional subspaces of $\mathbb{F}_q^n$.)

The first identity $(\mathrm{I})$ has a $\mathbb{F}_q$-interpretation as follows: we have two cases,

  1. The subspace $V$'s projection into $\mathbb{F}_q^{n-1}$ is still $k$-dimensional, in which case it is determined by its image $W$ under the projection and the corresponding section $W\to V$, and that section is the sum of the identity map on $W$ and an arbitrary linear map $W\to\mathbb{F}_qe_n$.

  2. The subspace $V$ is a direct sum of a $(k-1)$-dim subspace of $\mathbb{F}_q^{n-1}$ and $\mathbb{F}_qe_n$.

However I can't figure out a $\mathbb{F}_q$-interpretation of the second identity $(\mathrm{II})$. What is it? Surely I'm missing something obvious. Presumably it involves taking a complementary subspace to a $k$-dim subspace and then using another linear map from/to it.

  • 2
    $\begingroup$ Well, if you can argue that $\left[\begin{array}{c} n \\ k \end{array}\right]_q = \left[\begin{array}{c} n \\ n-k \end{array}\right]_q$ (which is true), then (II) follows easily from (I). $\endgroup$ – Jon Noel Sep 22 '17 at 22:25

Found a way. For subspaces $V$ of $\mathbb{F}_q^n$ there are two cases:

  1. $V$ is a subspace of $\mathbb{F}_q^{n-1}$
  2. Otherwise, $V$ is determined by picking a $(k-1)$-dim subspace $K$ of $\mathbb{F}_q^{n-1}$ to be the kernel of the projection $\pi:\mathbb{F}_q^n\to\mathbb{F}_q$ onto the $n$th coordinate, then picking any element $\alpha$ of the quotient space $\mathbb{F}_q^{n-1}/K$ to determine the fiber $\pi^{-1}(1)=\alpha$.

Edit: I generalized this argument in this answer to prove the $q$-analog of Chu-Vandermonde convolution. This yields both versions of Pascal's rule as a special case (as the convolution $q$-identity is "asymmetric," we can apply it for $(n-1)+1$ and $1+(n-1)$ to get the two versions of the rule).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.