1 Problem description

There is an interesting combinatorial problem that arose while I was computing the wedge product of two alternating tensors. Let $S_{k+l}$ be the permutation group on the set $\{1,2,\mathrm{\dots },k+l\}$, and $S_{k,l}$ be the set of all $(k,l)$-shuffles, i.e., $\sigma \in S_{k,l}$ means that $\sigma \in S_{k+l}$ and satisfies

Let the number of inversions of $\sigma$ be $\mathrm{inv}(\sigma )$. Then its sign is $\mathrm{sgn}(\sigma )={(-1)}^{\mathrm{inv}(\sigma )}$. Suppose $f$ and $g$ are two alternating $k$- and $l$-tensors on a vector space $V$. The wedge product of $f$ and $g$ is

$(f\wedge g)(v_1,\mathrm{\dots },v_{k+l})={\displaystyle \sum _{\sigma \in S_{k,l}}}\mathrm{sgn}(\sigma )f(v_{\sigma (1)},\mathrm{\dots },v_{\sigma (k)})g(v_{\sigma (k+1)},\mathrm{\dots },v_{\sigma (k+l)}),$

where $v_1,\mathrm{\dots },v_{k+l}\in V$. This naturally leads to the following question:

How many positive terms in the above summation, or equivalently, how many $(k,l)$-shuffles that have an even number of inversions?

