Cómo dividir $n$ distintos elementos en $k$ grupos de tamaño de al menos $m$

Question

Nunca he sido bueno con la combinatoria, por lo que siempre me he pegado con la memorización de la fórmula. Sin embargo, no puedo ni siquiera empezar a comprender la complejidad de este problema.

He intentado buscar respuestas útiles en este sitio, pero sólo he encontrado "$n$ idénticos elementos en grupos de tamaño, al menos, $k$ " y " $n$ distintos elementos en $k$ no vacío grupos.

También he leído acerca de los números de Stirling, pero yo no veo nada sobre el tamaño de los grupos.

Agradecería si alguien me pudiera ayudar enfoque de este problema, o me dirija a un ya publicado pregunta si este es un repost, por lo que me disculpo de antemano.

Answer 1

Si estás de acuerdo con la fórmula exponencial de las particiones del conjunto (es decir, Wilf del Generatingfunctionology libro, en la sección 3.6), a continuación, la mezcla de generación de función $$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$ es $$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$ para obtener un valor explícito.