Combinatorial proof of the identity ${{n}\brack {m}}_{q}{{m}\brack {k}}_{q} = {{n}\brack {k}}_{q}{{n-k}\brack {m-k}}_{q}$

Question

Problem

Let $$ [n]_q = \sum_{0 \leq k < n} q^k = \frac{1-q^n}{1-q} $$

and $$[n]_q! = \prod_{0 \leq m < n} \sum_{0 \leq k < m} q^k. $$

Define $$ {{n}\brack{k}}_q = \frac{[n]_q!}{[k]_q![n-k]_q!}. $$

Prove the trinomial revision identity

$$ {{n}\brack {m}}_{q}{{m}\brack {k}}_{q} = {{n}\brack {k}}_{q}{{n-k}\brack {m-k}}_{q}, \, n \geq m \geq k \geq 0. $$

My question

One of the combinatorial meaning for ${{n}\brack{k}}_q$ is given as follows.

Consider the lattice paths $p$ from $(0,0)$ to $(k,n-k)$ that takes only steps East and North. Then ${{n}\brack{k}}_q$ counts all such paths according to the area underneath such paths.

So, is there any combinatorial proof of trinomial revision identity using lattice paths?

Answer 1

It might be better to use another interpretation of ${n \brack k}_q$. Consider the set of strings of length $n$ over a totally ordered alphabet $A$. For any such string $w\in A^n$, let an inversion of $w$ be a pair of positions $(i,j)$ such that $i<j$ and $w_i>w_j$. Also, let $\mathrm{inv}(w)$ be the number of inversions of $w$. When the alphabet $A=\{0,1\}$, we get $${n\brack k}_q=\sum_{\substack{w\in\{0,1\}^n}\\ |w|_0=k}q^{\mathrm{inv}(w)},$$ where $|w|_0$ is the number of $0$’s in $w$. It's easy to construct a bijection from these strings to the lattice paths you described above by labeling each horizontal step with a $0$ and each vertical step with a $1$ (then each inversion $\dots1\dots0\dots$ corresponds to a unit square under the path).

To prove this trinomial identity, we simply need to consider strings $w$ over an alphabet $A=\{0,1,2\}$ with $k$ $0$'s, $m-k$ $1$'s, and $n-m$ $2$'s. Let $w_{01}$ be the substring of $0$'s and $1$'s of $w$ in order, and let $w_{12}$ be the substring of $1$'s and $2$'s of $w$ in order. Then we can break down the inversions of $w$ in $2$ ways to get the two sides of the trinomial identity:

• LHS:

  • the inversions between the $2$'s of $w$ and the elements of $w_{01}$, and
  • the inversions within $w_{01}$; and,

• RHS:

  • the inversions between the $0$'s of $w$ and the elements of $w_{12}$, and
  • the inversions within $w_{12}$.

Considering the first subset of inversions in each of the two cases is equivalent to relabeling all elements of $w_{12}$ as $1$'s and all elements of $w_{01}$ as $0$'s (and subsequently relabeling the $2$'s as $1$'s). Conversely, given a pair of binary strings $(u_1,u_2)$ of length $n$ that we would get from these relabelings (i.e. such that $u_1(i)\ge u_2(i)$ for all $i=1,\dots,n$), we can reconstruct the original ternary string by adding the two strings elementwise. You can translate this into facts about lattice paths, but inversions are a lot more convenient to use here.

Answer 2

This is not using lattice paths, but in my opinion the best combinatorial interpretation of ${n \brack k}_q$ is the number of $k$-dimensional subspaces of an $n$-dimensional vector space over the finite field $\mathbb{F}_q$. (Note the analog: The ordinary binomial coefficient $n \choose k$ is the number of $k$-element subsets of an $n$-element set.)

Now, many proofs for binomial coefficient can be translated to the Gauss coefficients. In this case, you get this: Let $N$ be an $n$-dimensional vector space over $\mathbb{F}_q$. Now count the set of all pairs $(M,K)$ with $M,K$ subspaces of $N$, $\dim(M) = m$, $\dim(K) = k$ and $K \subseteq M$ in two ways.