Consider the Young diagram of a partition with \(k\) parts and largest part \(\ell \). Its lower boundary is a lattice path from \((0,0)\) to \((\ell ,k)\) consisting of east-steps and north-steps. This path begins with an east-step (since otherwise, the partition would have fewer than \(k\) parts) and ends with a north-step (since otherwise, the largest part would be \({\lt}\ell \)). There are precisely \(k+\ell \) steps total, and the first and last are predetermined, so it remains to choose which \(k-1\) of the remaining \(k+\ell -2\) steps are north-steps. The number of such choices is \(\binom {k+\ell -2}{k-1}\).

The forward map sends \(f\) to the partition whose parts are the nonzero values of \(f\); the inverse pads the partition’s parts with zeros to length \(k\) and sorts. This is a sum-preserving bijection.

This is a restatement of the definition, grouping the sum by partition size \(m = |\lambda |\), and applying Lemma 2.137 to count the monotone functions with each given value sum.

The set of weakly increasing tuples is in bijection with the set of multisets of size \(k\) from \(\ell + 1\) elements, whose cardinality is \(\binom {k+\ell }{k}\) by the stars-and-bars formula.

(a) The definition of \(\binom {n}{k}_{q}\) yields

For each fixed \(\ell \in \{ 0,1,\ldots ,k\} \), the partitions \(\lambda \) with largest part \(\leq n-k\) and length \(\ell \) correspond bijectively to \(k\)-tuples \((\lambda _{1},\lambda _{2},\ldots ,\lambda _{k})\in \mathbb {N}^{k}\) satisfying \(n-k\geq \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{k}\geq 0\) and having exactly \(\ell \) positive entries (by padding with zeros). Summing over all \(\ell \) and then reversing the \(k\)-tuple (substituting \((i_{k},i_{k-1},\ldots ,i_{1})\) for \((\lambda _{1},\ldots ,\lambda _{k})\)) gives part (a).

(b) There is a bijection from weakly increasing \(k\)-tuples \((i_{1},\ldots ,i_{k})\in \{ 0,1,\ldots ,n-k\} ^{k}\) to strictly increasing \(k\)-tuples \((s_{1},\ldots ,s_{k})\in \{ 1,2,\ldots ,n\} ^{k}\), given by \((i_{1},\ldots ,i_{k})\mapsto (i_{1}+1,\, i_{2}+2,\, \ldots ,\, i_{k}+k)\). Moreover, strictly increasing \(k\)-tuples from \(\{ 1,\ldots ,n\} \) correspond bijectively to \(k\)-element subsets \(S\subseteq \{ 1,\ldots ,n\} \). Combining with (a) gives (b).

(c) Substituting \(1\) for \(q\) in (b) gives \(\binom {n}{k}_{1} = |\{ S\subseteq \{ 1,\ldots ,n\} :\, |S|=k\} | = \binom {n}{k}\).

From \(k{\gt}n\), we obtain \(n-k{\lt}0\). The sum in the definition is empty, since there exists no partition with largest part \(\leq n-k {\lt} 0\). Thus \(\binom {n}{k}_{q} = 0\).

For \(\binom {n}{0}_q\): the only weakly increasing \(0\)-tuple is the empty one, whose value sum is \(0\), giving \(q^0 = 1\).

For \(\binom {n}{n}_q\): when \(k = n\), we have \(n - k = 0\), so the values must lie in \(\{ 0\} \), and the only weakly increasing tuple sends everything to \(0\); the value sum is \(0\), giving \(q^0 = 1\).

(a) If \(k=0\), the claim reduces to \(1 = q^{n-k}\cdot 0 + 1\), which holds by Proposition 2.142 and Convention 2.143. So assume \(k {\gt} 0\).

Using Proposition 2.140 (b), we write \(\binom {n}{k}_q\) as a sum over \(k\)-element subsets \(S \subseteq \{ 1,\ldots ,n\} \). We split these subsets into type-1 (containing \(n\)) and type-2 (not containing \(n\)).

The type-2 subsets are exactly the \(k\)-element subsets of \(\{ 1,\ldots ,n-1\} \), contributing \(\binom {n-1}{k}_q\).

