# Reflection Rule for Gaussian Binomial Coefficients

Jump to navigation
Jump to search

## Theorem

Let $q \in \R_{\ne 1}, n \in \Z_{>0}, k \in \Z$.

Then:

- $\dbinom n k_q = q^{k \paren {n - k} } \dbinom n k_{q^{-1} }$

where $\dbinom n k_q$ is a Gaussian binomial coefficient.

## Proof

\(\displaystyle \dbinom n k_{q^{-1} }\) | \(=\) | \(\displaystyle \prod_{j \mathop = 0}^{k - 1} \dfrac {1 - \paren {q^{-1} }^{n - j} } {1 - \paren {q^{-1} }^{j + 1} }\) | Definition of Gaussian Binomial Coefficient | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \prod_{j \mathop = 0}^{k - 1} \dfrac {\frac {q^{n - j} - 1} {q^{n - j} } } {\frac {q^{j + 1} - 1} {q^{j + 1} } }\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \prod_{j \mathop = 0}^{k - 1} \dfrac {q^{j + 1} } {q^{n - j} } \dfrac {q^{n - j} - 1} {q^{j + 1} - 1}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \prod_{j \mathop = 0}^{k - 1} q^{1 - n} \dfrac {1 - q^{n - j} } {1 - q^{j + 1} }\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \paren {q^{1 - n} }^k \prod_{j \mathop = 0}^{k - 1} \dfrac {1 - q^{n - j} } {1 - q^{j + 1} }\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \dfrac 1 {q^{k \paren {n - 1} } } \dbinom n k_q\) | Definition of Gaussian Binomial Coefficient |

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $58$