Symmetry 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 = \dbinom n {n - k}_q$
where $\dbinom n k_q$ is a Gaussian binomial coefficient.
Proof
If $k < 0$ then $n - k > n$.
Similarly, if $k > n$, then $n - k < 0$.
In both cases:
- $\dbinom n k_q = \dbinom n {n - k}_q = 0$
Let $0 \le k \le n$.
Consider the case $k \le \dfrac n 2$.
Then $k \le n - k$.
\(\ds \binom n {n - k}_q\) | \(=\) | \(\ds \prod_{j \mathop = 0}^{\paren {n - k} - 1} \frac {1 - q^{n - j} } {1 - q^{j + 1} }\) | Definition of Gaussian Binomial Coefficient | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {1 - q^{n - 0} } {1 - q^{0 + 1} } } \paren {\frac {1 - q^{n - 1} } {1 - q^{1 + 1} } } \paren {\frac {1 - q^{n - 2} } {1 - q^{2 + 1} } } \cdots \paren {\frac {1 - q^{n - \paren {\paren {n - k} - 1} } } {1 - q^{\paren {\paren {n - k} - 1} + 1} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {1 - q^{n - 0} } {1 - q^{0 + 1} } } \paren {\frac {1 - q^{n - 1} } {1 - q^{1 + 1} } } \paren {\frac {1 - q^{n - 2} } {1 - q^{2 + 1} } } \cdots \paren {\frac {1 - q^{n - \paren {k - 1} } } {1 - q^{\paren {k - 1} + 1} } } \paren {\frac {1 - q^{n - k} } {1 - q^{k + 1} } } \cdots \paren {\frac {1 - q^{k + 1} } {1 - q^{n - k} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\frac {1 - q^{n - 0} } {1 - q^{0 + 1} } } \paren {\frac {1 - q^{n - 1} } {1 - q^{1 + 1} } } \paren {\frac {1 - q^{n - 2} } {1 - q^{2 + 1} } } \cdots \paren {\frac {1 - q^{n - \paren {k - 1} } } {1 - q^{\paren {k - 1} + 1} } }\) | The tail cancels out | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom n k_q\) | Definition of Gaussian Binomial Coefficient |
The case $k \ge \dfrac n 2$ can be done by observing:
- $n - k \le \dfrac n 2$
and hence by the above:
- $\dbinom n k_q = \dbinom n {n - \paren {n - k} }_q = \dbinom n {n - k}_q$
$\blacksquare$
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$