# Challenging combinatorial problem with balls and boxes

There are $N$ boxes. I want to distribute $(j\cdot D)$ balls into $N$ boxes, where $j$ and $D$ are arbitrary natural numbers.

However, more than $(D-1)$ balls is not allowed to be put in each box. That is, $(D-1)$ balls is maximum number of balls that we are able to put in each box. Empty box is allowed when I distribute the balls.

So... how many possibility of distributing $(j\cdot D)$ balls into $N$ boxes? I'm stuck on this problem.

-
are the balls numbered, or are we just interested in the number of balls in each box? That is is $\boxed{123}\boxed{45}\boxed{6}$ the same as $\boxed{246}\boxed{13}\boxed{5}$? – robjohn Jan 14 at 9:37

First, recall the soluction of the simpler problem without the maximum restriction (the answer for that is $N + jD -1 \choose N$). This can be obtained by noting that for one box there is always only one configuration (put all the balls in the box) which I denote $S_{1, k} = 1$. For two boxes, if you put $m$ balls in the first box, the number of balls in the second one is fixed and so the answer is $N+1$, so this can be regarded as a sum over the number of solutions for one box. In general for $N$ boxes you obtain the answer as an $N$-fold convolution of the constant function $S_{1,k}$. In particular, for all $N$ the answer is a polynomial in $k$.
For your problem, the solution is similar. I'll denote by $T^D_{N, k}$ the number of ways of putting $k$ balls into $N$ boxes with $D - 1$ maximum of balls in one box. Then $T^D_{1, k} = 1_{k < D}$ (i.e. 1 when $k$ is less than $D$). Now, observe that $T^D_{N,k} = S_{N,k}$ when $k < D$ (since in this range the maximum condition does not apply). Therefore, the $T^D_{N,k}$ for $N$ fixed looks again like a polynomial of degree $N-1$. But at $k=jD$ there is a discontinuity in the $(N-1)^{st}$ derivative corresponding to the maximum being hit. The graph looks like this for $D=6$:
So, what actually happens here is that we are summing the i.i.d random variables with uniform distribution. As a result, for $N \to \infty$ this approaches a normal distribution by the central limit theorem.
 I just realized that you only want the answer for $k = jD$, i.e. at the points of discontinuity. This is a simpler question than the one for which I posted the answer, so a closed-form solution might be possible. I'll leave my answer here for the time being anyway though. – Marek Jan 14 at 10:28
Exists$$\sum_{\stackrel{ c_{0}+c_{1}+...+c_{ N-1}=jD}{0\leq c_{i}\leq D-1,i=0,1,..,N-1}} \frac {(jD)!}{c_{0}!c_{1}!...c_{N-1}!}$$ possibility of distributing $(j\cdot D)$ distinct balls into $N$ boxes, if boxes are ordered and there exists some empty boxes. If empty boxes not allowed then we use $$\sum_{\stackrel{ c_{0}+c_{1}+...+c_{ N-1}=jD}{1\leq c_{i}\leq D-1,i=0,1,..,N-1}} \frac {(jD)!}{c_{0}!c_{1}!...c_{N-1}!}$$