Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
add comment

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

share|improve this answer
add comment

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$:

enter image description here

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.

share|improve this answer
    
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
add comment

${\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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.