Número de maneras de poner $n$ sin etiquetar bolas en $k$ contenedores, con un máximo de $m$ bolas en cada bin

Question

El número de maneras de poner $n$ sin etiquetar bolas en $k$ distintos contenedores es $$\binom{n+k-1}{k-1} .$$ Lo que tiene sentido para mí, pero lo que no puedo entender es cómo modificar esta fórmula si cada cubo tiene un máximo de $m$ bolas.

EDIT: Lo he probado:

Llegué a la generación de la función $$(1-x^{m+1})^k(1-x)^{-k}$$ lo que termina dando me $$\sum_{r(m+1)+r_2=n} \binom{k}{r}(-1)^{r_2}\binom{k+r_2-1}{r_2}$$

Pero cuando la programación de este:

def distribute_max(total,buckets,mmax):
  ret = 0
  for r in xrange(total//(mmax+1)+1):
    r_2 = total - r*(mmax+1)
    ret += choose(buckets,r) * (-1)**r_2 * choose(buckets + r_2 - 1,r_2)
  return ret

Me estoy poniendo de muy mal las respuestas. No estoy seguro de que paso la puse.

Answer 1

Como un cheque que me hice con una inclusión-exclusión argumento, consiguiendo $$\sum_i(-1)^i\binom{k}i\binom{n+k-1-i(m+1)}{k-1}\,.$$

Establecimiento $r=i$ $r_2=n-i(m+1)$ para que coincida con su notación, puedo hacer esto $$\sum_r (-1)^r\binom{k}r\binom{k+r_2-1}{r_2}\,.$$ It appears that you've the wrong exponent on $-1$.

Answer 2

Vamos a denotar el problema como $D(n,k,m)$, luego al $mk-n \leq m$, la respuesta puede ser dada como: $D(n,k,m)=\binom{km-n+k-1}{k-1}$ donde $m \leq n$.

Puede ser fácilmente verificado el uso de $D(5,2,3)=2$ o $D(6,3,3)=10$, etc..

Déjeme que se lo explique en mayor detalle con mi pobre inglés (lo siento).

Supongamos que partimos de que el estado de que todos los contenedores están llenos con $m$ bolas en cada uno. Entonces la tarea es eliminar a $mk-n$ pelotas de estos $k$ papeleras. A ditribute la $mk-n$ "eliminación" en $k$ papeleras, tenemos $\binom{km-n+k-1}{k-1}$ diferentes maneras si $mk-n \leq m$, es decir, el número de la eliminación en cada bin no excederá $m$.