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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .