# Parity of shuffle permutations

A $$(p,q)$$-shuffle is a permutation $$\sigma$$ of the set $$\{1, \dots, p, p+1, \dots,p+q\}$$ such that $$\sigma(1)<\dots<\sigma(p)$$ and $$\sigma(p+1) < \dots<\sigma(p+q)\,.$$

It is known that the number of $$(p,q)$$-shuffles is $${p+q \choose p}$$.

Looking at the case $$p+q = 6$$ and considering the parity of shuffles, I was surprised to find that

• $$3$$ of the $${6 \choose 1} = 6$$ $$(1,5)$$-shuffles have even parity
• $$9$$ of the $${6 \choose 2} = 15$$ $$(2,4)$$-shuffles have even parity
• $$10$$ of the $${6 \choose 3} = 20$$ $$(3,3)$$-shuffles have even parity
• $$9$$ of the $${6 \choose 4} = 15$$ $$(4,2)$$-shuffles have even parity
• $$3$$ of the $${6 \choose 5} = 6$$ $$(5,1)$$-shuffles have even parity

It's not so difficult to believe that the number of even $$(p,q)$$-shuffles should equal the number of even $$(q,p)$$-shuffles. But I was very surprised to see that there are so many more even than odd $$(2,4)$$-shuffles.

Are any closed-form solutions known for the number of even $$(p,q)$$-shuffles? If not, is anything known about the asymptotic behaviour?

• I have no time to give a full answer, but the generating polynomial of (p,q)-shuffles according to length is a Gaussian coefficient. So you can deduce the answer you're looking for by evaluating it at -1, which counts even permutations minus odd permutations. Commented Feb 7, 2020 at 10:28

As Philippe suggests in the comments, it is well know that $$\sum_{\sigma \text{ is a (a,b)-shuffle}} q^{\ell(\sigma)}={a+b \choose b}_q$$ where the $$q$$-binomial coefficient (or Gaussian binomial coefficient) on the right side is defined by $${n \choose k}_q=\frac{[n]_q! }{[k]_q! [n-k]_q!}$$ where $$[n]_q!=[1]_q [2]_q \cdots [n]_q$$ and $$[n]_q=1+q+\cdots +q^{n-1}$$.
Thus the difference between the number of even and odd shuffles is obtained by specializing at $$q=-1$$. This polynomial is palindromic, so, depending on the parity, one either gets 0 or the middle (and largest) coefficient of the polynomial $${a+b \choose b}_q$$.
• More generally there's a simple formula for a $q$-binomial coefficient evaluated at a root of unity, sometimes called the $q$-Lucas theorem, due, as far as I know, to Gloria Olive (Generalized powers. Amer. Math. Monthly 72 (1965), 619–627) and often rediscovered. See, e.g., mathoverflow.net/questions/313551/… Commented Feb 7, 2020 at 20:37