|
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. |
|||||
|
|
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. |
||||
|
|
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}!}$$ |
||||
|
|
