How to divide $n$ distinct elements into $k$ groups of size of at least $m$

396 Views Asked by At

I have never been good with combinatorics, so I have always stuck with memorizing the formula. However, I can't even begin to fathom the complexity of this problem.

I have tried searching for helpful answers on this site, but I only found " $n$ identical elements into groups of size at least $k$ " and " $n$ distinct elements into $k$ nonempty groups.

I have also read about the Stirling numbers, but I did not see anything about the size of the groups.

I would appreciate if someone could help me approach this problem, or direct me to an already posted question if this is a repost, for which I apologize in advance.

1

There are 1 best solutions below

0
On BEST ANSWER

If you're okay with the exponential formula for set partitions (say, in Wilf's Generatingfunctionology book, section 3.6), then the mixed generating function $$H(x,y)=\sum_{n,k} h(n,k) \frac{x^n}{n!}y^k$$ for the number of ways $h(n,k)$ to divide $n$ distinguishable elements into $k$ groups of size at least $m$ is $$H(x,y)=e^{y(e^x - e_{<m}^x)},$$ where $e_{<m}^x=\sum_{p<m}\frac{x^p}{p!}$. Then, by extracting the coefficient of $y^k$ in $H(x,y)$ you get$$ h(n,k)=n![x^n]\left(\frac{(e^x - e_{<m}^x)^k}{k!}\right).$$ It looks like you won't get anything pretty, but for any $m$ and $k$ you can expand $(e^x - e_{<m}^x)^k$ with the multinomial theorem and then extract the coefficient of $x^n$ to get an explicit value.