Let $\lambda=(\lambda_1,\lambda_2)$, $\mu=(\mu_1,\mu_2)$ be two compositions of $n$. Just to remind that $\lambda,\mu$ are not necessarily partitions. Denote $S_{\lambda}$ and $S_{\mu}$ the Young subgroups of $S_n$. Say, $S_{\lambda}=S_{\{1,2,\ldots,\lambda_1\}}\times S_{\{\lambda_1+1,\lambda_1+2,\ldots,\lambda_1+\lambda_2\}}$. For each $\sigma$ in $S_n$, the $(S_{\lambda},S_{\mu})$-double coset of $\sigma$ is the set $$S_{\lambda}\sigma S_{\mu}=\{s_{\lambda}\sigma s_{\mu}|s_{\lambda}\in S_{\lambda},s_{\mu}\in S_{\mu}\}.$$

The set of all double cosets is denoted $S_{\lambda}\setminus S_n/S_{\mu}$. The cardinality of the set $S_{\lambda}\setminus S_n/S_{\mu}$ is $\min\{\lambda_1,\lambda_2,\mu_1,\mu_2\}+1$. I want to ask if there exists an easy way to find out these representative elements of double cosets?

  • 2
    $\begingroup$ This is a known question, and has known answers, even in the case of arbitrary compositions (not just in two parts). See Mark Wildon, A model for the double cosets of Young subgroups for an exposition. For example, combining Lemma 5.4 with Corollary 5.1, you get a bijection between the minimum-length representatives of the double cosets and certain matrices. But the former representatives are in bijection with the double cosets themselves, since each double coset has exactly one such representative (this follows from Theorem 4.3). $\endgroup$ Commented Jul 16, 2017 at 13:26

1 Answer 1


$S_n$ is a Coxeter group (w.r.t. the neighbour-transpositions) and the Young subgroups are its parabolic subgroup. Therefore there is a canonical way to describe coset and double-coset representatives: There is a unique element of minimal length in each of these (double)cosets.

This also provides algorithmic ways to efficiently iterating through the set of (double)cosets by enumerating the representatives.


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.