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.



Number of double cosets of a Young subgroup
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.


