= Gaussian binomial coefficient recurrence
{c}
{title2=$G_{n,k}(t)=G_{n-1,k}(t)+t^{n-k}G_{n-1,k-1}(t)$}
For $n\geq1$ and $1\leq k\leq n$, the displayed <recurrence relation> uses $G_{n,0}(t)=1$ and $G_{n,k}(t)=0$ when $k<0$ or $k>n$. At $t=1$ it becomes <Pascal's identity>.
An exact weighted-<subset> formula is
$$
G_{n,k}(t)=\sum_{0\leq j_1<\cdots<j_k<n}t^{\sum_{i=1}^k(j_i-(i-1))}.
$$
The <exponent> measures how far the selected positions lie beyond the earliest possible choices $0,\ldots,k-1$. Split the <subsets> according to whether they contain $n-1$. Those without it give $G_{n-1,k}(t)$; deleting it from those with it removes exactly $n-k$ from their <exponent>. This gives the displayed <recurrence relation>, explaining why it builds <polynomials> with nonnegative <integer> <coefficients>.
Back to article page
