Consider the q-binomial coefficient $\binom{n}{k}_q$.

One combinatorial way to define it is as follows. Let $W_{n,k}$ be the set of binary words of length $n$ with $(n-k)$ 0's and $k$ 1's. An inversion in such a word $w=w_1\ldots w_n$ is a pair of indices $1 \leq i < j \leq n$ with $w_i > w_j$. Let $\mathrm{inv}(w)$ denote the number of inversions of $w$.

Then $\binom{n}{k}_q=\sum_{w\in W_{n,k}} q^{\mathrm{inv}(w)}$.

I am interested in plugging $q=-1$ into the binomial coefficient. For a word $w$, let $\mathrm{rev}(w)$ denote the reverse of $w$. So $w$ with $\mathrm{rev}(w) = w$ are the palindromes.

Theorem: $\binom{n}{k}_{q=-1} = \#\{w \in W_{n,k}\colon w = \mathrm{rev}(w)\}$.

It is possible to prove this theorem in an ugly way by evaluating $\binom{n}{k}_{q=-1}$ directly using the product formula $\binom{n}{k}_{q} = \frac{(1-q^n)(1-q^{n-1})\cdots(1-q^{n-k+1})}{(1-q^k)(1-q^{k-1})\cdots(1-q)}$. It is also possible to prove this in an algebraic way by realizing $\mathrm{rev}$ as a linear map on the exterior product $\wedge^k(\mathbb{C}^n)$.

As an intermediary between the ugly and the algebraic proofs, we can look for a nice combinatorial proof. In the case when $n=2m$ is even, I know a nice combinatorial proof via a sign-reversing involution, which I now briefly describe.

Take a word $w=w_1\ldots w_n \in W_{n,k}$. If $w$ is a palindrome, set $\tau(w) = w$. Otherwise, find the smallest $j$ such that $w_{m+1-j} \neq w_{m+j}$, and let $\tau(w)$ be the result of swapping these two letters in $w$. Then $\tau\colon W_{n,k}\to W_{n,k}$ is an involution which changes the parity of the number of inversions of the words it acts nontrivially on, and whose fixed points are precisely the palindromes (which all have an even number of inversions).

Question: Can this sign-reversing involution be extended to work in the case of $n$ odd?

  • 2
    $\begingroup$ Ah, I misread the definition of inversion and stupidly forgot what I know about $q$-binomial coefficients. $\endgroup$
    – Will Sawin
    Sep 7 at 0:16
  • 1
    $\begingroup$ If $n$ is odd and whichever one of $k$ or $n-k$ is even is congruent to $2$ mod $4$ then palindromes have an odd number of inversions (e.g. $010$). What would it mean for the involution proof to be extended to this case? A sign-reversing involution of the non-palindromes can't exist as it would prove the negation of the correct formula. $\endgroup$
    – Will Sawin
    Sep 7 at 0:26
  • $\begingroup$ @WillSawin: possibly now the fixed point set of the involution will not be the palindromes themselves, but some set in bijection with them. $\endgroup$ Sep 7 at 0:27

2 Answers 2


Here is a uniform proof:

Consider the involution on words $w_1,\dots,w_n$ of length $n$ that takes the first $j$ such that $1 \leq j \leq n/2$ with $w_{2j-1}$ and $w_{2j}$ distinct and swaps $w_{2j-1}$ and $w_{2j}$.

Any word not fixed by the involution has its sign reversed, since swapping two adjacent letters only affects the contribution of that pair of letters to the number of inversions and if the letters are different it always increases or reduces the number of inversions by one.

The fixed points are words that consist of $2 \lfloor \frac{n}{2} \rfloor$ pairs of the same bit repeated and then, if $n$ is odd, a final bit. These all have an even number of inversions since every pair has a repeated bit.

Thus, the signed sum is equal to the number of fixed points, which is naturally in bijection with the number of palindromes.


I am recording here the algebraic proof using exterior powers of vector spaces. I think it makes for an interesting comparison to Will Sawin's very nice answer, because here the reverse really appears. It is a standard "linear algebra argument" in the sense of the cyclic sieving phenomenon.

For convenience we work with subsets of $[n] := \{1,2,\ldots,n\}$ rather than binary words, but of course these are the same. Consider $V=\mathbb{C}^n$ with canonical ordered basis $e_1,\ldots,e_n$.

Let $\mathrm{rev}\colon V \to V$ denote the linear map which sends $e_i$ to $e_{n+1-i}$. The $k$th exterior power $\wedge^k V$ has a basis $e_S := e_{i_1} \wedge e_{i_2} \wedge \cdots \wedge e_{i_k}$ indexed by $k$-subsets $S= \{i_1 < \cdots < i_k\} \subseteq [n]$, and $(-1)^{\binom{k}{2}}\mathrm{rev}(e_S) = e_{\mathrm{rev}(S)}$ where for a subset we define $\mathrm{rev}(S) = \{n+1-i\colon i \in S\}$. So the trace of $(-1)^{\binom{k}{2}}\mathrm{rev}$ acting on $\wedge^k V$ is $\#\{S\colon \mathrm{rev}(S)=S\}$.

On the other hand, we can diagonalize $\mathrm{rev}\colon V \to V$: it has an eigenbasis $v_0,\ldots,v_{n-1}$ where the eigenvalue of $v_i$ is $q^{i}$ (here $q=-1$). Then a different basis of $\wedge^k V$ is given by wedges of the form $v_{i_1} \wedge \cdots \wedge v_{i_k}$, and in this basis we compute the trace of $\mathrm{rev}$ as $\sum_{S} q^{\sum_{i\in S}(i-1)}$ (a sum over $k$-element subsets $S\subseteq [n]$). But the combinatorial definition of $q$-binomial amounts to $\binom{n}{k}_q = q^{-\binom{k+1}{2}}\sum_{S} q^{\sum_{i\in S} i}$. Comparing the two formulas for the trace of $\mathrm{rev}\colon \wedge^kV \to \wedge^k V$ we get the desired result.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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