Is there a way to find a representative set for double cosets of groups?

Question

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,\dotsc,\lambda_1\}}\times S_{\{\lambda_1+1,\lambda_1+2,\dotsc,\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}\mid s_{\lambda}\in S_{\lambda},s_{\mu}\in S_{\mu}\}.$$

The set of all double cosets is denoted $S_{\lambda}\backslash S_n/S_{\mu}$. The cardinality of the set $S_{\lambda}\backslash 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 representative elements of these double cosets?

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.

Answer 2

Recently, I also faced with this question. And I’d like to share the answer I find.
Let $G$ be a complex reductive algebraic group. Denote $\Phi \supset \Phi^+ \supset \Delta$ to be a root system with fixed positive roots and simple roots, and $(W,S)$ to be the Weyl group and the corresponding simple reflections. Such a choice will give us a standard Borel subgroup $B$.
Let $I,J \subset \Delta$, then we will have two standard parabolic subgroups $P_I, P_J$ of $G$, and also parabolic subgroups $W_I, W_J$ of $W$. ($W_I$ is just the subgroup generated by simple reflections corresponding to $I$.) Then the generalized Bruhat decomposition told us that $P_I\backslash G/P_J \simeq W_I\backslash W/W_J$. In your case, you can just take $G = \operatorname{GL}_n$, then $W = S_n$, and $W_I$ will give you the Young subgroup.
After introducing the notation, we are ready to answer the question. Define $$ \begin{aligned} W^J := \{w \in W\mid w(J) \subset \Phi^+ \},\\ {^IW} := \{w \in W\mid w^{-1}(I) \subset \Phi^+\},\\ ^IW^J := {^IW} \cap W^J. \end{aligned}$$ Then $W^J$ is the set of coset representatives for $W/W_J$ with smallest length, $^IW$ is the set of coset representatives for $W_I \backslash W$ with smallest length, and $^IW^J$ is the set of double coset representatives of $W_I \backslash W / W_J$ with smallest length. (This is an exercise, which can be found in Bourbaki, Lie groups and Lie algebras, Chapter 4–6, P31, exercise 1.3.) Now return to the question, since you work on $\operatorname{GL}_n$ and $S_n$, everything can be write down explicitly. The above description is just some $w(i) < w(j)$ conditions.
Although the answer is not combinatorial, this also can give you a way to describe the double coset, which is useful in some case.

EDIT: This answer is just a supplement to @JohannesHahn’s existing answer. I’d like to appreciate @LSpice’s kindly comments.