The type-1 subsets biject to \((k{-}1)\)-element subsets of \(\{ 1,\ldots ,n-1\} \) via \(S \mapsto S \setminus \{ n\} \). Since \(\operatorname {sum}(S\cup \{ n\} ) = \operatorname {sum}S + n\), the exponent shifts by \(n - k\), giving \(q^{n-k}\binom {n-1}{k-1}_q\).

(b) This is proved similarly, or by combining part (a) with symmetry (applied locally before the main symmetry theorem is established).

By Lemma 2.149, \((1-q)[n]_q = 1 - q^n\). If \([n]_q = 0\), then \(1 - q^n = 0\), contradicting \(q^n \neq 1\).

Since \([n]_q! = \prod _{i=1}^{n} [i]_q\) and each factor is nonzero by Lemma 2.145, the product is nonzero.

(a) By induction on \(n\) (strong induction). For \(k = 0\) both sides equal \(1\). For \(k {\gt} 0\), we use the recurrence from Theorem 2.144 (a) to split \(\binom {n}{k}_q\), multiply both sides by the product \((1-q^k)\cdots (1-q)\), apply the inductive hypothesis to the two resulting terms (at \(n-1\)), and combine using the identity \((1-q^{k+1})q^{n-k-1} + (1-q^{n-k-1}) = 1-q^n\) (after appropriate index shifts).

(b) Divide both sides of (a) by \((1-q^k)(1-q^{k-1})\cdots (1-q)\), which is nonzero when \(q\) is not a root of unity of order \(\leq k\).

Telescoping: \((1-q)(q^{0}+q^{1}+\cdots +q^{n-1}) =(q^{0}+\cdots +q^{n-1})-(q^{1}+\cdots +q^{n}) =1-q^{n}\).

\([n]_1 = 1^0+1^1+\cdots +1^{n-1} = \underbrace{1+1+\cdots +1}_{n\text{ times}} = n\). Then \([n]_1! = [1]_1[2]_1\cdots [n]_1 = 1\cdot 2\cdots n = n!\).

By induction on \(k\). The base case \(k=0\) is trivial. For \(k+1\), split off the last factor \([n-k]_q\) from the falling product and use \([n-k]_q! = [n-k-1]_q! \cdot [n-k]_q\).

Divide the product formula from Theorem 2.147 (b) by \((1-q)^k\) to replace each factor \((1-q^m)/(1-q)\) with \([m]_q\).

The first equality follows from Theorem 2.147 (b) by rewriting each factor \((1-q^m)/(1-q)\) as \([m]_q\) (using Lemma 2.149). The second equality follows from the splitting \([n]_q! = [n]_q[n{-}1]_q\cdots [n{-}k{+}1]_q \cdot [n{-}k]_q!\) (Lemma 2.151).

For each index \(i\), the number of \(j \in \{ 0,1,\ldots ,m{-}1\} \) with \(g_j {\gt} k{-}1{-}i\) equals the number of \(j\) with \(j \ge m - f_i\), which equals \(f_i\). The proof uses the complement counting identity and the characterization of the profile of \(f\) via the predicate \(f_{i'} \le m{-}1{-}j\).

By swapping the order of summation in the double sum \(\sum _j \# \{ i : f(i) {\gt} m{-}1{-}j\} \) and using the identity \(\# \{ j : j \ge m - v\} = v\) for \(0 \le v \le m\).

We construct an explicit involution on weakly increasing tuples. Given a weakly increasing tuple \((f_0, f_1, \ldots , f_{k-1}) \in \{ 0,1,\ldots ,m\} ^k\) (where \(m = n-k\)), define the transpose \((g_0, g_1, \ldots , g_{m-1}) \in \{ 0,1,\ldots ,k\} ^m\) by

This tuple is again weakly increasing. The transpose operation is an involution (applying it twice recovers the original tuple) and preserves the sum of values (\(\sum _j g_j = \sum _i f_i\)). It therefore gives a sum-preserving bijection between weakly increasing \(k\)-tuples in \(\{ 0,\ldots ,n{-}k\} \) and weakly increasing \((n{-}k)\)-tuples in \(\{ 0,\ldots ,k\} \), proving \(\binom {n}{k}_q = \binom {n}{n-k}_q\).