= Lattice-path interpretation of Gaussian binomial coefficients
{title2=$G_{n,k}(t)=\sum_P t^{A(P)}$}
Use <lattice paths> with $k$ north steps and $n-k$ east steps, beginning at $(0,0)$. Let $A(P)$ be the <sum> of the horizontal coordinates of its north steps, equivalently the number of unit cells to their left inside the $k$-by-$(n-k)$ <rectangle>. A north step in zero-based word position $j_i$ has $i-1$ earlier north steps, so its horizontal coordinate is $j_i-(i-1)$. The <Gaussian binomial coefficient recurrence> therefore counts these <lattice paths> with weight $t^{A(P)}$.
For $n=4,k=2$, the words `NNEE`, `NENE`, `NEEN`, `ENNE`, `ENEN`, `EENN` have respective <areas> $0,1,2,2,3,4$. The word `NEEN` contributes $t^2$ because the two north steps occur at horizontal coordinates zero and two. These paths never move south or west; allowing such extra steps would change the collection being counted.
Back to article page
