4
$\begingroup$

Let $\lambda\vdash n$ be a partition of $n$ with $k$ parts and $S_\lambda$ be a Young subgroup of $S_n$. Further let $S_\lambda\backslash S_n/ S_\lambda$ be the set of double-cosets. Now I would like to get the most general bound on the number of these cosets. All I could come up with is roughly $n^{k^2}$ but I wonder if this is not far to big.. For example in the cases $\lambda=(n-k,k)$ I think that there are only $k$ such double cosets.

$\endgroup$
1
  • $\begingroup$ You need to add a broader tag such as 'group-theory'. Aside from that, Richard's answer reflects the fact that a great deal is known about symmetric groups; so your question is certainly not new. $\endgroup$ Oct 2, 2014 at 15:56

1 Answer 1

14
$\begingroup$

It is a standard result that the number of double cosets of the pair $(S_\lambda, S_\mu)$ is the number of matrices of nonnegative integers with row sum vector $\lambda$ and column sum vector $\mu$. See for instance Exercise 7.77 of Enumerative Combinatorics, vol. 2. This makes it clear, for instance, why there are only $k+1$ double cosets when $\lambda=\mu=(n-k,k)$. There are also many known estimates for the number of matrices of nonnegative integers with given row and column sum vectors. An example is the paper http://www.math.lsa.umich.edu/~barvinok/asymptotics.pdf by Barvinok and Hartigan.

$\endgroup$
0

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.