First observe that there are $\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)$ shuffles. Since the entries within each block remain in increasing order, every inversion must occur between the first $k$ positions and the last $l$ positions. More precisely, let $A_{\sigma }=\{\sigma (1),\mathrm{\dots },\sigma (k)\}$ and $B_{\sigma }=\{\sigma (k+1),\mathrm{\dots },\sigma (k+l)\}=A_{\sigma }^c$, and define $\rho (A_{\sigma })=\mathrm{\#}\{(a,b):a\in A_{\sigma },b\in B_{\sigma },a>b\}$. Then $\mathrm{inv}(\sigma )=\rho (A_{\sigma })$. Suppose the number of even and odd shuffles are $E$ and $O$, respectively. Then we have

$\{\begin{array}{cc}E+O=\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)\hfill & \\ E-O={\sum }_{\sigma \in S_{k,l}}{(-1)}^{\rho (A_{\sigma })}.\hfill & \end{array}$

The main difficulty is to give a formulation for $E-O$. As we shall see, the appropriate tool for this purpose is the $q$-binomial coefficient.

2 $q$-binomial coefficient

The $q$-binomial coefficient, also called the Gaussian binomial coefficient, is a $q$-analogy of the binomial coefficient. A more detailed theory can be found in the book [1]. Given a number $q$, the $q$-binomial coefficient is defined as

${\left({\displaystyle \genfrac{}{}{0pt}{}{n}{r}}\right)}_q={\displaystyle \frac{(1-q^n)(1-q^{n-1})\mathrm{\cdots }(1-q^{n-r+1})}{(1-q)(1-q^2)\mathrm{\cdots }(1-q^r)}}$ (1)

where $n\ge r$ are nonnegative integers, and for $r=0$ the value is $1$. It satisfies the $q$-Pascal’s identity

${\left({\displaystyle \genfrac{}{}{0pt}{}{n}{r}}\right)}_q={\left({\displaystyle \genfrac{}{}{0pt}{}{n-1}{r}}\right)}_q+q^{n-r}{\left({\displaystyle \genfrac{}{}{0pt}{}{n-1}{r-1}}\right)}_q.$ (2)

Combining this identity with the mathematical induction, it is obvious that ${\left(\genfrac{}{}{0pt}{}{n}{r}\right)}_q$ is a polynomial of $q$ with nonnegative integer coefficients, and the degree is $r(n-r)$. To further investigate its properties, define the $q$-number

${[k]}_q=1+q+q^2+\mathrm{\cdots }+q^{k-1}=\{\begin{array}{cc}\frac{1-q^k}{1-q},q\ne 1\hfill & \\ k,q=1,\hfill & \end{array}$

and the $q$-factorial

${[k]}_q!={[1]}_q\cdot {[2]}_q\mathrm{\cdots }{[k-1]}_q\cdot {[k]}_q.$

Then we can write ${\left(\genfrac{}{}{0pt}{}{n}{r}\right)}_q$ equivalently as

${\left({\displaystyle \genfrac{}{}{0pt}{}{n}{r}}\right)}_q={\displaystyle \frac{{[n]}_q!}{{[n-r]}_q!{[r]}_q!}}.$ (3)

A basic relationship between the $q$-factorial and the inversions is stated as follows.

Proposition 1.

Let $S_n$ be the permutation group on the set $\{1,2,\mathrm{\dots },n\}$. Then

${\displaystyle \sum _{\sigma \in S_n}}{q}^{\mathrm{inv}(\sigma )}={[n]}_q!$ (4)

Proof.

For any element in $S_n$, it can be constructed by putting $n$ in a position between $\{1,2,\mathrm{\dots },n\}$, and the number of the increase of the inversions equals to the number of elements that in the right side of $n$. Therefore, it holds that

${\displaystyle \sum _{\sigma \in S_n}}{q}^{\mathrm{inv}(\sigma )}$ $={\displaystyle \sum _{{\sigma }^{\prime }\in S_{n-1}}}{\displaystyle \sum _{j=0}^{n-1}}{q}^{\mathrm{inv}({\sigma }^{\prime })+j}$

$=\left({\displaystyle \sum _{{\sigma }^{\prime }\in S_{n-1}}}{q}^{\mathrm{inv}({\sigma }^{\prime })}\right)(1+q+\mathrm{\cdots }+q^{n-1})$

$={[n]}_q{\displaystyle \sum _{{\sigma }^{\prime }\in S_{n-1}}}{q}^{\mathrm{inv}({\sigma }^{\prime })}.$

For $n=1$, we have ${\sum }_{\sigma \in S_1}{q}^{\mathrm{inv}(\sigma )}=q^0=1$. Therefore, we obtain

${\displaystyle \sum _{\sigma \in S_n}}{q}^{\mathrm{inv}(\sigma )}={[n]}_q{[n-1]}_q{\displaystyle \sum _{\sigma \in S_{n-2}}}{q}^{\mathrm{inv}(\sigma )}=\mathrm{\cdots }={[n]}_q!.$

The proof is completed. ∎

3 The value of $E-O$

Now we come back to the original question. A key observation is that any permutation in $S_{k+l}$ has a unique decomposition:

$\sigma =\pi \circ \tau ,$

where $\tau$ is a $(k,l)$-shuffle and $\pi =({\pi }_1,{\pi }_2)\in S_k\times S_l$ with ${\pi }_1$ and ${\pi }_2$ act on the sets $A_{\tau }$ and $B_{\tau }$, respectively. Moreover, the number of inversions of $\sigma$ satisfies

$\mathrm{inv}(\sigma )=\rho (A_{\tau })+\mathrm{inv}({\pi }_1)+\mathrm{inv}({\pi }_2).$

Therefore, we have

${\displaystyle \sum _{\sigma \in S_{k+l}}}{q}^{\mathrm{inv}(\sigma )}$ $={\displaystyle \sum _{\tau \in S_{k,l}}}{\displaystyle \sum _{({\pi }_1,{\pi }_2)\in S_k\times S_l}}{q}^{\rho (A_{\tau })+\mathrm{inv}({\pi }_1)+\mathrm{inv}({\pi }_2)}$

$={\displaystyle \sum _{\tau \in S_{k,l}}}{q}^{\rho (A_{\tau })}{\displaystyle \sum _{{\pi }_1\in S_k}}{q}^{\mathrm{inv}({\pi }_1)}{\displaystyle \sum _{{\pi }_2\in S_l}}{q}^{\mathrm{inv}({\pi }_2)}$

$={\displaystyle \sum _{\tau \in S_{k,l}}}{q}^{\rho (A_{\tau })}\cdot {[k]}_q!\cdot {[l]}_q!.$

By Proposition 1, this implies

${\displaystyle \sum _{\tau \in S_{k,l}}}{q}^{\rho (A_{\tau })}={\displaystyle \frac{{[k+l]}_q!}{{[k]}_q!{[l]}_q!}}={\left({\displaystyle \genfrac{}{}{0pt}{}{k+l}{k}}\right)}_q,$ (5)

and thereby $E-O={\left(\genfrac{}{}{0pt}{}{k+l}{k}\right)}_{-1}$. To compute ${\left(\genfrac{}{}{0pt}{}{N}{k}\right)}_{-1}$ for any $N\ge k\ge 0$, using the $q$-Pascal’s identity

${\left({\displaystyle \genfrac{}{}{0pt}{}{N}{k}}\right)}_{-1}={\left({\displaystyle \genfrac{}{}{0pt}{}{N-1}{k}}\right)}_{-1}+{(-1)}^{N-k}{\left({\displaystyle \genfrac{}{}{0pt}{}{N-1}{k-1}}\right)}_{-1}$

and the initial values ${\left(\genfrac{}{}{0pt}{}{N}{0}\right)}_{-1}=1$ and ${\left(\genfrac{}{}{0pt}{}{k}{k}\right)}_{-1}=1$, we can recursively obtain all the values.

For $\sigma \in S_{k,l}$ with $k+l=N$, write the elements in $A_{\sigma }$ as . Then the number of inversions of $\sigma$ is $\rho (A_{\sigma })=(i_1-1)+(i_2-2)+\mathrm{\cdots }+(i_k-k)$. Now consider the polynomial $p_N(x)={\prod }_{i=0}^{N-1}(1+q^{i}x)$. The coefficient of the $x^k$ term is

$c_k={\displaystyle \sum _{S\in X_k}}{q}^{j_1+j_2+\mathrm{\cdots }+j_k},$

where . It is easy to verify the one-to-one correspondace between the tuples $(j_1,j_2,\mathrm{\dots },j_k)$ and the above $(k,l)$-shuffles by letting $j_t=i_t-1$. Therefore, we have

${\displaystyle \sum _{t=1}^k}{j}_t={\displaystyle \sum _{t=1}^k}(i_t-1)=\rho (A_{\sigma })+{\displaystyle \sum _{t=1}^k}t-k=\rho (A_{\sigma })+{\displaystyle \frac{k(k-1)}{2}}.$

This implies that

$c_k=q^{k(k-1)/2}{\displaystyle \sum _{\sigma \in S_{k,l}}}{q}^{\rho (A_{\sigma })}=q^{k(k-1)/2}{\left({\displaystyle \genfrac{}{}{0pt}{}{N}{k}}\right)}_q.$

This gives the relation between the $q$-binomial coefficient and the coefficient of the $x^k$ term of the polynomial ${\prod }_{i=0}^{N-1}(1+q^{i}x)$.

Using the above relation, substituting $q=-1$ into the polynomial $p_N(x)$ and comparing the coefficient of the $x^k$ term, we finally obtain

$E-O={\left({\displaystyle \genfrac{}{}{0pt}{}{k+l}{k}}\right)}_{-1}=\{\begin{array}{cc}0,kl\equiv 1(\mathrm{mod2})\hfill & \\ \left(\genfrac{}{}{0pt}{}{\lfloor (k+l)/2\rfloor }{\lfloor k/2\rfloor }\right),\mathrm{else}.\hfill & \end{array}$ (6)

Returning to the original problem, this means that in the wedge product of a $k$-tensor and an $l$-tensor, the number of positive terms exceeds the number of negative terms by the amount $\left(\genfrac{}{}{0pt}{}{\lfloor (k+l)/2\rfloor }{\lfloor k/2\rfloor }\right)$, or they are equal when both $k$ and $l$ are odd integers.