Counting parabolic double cosets in symmetric groups (Q2049615)

Summary: Billey, Konvalinka, Petersen, Solfstra, and Tenner recently presented a method for counting parabolic double cosets in Coxeter groups, and used it to compute \(p_n\), the number of parabolic double cosets in \(S_n\), for \(n\leqslant 13\). In this paper, we derive a new formula for \(p_n\) and an efficient polynomial time algorithm for evaluating this formula. We use these results to compute \(p_n\) for \(n\leqslant 5000\) and to prove an asymptotic formula for \(p_n\) that was conjectured by Billey et al.