0
$\begingroup$

How do I calculate the number of options for $k$ different balls in $n$ cells, with at least $1$ ball in each cell?

Lets say $6$ different balls in $3$ different cells, with at least $1$ ball in each cell.

like this: $$x_1+x_2+x_3 = 6$$

I would like to see an explanation please and not just the answer.

Thanks!

$\endgroup$
  • $\begingroup$ See Theorem 1 and its proof on the linked page. $\endgroup$ – N. F. Taussig Aug 18 '19 at 18:06
  • $\begingroup$ Thanks, but the theorom 1 relate to balls (starts) that are NOT distinguishable. I intended that the balls and the cells are different. different balls, different cells. $\endgroup$ – Alon Aug 18 '19 at 18:22
  • $\begingroup$ Sorry about that. When somebody writes $x_1 + x_2 + x_3 = 6$, I immediately think about identical balls in distinct boxes. I will address your question about distinct balls in distinct boxes. $\endgroup$ – N. F. Taussig Aug 18 '19 at 18:32
0
$\begingroup$

In how many ways can six distinct balls be placed in three boxes if at least one ball is placed in each box?

There are three choices for each of the six balls, so there are $3^6$ ways to place the balls without restriction. From these, we must subtract those distributions in which one or more of the boxes is left empty. To do so, we use the Inclusion-Exclusion Principle.

There are three ways to exclude one of the boxes from receiving a ball and $2^6$ ways to distribute the balls to the remaining boxes. Thus, there are $\binom{3}{1}2^6$ ways to exclude one of the boxes from receiving a ball.

However, if we subtract this amount from the total, we will have subtracted those cases in which two boxes are left empty twice, once for each way we could have designated one of those boxes as the box that is left empty. We only want to subtract them once, so we must add them back.

There are three ways to exclude two of the three boxes and one way to place all the balls in the remaining box.

Hence, there are $$3^6 - \binom{3}{1}2^6 + \binom{3}{2}1^6$$ ways to distribute six distinct balls to three distinct boxes so that at least one ball is placed in each box.

In how many ways can $k$ distinct balls be placed in $n$ distinct boxes if at least one ball is placed in each box?

Since there are $n$ choices for each of the $k$ balls, there are $n^k$ ways to distribute the balls without restriction.

There are $\binom{n}{i}$ ways to exclude $i$ of the $n$ boxes from receiving a ball and $(n - i)^k$ ways to distribute $k$ balls to the remaining $n - i$ boxes. Thus, by the Inclusion-Exclusion Principle, the number of ways to place $k$ distinct balls in $n$ distinct boxes is $$\sum_{i = 0}^{n} (-1)^i\binom{n}{i}(n - i)^k$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We really finally solved this way, thanks you and all very much! $\endgroup$ – Alon Aug 18 '19 at 18:50
  • $\begingroup$ But you could write it shorter - sorry for the complains... we just solved it and explained it shorter thats all. thank you! $\endgroup$ – Alon Aug 18 '19 at 18:50
0
$\begingroup$

For a detailed description of all the cases, please see Distributing Balls into Boxes

Your problem is covered by Theorem $5$, Case $2$. Applying the formula on page $3$, the answer in this case would be $540$. Please check the calculations.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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