Sign-reversing involution for $q$-binomial coefficient at $q=-1$

Question

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?

Answer 1

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.

Answer 2

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.