2
$\begingroup$

How many ways are there to distribute $N$ ($N$ is an even number) indistinguishable balls into $n$ distinguishable boxes if each box can contain at most $\frac{N}{2}$ balls. My solution:

There are $${N+n-1}\choose{n-1}$$

different ways to distribute $N$ indistinguishable balls into $n$ distinguishable boxes. But we must subtract the number of those cases in which there are more than $\frac{N}{2}$ balls in one of the boxes.

If we put $\frac{N}{2}+1$ balls in the first box we get

$${\frac{N}{2}-1+n-2}\choose{n-2}$$ different ways to distribute $\frac{N}{2}-1$ balls into the boxes $2,\cdots , n$

Similary, for the case where we have $\frac{N}{2}+j$ balls in (exactly) one on the boxes, $j=1,..., \frac{N}{2}$ we get the formula $${\frac{N}{2}-j+n-2}\choose{n-2}$$. Then, the answer is

$${{N+n-1}\choose{n-1}}-n\sum_{j=1}^{\frac{N}{2}}{{\frac{N}{2}-j+n-2}\choose{n-2}}$$

$\endgroup$
2
  • $\begingroup$ Please add more info/your own effort and any simplifications you've achieved. Otherwise it gives an impression that you just want us to do your work for you. $\endgroup$
    – Arkady
    Commented Sep 12, 2017 at 20:56
  • $\begingroup$ Ravi, the problem is that I don't know how to begin. The stars and bars approach doesn't work. $\endgroup$
    – Doudou
    Commented Sep 13, 2017 at 11:40

1 Answer 1

2
$\begingroup$

Since $N$ is even, let $N = 2k$. Then the question can be rephrased as follows: In how many ways can $2k$ indistinguishable balls be placed in $n$ boxes if at most $k$ balls can be placed in one box?

Clearly, $n \geq 2$, for otherwise we would not be able to distribute all the balls to the boxes given the restriction that at most $k$ balls may be placed in one box.

The number of ways of placing $2k$ balls in $n$ boxes is the number of solutions of the equation $$x_1 + x_2 + x_3 + \ldots + x_n = 2k \tag{1}$$ in the nonnegative integers. Since a particular solution of equation 1 corresponds to the placement of $n - 1$ addition signs in a row of $2k$ ones, equation 1 has $$\binom{2k + n - 1}{n - 1}$$ solutions since we must choose which of the $2k + n - 1$ positions (for $2k$ ones and $n - 1$ addition signs) will be filled with addition signs.

From these, we must exclude those cases in which one box receives more than $k$ balls. Notice that there can be at most one such box since $2(k + 1) = 2k + 2 > 2k = N$.

Suppose that box 1 contains more than $k$ balls. Then $x_1' = x_1 - (k + 1)$ is a nonnegative integer. Substituting $x_1' + k + 1$ for $x_1$ in equation 1 yields \begin{align*} x_1' + k + 1 + x_2 + x_3 + \ldots + x_n & = 2k\\ x_1' + x_2 + x_3 + \ldots + x_n & = k - 1 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{k - 1 + n - 1}{n - 1} = \binom{n + k - 2}{n - 1}$$ solutions. By symmetry, there are an equal number of solutions of equation 1 for each of the $n$ variables that could exceed $k$. Hence, we must exclude $$n\binom{n + k - 2}{n - 1}$$ solutions.

Consequently, there are $$\binom{2k + n - 1}{n - 1} - n\binom{n + k - 2}{n - 1}$$ ways to distribute $N = 2k$ indistinguishable balls to $n$ boxes if no box can contain more than $N/2 = k$ balls.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .