5
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Philippe Nadeau
    Commented Feb 7, 2020 at 10:28

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Precise asymptotics for this coefficient (and others) are given in Theorem 1 of this paper by Melczer, Panova, and Pemantle.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ "q = -1"/"cyclic sieving" should tell you that this counts the number of binary words with a 0s and b 1s that are palindromic. $\endgroup$
    – Sam Hopkins
    Commented Feb 7, 2020 at 18:22
  • $\begingroup$ (Not to hard to prove that with a sign-reversing involution, in fact.) $\endgroup$
    – Sam Hopkins
    Commented Feb 7, 2020 at 18:31
  • $\begingroup$ 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/… $\endgroup$
    – Ira Gessel
    Commented Feb 7, 2020 at 20:37

Your Answer

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

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