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.
-
$\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$– Jim HumphreysOct 2, 2014 at 15:56
1 Answer
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.