1
$\begingroup$

Trying a bit of combinatorics this winter break, and I don't understand a certain claim.

The claim is that for each $k$ there is a unique polynomial $P_k(x)$ of degree $k$ whose coefficients are in $\mathbb{Q}(q)$, the field of rational functions, such that $P_k(q^n)=\binom{n}{k}_q$ for all $n$.

Here $\binom{n}{k}_q$ is the $q$-binomial coefficient. I guess what is mostly troubling me is that $P_k(q^n)$ is a polynomial in $q^n$. I'm sure it's obvious, but why is the claim true? Thanks.

  • 1
    @Sasha, if $P(x)=1+q^{-1}x$, then $P(q^2)=1+q$.2011-12-19

3 Answers 3

2

I think it could go something like this (but I'll bet there's also an inductive proof or even a more direct and beautiful formula): $ [n]_q = \sum_{i=0}^{n-1}\;q^i = \frac{1-q^n}{1-q} = f(q^n) \qquad\text{for}\qquad 0 < n \in \mathbb{N} \qquad\text{and}\qquad f(x) = \frac{1-x}{1-q} \in \mathbb{Q}(q)[x] $ Now if we note that $[0]_q=0$ and that $[a+b]_q=[a]_q+q^a[b]_q$ for $a,b\in\mathbb{N}$, then for $a=n-i$ and $b=1+i$, it follows that $[n-i]_q=[n]_q-q^{n-i}[1+i]_q$ for $0 \leq i \leq k < n$, so that $ \binom{n}{k}_q = \prod_{i=0}^{k-1}\frac{[n-i]_q}{[1+i]_q} = \prod_{i=0}^{k-1}\frac{[n]_q-q^{n-i}[1+i]_q}{[1+i]_q} = P_k(q^n) %\qquad\text{for}\qquad %[m]_q! = \prod_{h=1}^{m} [h]_q $ for $ P_k(x) =\prod_{i=0}^{k-1}\frac{f(x)-x\cdot c_i q^{-i}}{c_i} =\prod_{i=0}^{k-1}\left(\frac{f(x)}{c_i}-\frac{x}{q^i}\right) \in \mathbb{Q}(q)[x] $ since each $c_i=[1+i]_q\in\mathbb{Q}(q)$, and that, furthermore, $deg(P_k)=k$ since each term in the above product is linear. This simplifies to $ P_k(x) = \prod_{i=1}^{k} \frac{1 - x (1+q-q^{1-i})}{1-q^i}. $

1

The $q$-binomial coefficient satisfies the recurrence $ \binom{n}{k}_q = q^k \binom{n-1}{k}_q + \binom{n-1}{k-1}_q, $ which follows easily from the definition. We can assume inductively that each term on the right is a polynomial and therefore the LHS is a polynomial.

Edit: Unfortunately this does not seem to yield the uniqueness required in the question.

  • 0
    @mixedmath: I wanted to give credit to Chris for being bold enough to take that path, which I suspect now will also get there.2011-12-21
1

Existence. Recall $[\begin{smallmatrix} n \\ k \end{smallmatrix}]_q$ counts the $k$-dimensional subspaces of $\mathbb{F}_q^{\,n}$. A $k$-frame is an ordered linearly independent $k$-subset of $\mathbb{F}_q^{\,n}$. The number of $k$-frames may be counted in two ways: first, pick a vector, then a vector not in the span of the first, then a vector not in the span of the first two, and so on yielding $(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})$. On the other hand, we may also count them by first picking a $k$-dimensional subspace, and then within that subspaces repeating the same process, yielding instead $[\begin{smallmatrix} n \\ k \end{smallmatrix}]_q(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})$. Equating yields the formula

$ \begin{bmatrix} n \\ k \end{bmatrix}_q = \frac{\color{Red}{q^n}-1}{q^k-1}\frac{\color{Red}{q^n}-q}{q^k-q}\cdots\frac{\color{Red}{q^n}-q^{k-1}}{q^k-q^{k-1}}. $

Evidently this is a polynomial in $q^n$ with coefficients in $\mathbb{Q}(q)$. By cancelling powers of $q$ in each of the fractions, then dividing top and bottom of each by $(q-1)$ in order to obtain $q$-analogs of integers, we may check this matches the textbook formula

$ \frac{[n]_q[n-1]_q\cdots[n-(k-1)]_q}{[k]_q\,[k-1]_q\cdots\cdots\cdots\cdots[1]_q} = \frac{[n]_k!}{[k]_q!\,[n-k]_q!}. $

Uniqueness. If $P,Q\in\mathbb{Q}(q)[T]$ and $P(q^n)=Q(q^n)$ for all $n$, then their difference $R(q^n)$ must be the zero element of $\mathbb{Q}(q)$ for all $n$. Without loss of generality, $R(T)\in\mathbb{Q}[q,T]$ after clearing denominators of coefficients of powers of $T$. Writing $R(T)=a_d(q)T^d+\cdots+a_1(q)T+q_0(q)$, we can find an $n$ large enough so that $\deg(a_d)+nd>\deg(a_k)+nk$ for $k, so $\deg P(q^n)>0$, a contradiction, unless $d=0$ and so $R(T)=0$.