¿Número de formas de distribuir n objetos idénticos entre r grupos idénticos de forma que cada grupo reciba como máximo Ceil(n/r) objetos?

Question

Número de formas de distribución $n$ objetos entre $r$ grupos tales que cada grupo obtenga como máximo $Ceil(n/r)$ ¿Objetos?

Busco una fórmula que me pueda dar el resultado y si es posible una demostración de por qué es correcta. Gracias de antemano.

Answer 1

En lugar de distribuir los objetos entre los grupos hasta que haya $n$ objetos, con un límite de $\lceil \frac nr\rceil$ por grupo, podemos empezar poniendo $\lceil \frac nr\rceil$ objetos en cada grupo, y luego eliminar objetos de algunos grupos hasta que sólo haya $n$ objetos a la izquierda. Tendremos que eliminar $$k := r\left\lceil \frac nr\right\rceil - n = (-n) \bmod r$$ objetos en total.

Así que ahora sólo tenemos que contar el número de maneras de distribuir $k$ objetos entre $r$ grupos. Desde $0\le k < r$ no tenemos que preocuparnos por el límite superior de como máximo $r$ partes, por lo que esto equivale a encontrar $p(k)$ : el número de particiones de $k$ . ( Enlace a Wikipedia )

He hecho una suposición arriba que no es necesariamente cierta: que cualquier forma de eliminar $k$ objetos es válida. De hecho, si $k > \lceil \frac nr \rceil$ entonces no todas las particiones de $k$ están permitidos: por ejemplo, eliminar $k$ objetos todos de un grupo no es válido si había menos de $k$ objetos en ese grupo para empezar. En este caso, si $p_m(k)$ denota el número de particiones de $k$ con una parte más grande de tamaño $m$ entonces el número de particiones válidas es $$\sum_{m=0}^{\lceil n/r \rceil} p_m(k) = p_{\lceil n/r \rceil}(k + \lceil \tfrac nr \rceil).$$ Para un tamaño suficientemente grande $n$ esta restricción deja de importar, por lo que la respuesta será la periódica $p(k)$ . Por ejemplo, si fijamos $r=5$ la respuesta para $n=1, 2, \dots$ es la secuencia $$1,1,1,1,1,\;3,2,2,1,1,\;4,3,2,1,1,\;5,3,2,1,1,\dots$$ con el bloque final $5,3,2,1,1$ (que es $p(4), p(3), p(2), p(1), p(0)$ ) repitiendo para siempre.