# 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 '13 at 9:37

## 4 Answers

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

-

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 '13 at 10:28

${\large\mbox{Starting from}}$ @Adi Dani ${\large answer}$

\begin{align} & ? \equiv \sum_{\stackrel{c_{0}\ +\ c_{1}\ +\ \cdots\ +\ c_{N-1} = jD} {\vphantom{\Large A}1\ \leq c_{i}\ \leq D-1,\ i = 0, 1, \ldots, N\ -\ 1}} \frac {(jD)!}{c_{0}!c_{1}!...c_{N-1}!} \\[3mm]&= \sum_{\vphantom{\Large A}1\ \leq\ c_{i}\ \leq\ D - 1 \atop \vphantom{\Huge A} i = 0, 1,.., N - 1} \frac {(jD)!}{c_{0}!\,c_{1}!\,\ldots\,c_{N-1}!} \oint_{\left\vert z\right\vert = 1}{{\rm d}z \over 2\pi{\rm i}}\,{1 \over z} {1 \over z^{c_{0}\ +\ c_{1}\ +\ \cdots\ +\ c_{N-1}\ -\ jD}} \\[3mm]&= \left(jD\right)! \oint_{\left\vert z\right\vert = 1}{{\rm d}z \over 2\pi{\rm i}}\, {1 \over z^{1\ -\ jD}} \left\lbrack% \sum_{c = 1}^{D - 1}{\left(z^{-1}\right)^{c} \over c!}% \right\rbrack^{N} = \left(jD\right)! \oint_{\left\vert z\right\vert = 1}{{\rm d}z \over 2\pi{\rm i}}\,{1 \over z}\, z^{\,jD}\,{\rm f}_{N,D}\left(1 \over z\right) \end{align}

$\displaystyle{% \quad\mbox{where} \quad {\rm f}_{N,D}\left(z\right) \equiv \phi_{D}^{N}\left(z\right)\,, \quad \phi_{D}\left(z\right) \equiv \sum_{c = 1}^{D - 1}{z^{c} \over c!}}$.

\begin{align} ? &= \left(jD\right)! \oint_{\left\vert z\right\vert = 1}{{\rm d}z \over 2\pi{\rm i}}\,{1 \over z}\, z^{\,jD}\phantom{A} \sum_{n = N}^{N\left(D\ -\ 1\right)} {{\rm f}_{N,D}^{\left(n\right)}\left(0\right) \over n!}\, \left(1 \over z\right)^{n} = {\Large {\rm f}_{N,D}^{\left(jD\right)}\left(0\right)} \end{align} However, $\displaystyle{\ \ % {\rm f}_{N,D}'\left(z\right) = N\phi_{D}^{N - 1}\left(z\right)\phi_{D}'\left(z\right) = N\,{\rm f}_{N - 1,D}\left(z\right)\,\phi'\left(z\right)}$ and \begin{align} {\rm f}_{N,D}^{\left(jD\right)}\left(0\right) &= N\sum_{\ell = 0}^{jD - 1}{jD - 1\choose \ell} {\rm f}_{N - 1,D}^{\left(jD - 1 - \ell\right)}\left(0\right)\ \phi^{\left(\ell + 1\right)}\left(0\right) \\[3mm]&= N\sum_{\ell = 0}^{M}{jD - 1\choose \ell} {\rm f}_{N - 1,D}^{\left(jD - 1 - \ell\right)}\left(0\right)\,, \qquad M \equiv \min\left\lbrace jD - 1,D - 2\right\rbrace \end{align}

${\rm f}_{N,D}^{\left(jD\right)}\left(0\right)$ is calculated recursively.

-

The question isn't very clear about whether the balls are numbered or indistinguishable. In this answer, I will assume the boxes are ordered but the balls are indistinguishable. i.e. we only care about the number of balls in each boxes. WOLOG, we will also assume $j \le N$ or the answer will be trivially zero.

For each admissible configuration of putting $c_1$ balls into $1^{st}$ box, $c_2$ balls into $2^{nd}$ box and so on, one can associate with it a monomial in $N$ indeterminates $t_1, t_2,\ldots,t_N$:

$$(c_1, c_2, \ldots, c_N) \quad\mapsto\quad t_1^{c_1} t_2^{c_2} \ldots t_n^{c_N} \in \mathbb{Z}[t_1,t_2,\ldots,t_N]$$

One can see this correspondence is one to one. The collection of all possible ways of placing at most $D\!-\!1$ balls into $N$ boxes can be described/summarized by a single polynomial:

$$(1+t_1+t_1^2 + \ldots + t_1^{D-1})(1+t_2+t_2^2 + \ldots + t_2^{D-1})\cdots (1+t_N+t_N^2 + \ldots + t_N^{D-1})$$

If one replace all these $N$ determinates $t_i$ by a single indeterminate $t$, the above correspondence allow us to read off $\mathscr{N}_{jD}$, the number of ways of placing $jD$ balls into $N$ boxes subject to the constraint, as the coefficients of $t^{jD}$ in the polynomial:

$$(1+t+\ldots+t^{D-1})^N = \left( \frac{1-t^D}{1-t} \right)^N$$

Let us use the notation $[t^e](\cdots)$ as a short hand for extracting the coefficient of $t^e$ from any formal power series $(\ldots)$ in $t$.

Notice $\displaystyle\quad (1-t^D)^N = \sum_{r=0}^N (-1)^r \binom{N}{r} t^{rD},\quad$ we have: $$\mathscr{N}_{jD} = [t^{jD}] \left( \sum_{r=0}^N (-1)^r \binom{N}{r} t^{rD} \right)(1-t)^{-N} = \sum_{r=0}^j (-1)^r \binom{N}{r} [ t^{(j-r)D} ] (1-t)^{-N}$$

Since $\displaystyle \quad (1-t)^{-N} = \sum_{s=0}^{\infty} \binom{N+s-1}{s} t^s, \quad$ we can further simplify $N_{jD}$ and get $$\mathscr{N}_{jD} = \sum_{r=0}^j (-1)^r \binom{N}{r} \binom{N+(j-r)D-1}{(j-r)D} = \sum_{r=0}^j (-1)^{j-r} \binom{N}{j-r} \binom{N+rD-1}{rD}$$

-