Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It is a standard exercise in combinatorics to show that the binomial coefficient satisfies the reciprocity law $\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}$ for $n, k \geqslant 0$, which is the multiset coefficient up to sign. Does the $q$-binomial coefficient $\binom{-n}{k}_{q}$ satisfy a similar reciprocity law with a nice combinatorial interpretation (and proof), which specializes to the case above for $q \to 1$?

share|improve this question
1  
I do not have a combinatorial proof, but playing and matching I get $\binom{-n}{k}_q = (-1)^k q^{n k} \cdot q^{k(k-1)/2} \cdot \binom{n+k-1}{k}_q$, which works for $n \geqslant 1$ and $k \geqslant 0$. –  Sasha Apr 5 '12 at 15:59
    
Thanks. Perhaps with the formula I might be able to prove this combinatorially. –  user02138 Apr 5 '12 at 16:08
    
Should the exponent of the $q$ be $-nk - k(k-1)/2$? –  user02138 Apr 5 '12 at 16:26
    
Yes, indeed. Sorry about that. Retyping the formula $\binom{-n}{k}_q = (-1)^k q^{-n k} \cdot q^{-k(k-1)/2} \cdot \binom{n+k-1}{k}_q$, for $n\geqslant 1$ and $k \geqslant 0$. –  Sasha Apr 5 '12 at 16:45
1  
If you read German you can find @Sasha’s identity on p. 23 of Ch. 2 of these notes by Johann Cigler, between (2.23) and (2.24). I didn’t look closely, but the argument appears to be computational. –  Brian M. Scott Apr 5 '12 at 19:24

1 Answer 1

up vote 3 down vote accepted

I don’t know that there’s really an entirely natural combinatorial interpretation of $\binom{-n}k$ or ${\binom{-n}k}_q$ for $n>0$, but perhaps this is of some interest.

For $0\le k\le n$, $\binom{n}k$ is the number of lattice paths from $\langle 0,0\rangle$ to $\langle k,n-k\rangle$ using $k$ right-steps and $n-k$ up-steps. ${\binom{n}k}_q$ is the number of such paths broken down according to the area between the path and the horizontal axis: the coefficient of $q^r$ is the number of paths for which the area is $r$.

For $k\ge 0$ and $n>0$, $\left|\binom{-n}k\right|$ is the number of lattice paths from $\langle 0,0\rangle$ to $\langle k,-n-k\rangle$ using $n$ down-steps and $k$ down-right-steps (i.e., steps $\langle i,j\rangle\to\langle i,j-1\rangle\to\langle i+1,j-1\rangle$), with the proviso that the last step must be a down-step. $\left|{\binom{-n}k}_q\right|$ is the number of such paths broken down according to the signed area between the path and the horizontal axis: the coefficient of $q^r$ is the number of paths for which the signed area is $r$ (which of course is negative). In both cases the sign of the binomial coefficient is given by $(-1)^k$.

Still with $k\ge 0$ and $n>0$, $\binom{n+k-1}k$ is the number of lattice paths from $\langle 0,0\rangle$ to $\langle k,n-1\rangle$ using $k$ right-steps and $n-1$ up-steps; ${\binom{n+k-1}k}_q$ breaks them down by area between the path and the horizontal axis, as before. Take any one of these paths and add an up-step from $\langle k,n-1\rangle$ to $\langle k,n\rangle$. Now replace each up-step by a down-step and each right-step by a down-right-step. The resulting path goes from $\langle 0,0\rangle$ to $\langle k,-n-k\rangle$ and ends with a down-step, and the correspondence is clearly bijective, so $\left|\binom{-n}k\right|=\binom{n+k-1}k$. Moreover, the transformation takes a path with signed area $r\ge 0$ between it and the horizontal axis to one with signed area $-r-\binom{k+1}2$. Thus, up to sign the coefficient of $q^r$ in ${\binom{n+k-1}k}_q$ is equal to the coefficient of $q^{-r-\binom{k+1}2}$ in ${\binom{-n}k}_q$. By an obvious symmetry $q^r$ and $q^{(n-1)k-r}$ have the same coefficient in ${\binom{n+k-1}k}_q$, so up to sign the coefficient of $q^{(n-1)k-r}$ in ${\binom{n+k-1}k}_q$ is equal to the coefficient of $q^{-r-\binom{k+1}2}$ in ${\binom{-n}k}_q$. Finally,

$$\begin{align*} \left((n-1)k-r\right)-\left(-r-\binom{k+1}2\right)&=(n-1)k+\binom{k+1}2\\ &=nk+\binom{k}2\;, \end{align*}$$

so the coefficient of $q^r$ in $\left|{\binom{-n}k}_q\right|$ is equal to the coefficient of $q^{r+nk+\binom{k}2}$ in ${\binom{n+k-1}k}_q$, and we have

$${\binom{-n}k}_q q^{nk+\binom{k}2}=(-1)^k{\binom{n+k-1}k}_q\;.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.