Mathematics compares the most diverse phenomena and discovers the secret analogies that unite them.
— Joseph Fourier
The only moral it is possible to draw from this story is that one should never throw the Q letter into a privet bush, but unfortunately there are times when it is unavoidable.
— Douglas Adams (Life, the Universe, and Everything)
In previous chapters we have seen how to prove identities by interpreting them using combinatorial objects. In this section we generalize combinatorial proofs from identities involving constants to identities involving polynomials. In fact, we can derive $q$-analogues (by convention our polynomials use the variable $q$) of classical identities by replicating our combinatorial proofs while tracking additional parameters.
We begin our discussion by deriving a $q$-analogue of the factorial, along with a combinatorial interpretation of this analogue. Because $n!$ counts the number of permutations of size $n,$ our interpretation of the $q$-factorial will come from refining partitions using a natural parameter.
Let $\pi = \pi_1 \cdots \pi_n$ be a permutation of $[n] = \{1,\dots,n\}.$ An inversion in $\pi$ is a pair $(i,j)$ with $1 \leq i < j \leq n$ such that $\pi_i > \pi_j.$ We denote the number of inversions in $\pi$ by $\text{inv}(\pi).$
In other words, an inversion is a pair of elements that, reading left-to-right, has a bigger number before a smaller number. Note that an entry in a permutation can be in multiple inversions.
Example: The permutation $\pi = 1\,2\,3$ has no inversions. The permutation $\pi = 1\,3\,2$ has a single inversion as the $2$ and $3$ appear out of order when read left-to-right. The permutation $\pi = 3\,2\,1$ contains three inversions from the pairs $32, 31,$ and $21.$
If $k \in \mathbb{N}$ then we define
$$[k]_q = 1 + q + \cdots + q^{k-1}$$
with $[0]_q = 1.$ The $q$-factorial of $n \in \mathbb{N}$ is
$$ [n]!_q = [n]_q \cdot [n-1]_q \cdots [0]_q.$$
Remark: If $k$ is a positive integer then setting $q=1$ in $[k]_q$ recovers $k$ and setting $q=1$ in $[n]!_q$ recovers $n!.$
Remark: The factorization $1-q^k = (1-q)(1+q+\cdots+q^{k-1})$ implies that
$$ [k]_q = \frac{1-q^k}{1-q} $$
for positive integers $k.$
One of the main reasons to use this generalization of the factorial is a combinatorial interpretation of the $q$-factorial using inversions.
$q$-Factorial Theorem: If $S_n$ is the set of permutations of size $n$ then
$$ \sum_{\pi \in S_n} q^{\text{inv}(\pi)} = [n]!_q. $$
Proof of the $q$-Factorial Theorem
We give a bijective proof that there are $n!$ permutations of size $n,$ with the bijection constructed so that the number of inversions in a permutation behaves nicely under the map. The result holds trivially when $n=0,$ so we assume that $n$ is a positive integer. Define the product of sets
$$ P_n = [n] \times [n-1] \times \cdots [1] $$
where as usual $[k] = \{1,\dots,k\}$ so $|P_n| = n!.$
Let $I:S_n \rightarrow P_n$ be the map that takes a permutation $\pi = \pi_1\,\cdots\,\pi_n$ and returns the tuple $(1+r_1,\dots,1+r_n)$ where for each $1 \leq i \leq n,$
$$
\begin{aligned}
r_i &= \text{number of indices $j$ with $i< j \leq n$ and $\pi_i>\pi_j$} \\[+2mm]
&= \text{number of inversions starting at position $i.$}
\end{aligned}
$$
The map $I$ is well-defined because there are only $n-k$ elements in $\pi$ after position $k,$ and thus at most $n-k$ inversions starting at position $k.$
Example: The permutation $\pi = 4\,3\,5\,1\,2$ has $3$ inversions starting at the first position, $2$ inversions starting at the second and third positions, and $0$ inversions starting at the fourth and fifth positions, so the image of $\pi$ under $I$ is $(4,3,3,1,1).$
Conversely, let $J:P_n \rightarrow S_n$ be the map that takes a tuple $(s_1,\dots,s_n) \in P_n$ and returns the permutation $\pi = \pi_1\,\cdots\,\pi_n$ built inductively by setting $\pi_1$ to the $s_1$th smallest element of $[n]$ and
$$\pi_i = \text{$s_i$th smallest element of $[n] \setminus \{\pi_1,\dots,\pi_{i-1}\}$}$$
for all $2 \leq i \leq n.$ The map $J$ is well-defined since $(s_1,\dots,s_n) \in P_n$ implies $1 \leq s_k \leq n-k+1$ so the set $[n]\setminus\{\pi_1,\dots,\pi_{k-1}\}$ has at least $s_k$ elements for all $k.$
Example: The image $\pi$ of $(4,3,3,1,1)$ under $J$ has $\pi_1=4,$ while
$$
\begin{aligned}
\pi_2 &= \text{$3$rd smallest unassigned element of } \{1,2,3,{\color{red}4},5\}=3 \\
\pi_3 &= \text{$3$rd smallest unassigned element of } \{1,2,{\color{red}3},{\color{red}4},5\}=5 \\
\pi_4 &= \text{$1$st smallest unassigned element of } \{1,2,{\color{red}3},{\color{red}4},{\color{red}5}\}=1 \\
\pi_5 &= \text{$1$st smallest unassigned element of } \{{\color{red}1},2,{\color{red}3},{\color{red}4},{\color{red}5}\}=2
\end{aligned}
$$
so $J(4,3,3,1,1) = 4\,3\,5\,1\,2.$
Exercise: Prove that $I$ and $J$ are inverse functions, and thus bijections.
Since $I$ and $J$ are inverses, if
$ \pi = J(s_1,\dots,s_n)$
then
$I(\pi) = (s_1,\dots,s_n),$
so $s_i-1$ is the number of inversions starting at position $i$ and
$$\text{inv}(J(s_1,\dots,s_n)) = (s_1-1) + \cdots + (s_n-1).$$
Thus, the fact that $J$ is a bijection implies
$$
\begin{aligned}
\sum_{\pi \in S_n} q^{\text{inv}(\pi)}
&=\sum_{(s_1,\dots,s_n) \in P_n} q^{\text{inv}(J(s_1,\dots,s_n))} \\[+3mm]
&=\sum_{(s_1,\dots,s_n) \in P_n} q^{(s_1-1) + \cdots + (s_n-1)} \\[+3mm]
&=\left(\sum_{s_1 \in [n]} q^{s_1-1}\right)\left(\sum_{s_{2} \in [n-1]} q^{s_2-1}\right)\cdots\left(\sum_{s_n \in [1]} q^{s_n-1}\right) \\[+5mm]
&= [n]!_q
\end{aligned}
$$
as claimed.
Remark: Our proof of the $q$-Factorial Theorem uses the fact that if $f:A\rightarrow B$ is a bijection between finite sets $A$ and $B$ and $p$ is a function on $A$ then
$$ \sum_{\alpha \in A} p(\alpha) = \sum_{\beta \in B} q(\beta),$$
where $q(\beta)=p(\alpha)$ for the unique value $\alpha\in A$ with $f(\alpha)=\beta.$ This observation will be key to most of the $q$-analogues we derive.
Having defined $q$-factorials above, for any $n,k \in \mathbb{N}$ with $0 \leq k \leq n$ we define the $q$-binomial coefficient
$$ \left[ n \atop k \right]_q = \frac{[n]!_q}{[k]!_q\; [n-k]!_q}.$$
The $q$-binomial coefficients are also called Gaussian coefficients or Gaussian polynomials in some sources. It is not immediately obvious from this definition that the $q$-binomial coefficients are always polynomials: there are many proofs of this fact, and it follows immediately from the $q$-binomial theorem discussed below.
Exercise: Prove that for all $m\in\mathbb{N}$ and $0 \leq \mu \leq m,$
$$ \left[ m \atop \mu \right]_q = \prod_{i=0}^{\mu-1} \left(\frac{1-q^{m-i}}{1-q^{i+1}}\right).$$
Example: The $q$-binomial coefficient can be computed by hand for small values, such as
$$
\begin{aligned}
\left[ 4 \atop 2 \right]_q &= \frac{(1+q)(1+q+q^2)(1+q+q^2+q^3)}{(1+q)(1+q)} \\[+5mm]
&= (1+q+q^2)(1+q^2) \\[+3mm]
&= q^4+q^3+2q^2+q+1.
\end{aligned}
$$
Larger values can easily be determined with a computer algebra system. For instance, running
from sage.combinat.q_analogues import q_binomial
q_binomial(10,5)
in Sage returns the $q$-binomial coefficient $\left[ 10 \atop 5 \right]_q$ as a degree 25 polynomial,
The regular binomial coefficient $\binom{n}{k}$ counts the number of subsets of $[n]=\{1,\dots,n\}$ of size $k,$ so we introduce a parameter on subsets to obtain an enumeration problem where the $q$-binomial coefficients appear.
If $S=\{s_1,\dots,s_k\}$ is a subset of $[n]$ then the sum of $S$ is
$$\text{sum}(S) = s_1 + \cdots + s_k.$$
Just as we used inversions to give a combinatorial interpretation for the $q$-factorial, we can use subset sum to give a combinatorial interpretation for the $q$-binomial coefficients.
$q$-Binomial Theorem: For any $n\in\mathbb{N},$
$$
\prod_{k=1}^n \left(1+q^kz\right)
= \sum_{S \subset [n]}q^{\text{sum}(S)}z^{|S|}
= \sum_{k=0}^n q^{\frac{k(k+1)}{2}} \left[ n \atop k \right]_q z^k. $$
The $q$-Binomial Theorem implies that (up to a monomial) the coefficients of the $q$-binomial $\left[ n \atop k \right]_q$ enumerate the subsets of $[n]$ with size $k$ by their sum.
Remark: Setting $q=1$ in the $q$-Binomial Theorem recovers the classic binomial theorem
$$ (1+z)^n = \sum_{k=0}^n \binom{n}{k} z^k. $$
Figure:
The earliest known published statement of the $q$-Binomial Theorem in the introduction to the 1811 second volume of Rothe’s textbook Handbuch der reinen Mathematik. Systematisches Lehrbuch der Arithmetik, where Rothe describes material his publisher forced him to cut due to space limitations. A full treatment and proof of the $q$-binomial theorem was published soon after in Grunson’s 1818 article Neuer analytischen Lehrsatz.
We split our proof of the $q$-Binomial Theorem into two parts.
Fix a natural number $n$ and let $\mathcal{B}_n$ be the class of subsets of $[n]$ enumerated by size and sum. A subset $S$ of $[n]$ is uniquely determined by the tuple $(\omega_1,\dots,\omega_n)$ where $\omega_i = 1$ if $i \in S$ and $\omega_i=0$ otherwise, so we have the specification
$$\mathcal{B}_n = \left(\epsilon + \mathcal{Z}_1\right) \times \cdots \times \left(\epsilon + \mathcal{Z}_n\right)$$
where $\mathcal{Z}_i$ is an atom marking that $i \in S.$ Since any value $i \in S$ adds $i$ to the parameter $\text{sum}(S)$ we have the parameterized specification
$$\mathcal{B}_n = \left(\epsilon + \mu \times \mathcal{Z}_1\right) \times \left(\epsilon + \mu^2 \times \mathcal{Z}_2\right) \times \cdots \times \left(\epsilon + \mu^n \times\mathcal{Z}_n\right),$$
giving the claimed bivariate generating function
$$
B_n(u,z) = \sum_{S \subset [n]}u^{\text{sum}(S)}z^{|S|}
= (1+uz)(1+u^2z)\cdots(1+u^nz)
$$
after setting $u=q.$
For any $n \in \mathbb{N}$ and $0 \leq k \leq n$ let $\mathcal{B}_n(k)$ denote the subsets of $[n]$ with $k$ elements. Because we already know a relationship between the $q$-factorial and permutations, we will define a bijection $\psi_{n,k}:S_n\rightarrow\mathcal{B}_n(k) \times S_k \times S_{n-k}.$
Remark: We know that
$$|\mathcal{B}_n(k)| = \frac{n!}{k!(n-k)!} = \frac{|S_n|}{|S_k|\cdot|S_{n-k}|},$$
but dealing with division is hard from a combinatorial point of view. Hence, we “clear denominators” and construct a bijection between the sets $S_n$ and $\mathcal{B}_n(k) \times S_k \times S_{n-k}$ of the same sizes.
For any sequence $a_1,\dots,a_m$ of distinct positive integers, let $P(a_1,\dots,a_m)$ denote the permutation obtained by replacing each $a_i$ with its relative order in the sequence.
Example: $P(3,19,5,2,32) = 2\;4\;3\;1\;5$ since $3$ is the second smallest element in the sequence, $19$ is the fourth smallest element, and so on.
Let $\psi_{n,k}$ be the function that takes $\sigma_1\cdots\sigma_n \in S_n$ and returns the triple $(\alpha,\beta,\gamma) \in \mathcal{B}_n(k) \times S_k \times S_{n-k}$ where
Because we know that $S_n$ and $\mathcal{B}_n(k) \times S_k \times S_{n-k}$ are finite and have the same size, it is sufficient to prove that $\psi_{n,k}$ is injective.
Suppose that $\sigma$ and $\tau$ are distinct elements of $S_n$ with
$$ \psi_{n,k}(\sigma) = \left(\alpha_\sigma,\beta_\sigma,\gamma_\sigma\right)
\qquad
\psi_{n,k}(\tau) = \left(\alpha_\tau,\beta_\tau,\gamma_\tau\right).
$$
If $\{\sigma_1,\dots,\sigma_k\} \neq \{\tau_1,\dots,\tau_k\}$ then $\alpha_\sigma \neq \alpha_\tau.$
Otherwise, if $\sigma_1 \cdots \sigma_k \neq \tau_1\cdots\tau_k$ then $\beta_\sigma \neq \beta_\tau.$
Otherwise we have $\sigma \neq \tau$ and $\{\sigma_{k+1},\dots,\sigma_n\} = \{\tau_{k+1},\dots,\tau_n\},$ so that $\sigma_{k+1} \cdots \sigma_n \neq \tau_{k+1}\cdots\tau_n$ and thus $\gamma_\sigma \neq \gamma_\tau.$
In any case, if $\sigma\neq\tau$ then $\psi_{n,k}(\sigma) \neq \psi_{n,k}(\tau)$ so $\psi_{n,k}$ is injective.
Lemma 2: If $\sigma\in S_n$ with $\psi_{n,k}(\sigma) = (\alpha,\beta,\gamma)$ then
$$ \text{inv}(\sigma) = \left(\text{sum}(\alpha) - \frac{k(k+1)}{2}\right) + \text{inv}(\beta) + \text{inv}(\gamma). $$
Proof of Lemma 2
We separate the inversions of $\sigma$ into three sets,
$$
\begin{aligned}
E_1 &= \text{inversions $(i,j)$ where $i< j \leq k$} \\
E_2 &= \text{inversions $(i,j)$ where $k+1 \leq i< j$} \\
E_3 &= \text{inversions $(i,j)$ where $i \leq k < j.$}
\end{aligned}
$$
Since $\beta$ is a permutation with the same relative order as $\sigma_1\cdots\sigma_k$ we have $|E_1|=\text{inv}(\beta).$ Similarly, $\gamma$ is a permutation with the same relative order as $\sigma_{k+1}\cdots\sigma_n$ so $|E_2|=\text{inv}(\gamma).$ Thus, it is sufficient to prove that
$$ |E_3| = \text{sum}(\alpha) - \frac{k(k+1)}{2}.$$
An inversion in $E_3$ corresponds to a pair of numbers $a,z \in [n]$ where $a \in \{\sigma_1,\dots,\sigma_k\}$ and $z \in [n]\setminus \alpha$ with $a>z.$ If $s_i$ denotes the $i$th smallest element of $\alpha$ then there are $s_i$ elements in $[n]$ that are at most $s_i$ and $i$ elements in $\alpha$ that are at most $s_i,$ meaning there are $s_i-i$ elements in $[n]\setminus \alpha$ that are at most $s_i.$
Thus,
$$|E_3| = (s_1-1) + (s_2-2) + \cdots + (s_k-k) = \text{sum}(A) - \frac{k(k+1)}{2}$$
as claimed.
Combining Lemmas 1 and 2 with the $q$-Factorial Theorem gives
In addition to subsets, lattice paths are often used in combinatorial arguments involving binomial coefficients. We thus give a lattice path interpretation of the $q$-binomial coefficients.
For any $a,b\in\mathbb{N}$ let $L(a,b)$ be the set of lattice paths from $(0,0)$ to $(a,b)$ consisting of East steps $\text{E}=(1,0)$ and North steps $\text{N}=(0,1).$
Example: The set $L(2,1) = \{\text{NEE},\text{ENE},\text{EEN}\}.$
Figure:
The three elements of $L(2,1)$ and their areas.
An element of $L(a,b)$ must have $a$ East steps and $b$ North steps, which form a string of length $a+b.$ There are $\binom{a+b}{a}$ ways to pick the positions of the East steps, which uniquely determines the location of the North steps, so
$$ |L(a,b)| = \binom{a+b}{a}.$$
To interpret $q$-binomials we introduce a new parameter on walks.
If $P \in L(a,b)$ the area of $P$ is the number $\text{area}(P)$ of $1\times1$ boxes underneath the steps of $P$ and above the $x$-axis.
Remark: Some authors define the area of a path as the number of boxes above the path and beneath the line $y=b.$
$q$-Lattice Path Theorem: For any $a,b\in\mathbb{N},$
$$ \sum_{P \in L(a,b)}q^{\text{area}(P)} = \left[ a+b \atop a \right]_q. $$
Proof of the $q$-Lattice Path Theorem
Let $f:L(a,b) \rightarrow \mathcal{B}_{a+b}(a)$ be the function that maps a path $P \in L(a,b)$ to the indices of its East steps. Because a path in $L(a,b)$ is uniquely defined by the location of its East steps, $f$ is a bijection.
Suppose $f(P) = \{s_1,\dots,s_a\}$ for some path $P$ where the $s_i$ are listed in increasing order. The number of boxes underneath $P$ in the column whose top is the $s_i$th step equals the number of North steps before $s_i.$ Since there are $i$ East steps up to $s_i$ there are $s_i - i$ North steps before $s_i,$ and
$$ \text{area}(P) = \text{sum}(f(P)) - \sum_{i=1}^a i = \text{sum}(f(P)) - \frac{a(a+1)}{2}.$$
Example: If $P=\text{NENEENEENN}$ then $f(P)=\{2,4,5,7,8\}$ and
Having established several combinatorial interpretations of $q$-factorials and $q$-binomials, we can refine combinatorial proofs of classical identities to their $q$-analogues. The identities we see in these notes will typically be derived by going back to the objects discussed here.
$\displaystyle\sum_{S \in \mathcal{B}_n(k)}q^{\text{sum}(S)}= q^{\frac{k(k+1)}{2}} \left[ n \atop k \right]_q$
Lattice Paths
area
$\displaystyle\sum_{P \in L(a,b)}q^{\text{area}(P)}= \left[ a+b \atop a \right]_q$
Example: Give a combinatorial proof that
$$ \binom{a+b}{k} = \sum_{j=0}^k \binom{a}{j}\binom{b}{k-j} $$
for any $a,b,k \in \mathbb{N}$ with $0 \leq k \leq a+b.$
Click for Answer
We interpret the binomial coefficients that appear in this equality as subset sizes. Any subset $S$ of $[a+b]$ of size $k$ can be uniquely decomposed as
a subset $\alpha(S) = S \cap \{1,\dots,a\}$ of size $j$ and
a subset $\beta(S) = S \cap \{a+1,\dots,a+b\}$ of size $k-j$
for some $0 \leq j \leq k.$ If $\gamma(S)$ denotes the set obtained by subtracting $a$ from the elements of $\beta(S)$ then the map
$$ f : \mathcal{B}_{a+b}(k) \rightarrow \bigcup_{j=0}^k \mathcal{B}_{a}(j) \times \mathcal{B}_{b}(k-j)$$
defined by $f(S) = (\alpha(S),\gamma(S))$ is a bijection. Since this is a disjoint union, we see that
$$
\begin{aligned}
\binom{a+b}{k}
= \left|\mathcal{B}_{a+b}(k)\right|
&= \sum_{j=0}^k \left|\mathcal{B}_{a}(j)\right| \cdot \left|\mathcal{B}_{b}(k-j)\right| \\[+2mm]
&= \sum_{j=0}^k \binom{a}{j}\binom{b}{k-j}
\end{aligned}
$$
as desired.
Example: Generalize your argument in the last example to prove that
$$ \left[ a+b \atop k \right]_q = \sum_{j=0}^k q^{(a-j)(k-j)-j} \left[ a \atop j \right]_q \left[ b \atop j \right]_q $$
for any $a,b,k \in \mathbb{N}$ with $0 \leq k \leq a+b.$
Click for Answer
If $S \in \mathcal{B}_{a+b}(k)$ and $f(S) = (P,Q)$ where $f$ is the bijection constructed in the last example then
$$ \text{sum}(S) = \text{sum}(P) + \text{sum}(Q) + a|Q|, $$
since we subtract $a$ from every element of $S$ in $\{a+1,\dots,a+b\}$ when constructing $Q.$ Thus, the $q$-Binomial Theorem implies
$$
\begin{aligned}
q^{\frac{k(k+1)}{2}}\left[ a+b \atop k \right]_q
&= \sum_{S \in \mathcal{B}_{a+b}(k)} q^{\text{sum}(S)} \\[+3mm]
&= \sum_{j=0}^k \;\sum_{\substack{P \in \mathcal{B}_{a}(j)\\[+1mm] Q \in \mathcal{B}_{b}(k-j)}} q^{\text{sum}(P) + \text{sum}(Q) + a(k-j)} \\[+3mm]
&= \sum_{j=0}^k q^{a(k-j)} \cdot q^{\frac{j(j+1)}{2}}\left[ a \atop j \right]_q \cdot q^{\frac{(k-j)(k-j+1)}{2}}\left[ b \atop k-j \right]_q
\end{aligned}
$$
and the result follows from algebraically simplifying
$$ \small
\begin{aligned}
&a(k-j) + \frac{j(j+1)}{2} + \frac{(k-j)(k-j+1)}{2} - \frac{k(k+1)}{2} \\[+3mm]
&\;\;= (a-j)(k-j)-j
\end{aligned}$$
in the powers of $q.$
Example: Use lattice path enumeration to prove that
$$ \left[ 2n \atop n \right]_q = \sum_{k=0}^n q^{k^2} \left[ n \atop k \right]_q^2 $$
for any $n \in \mathbb{N}.$
Click for Answer
We start by trying to prove the classical equality
$$ \binom{2n}{n} = \sum_{k=0}^n\binom{n}{k}^2 $$
obtained by setting $q=1$ using lattice path enumeration, and then tracking the area parameter. Since $\binom{2n}{n} = |L(n,n)|$ we try to suitably decompose a lattice path from $(0,0)$ to $(n,n)$ using North and East steps.
Decomposing an element $P$ of $L(n,n)$ as the walk $P_1\cdots P_n$ defined its first $n$ steps followed by the walk $P_{n+1}\cdots P_{2n}$ defined by its remaining $n$ steps gives a bijection
$$f:L(n,n)\rightarrow\bigcup_{k=0}^n L(n-k,k) \times L(k,n-k)$$
where $k$ denotes the number of North steps a walk takes in its first $n$ steps. Although not needed to solve the question at hand, we note that this bijection does prove the classical identity
$$
\begin{aligned}
\binom{2n}{n} &= |L(n,n)| \\
& = \sum_{k=0}^n |L(n-k,k)| \cdot |L(k,n-k)| \\
& = \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} \\
& = \sum_{k=0}^n \binom{n}{k}^2.
\end{aligned}
$$
If $f(P) = (Q,Q^\prime)$ where $Q$ has $k$ North steps then, since $P$ is $Q$ followed by $Q^\prime$ after $Q^\prime$ is raised by $k$ North steps,
we have
$$ \text{area}(P) = \text{area}(Q) + \text{area}(Q^\prime) + k^2. $$
Thus, the $q$-Lattice Path Theorem implies
$$
\begin{aligned}
\left[ 2n \atop n \right]_q &= \sum_{P \in L(n,n)}q^{\text{area}(P)} \\
& = \sum_{k=0}^n \;\sum_{\substack{Q \in L(n-k,k)\\[+1mm] Q^\prime \in L(k,n-k)}} q^{\text{area}(Q) + \text{area}(Q^\prime) + k^2} \\
& = \sum_{k=0}^n q^{k^2} \left[ n \atop k \right]_q \left[ n \atop n-k \right]_q \\
& = \sum_{k=0}^n q^{k^2} \left[ n \atop k \right]_q^2,
\end{aligned}
$$
as claimed.
Remark: Just as we extended classical binomial coefficients $\binom{n}{k}$ to general $n\in\mathbb{C}$ it is possible to extend the $q$-binomial coefficient $\left[ n \atop k \right]_q.$ Writing
$$ \left[ n \atop k \right]_q = \frac{[n]_q\cdots [n-k+1]_q}{[k]!_q}, $$
it is enough to generalize
$$ [n]_q = 1 + q + \cdots + q^{n-1} = \frac{1-q^n}{1-q}$$
when $n \notin\mathbb{N}.$ This can be accomplished, for instance, using a series expansion
$$ \frac{1-q^n}{1-q} = n - \frac{n(n-1)}{2}(1-q) + \cdots $$
which connects to the rich theory of hypergeometric series.
Problem 1: Prove that the $q$-Lattice Path Theorem still holds if the area of a path in $L(a,b)$ is defined to be the number of $1\times1$ boxes above the path and below the line $y=b.$
Problem 2: Give a combinatorial proof involving lattice paths that, for all $a,b,n \in \mathbb{N}$ with $0 \leq a \leq b,$
$$\binom{b+n+1}{n} = \sum_{j=0}^n\binom{a+j}{j}\binom{(b-a)+(n-j)}{n-j}.$$
Problem 3: Prove a $q$-analogue of the identity in Problem 2 (i.e., an identity where the binomial coefficients are replaced by $q$-binomial coefficients, potentially after multiplying by an extra power of $q$).
Problem 4: Prove that
$$ \left[ n \atop k \right]_q = q^k\left[ n-1 \atop k \right]_q + \left[ n-1 \atop k-1 \right]_q$$
for all $n,k \in \mathbb{N}$ with $k \leq n.$
Problem 5: Prove that
$$ \left[ a+b+1 \atop b \right]_q = \sum_{j=0}^b q^{(a+1)(b-j)}\left[ a+j \atop j \right]_q$$
for all $a,b \in \mathbb{N}.$
Problem 6: Fix a positive integer $t$ and recall that a multiset of size $n$ with $t$ types is a set containing $n$ of the numbers $\{1,\dots,t\}$ where numbers can appear multiple times. Define a parameter on the class of multisets with $t$ types and use it to prove the Negative $q$-Binomial Theorem
$$\frac{1}{(1-z)(1-qz)\cdots(1-q^{t-1}z)} = \sum_{n \geq 0} \left[ n+t-1 \atop t-1 \right]_q z^n.$$
Problem 7: Fix $n \in \mathbb{N}$ and $0 \leq k \leq n.$ Prove that if $q=p^r$ is a prime power and $\mathbb{F}_q$ is the finite field with $q$ elements then the number of $k$-dimensional subspaces of an $n$-dimensional vector space over $\mathbb{F}_q$ is $\left[ n \atop k \right]_q.$
