1
$\begingroup$

How many options do we have to divide $k$ balls to $n$ cells if $k\geq n$ and:

CONDITION 1: Every cell will have at least one ball.

CONDITION 2: different $k$ balls, different $n$ cells, and there is significance to how we sort the balls in the cells.

Well, I divided the solution to two parts:

PART 1: if $k = n$, then we have $k!$ options.

PART 2: if $k > n$, then we put one ball to every cell, for that we have $k!$ options, and then we have left $k-n$ balls to divide to $n$ cells. which is $(k-n)^n$ options.

Then we sum it all: $k! + k!(k-n)^n$ options.

What do you guys think?

Btw, there's a BONUS question to that, what will be your answer if we change from different $n$ cells to, these $n$ cells are now identical.

Well, I believe it will be $\frac{k!}{k}$ for $k = n$, and will be $\frac {k! + k!(k-n)^n}{k}$ for $k > n$.

Thoughts?

$\endgroup$
1
$\begingroup$

The crucial thing is that order in the cells matters.

There are $k!$ ways to line up the balls. Now we want to insert separators into $n-1$ of the $k-1$ gaps between balls. This can be done in $\binom{k-1}{n-1}$ ways, for a total of $k!\binom{k-1}{n-1}$.

We leave it to you to collect the bonus. The answer to the first part will be useful.

$\endgroup$
  • $\begingroup$ I will review tomorrow a little bit more on the material before I accept your answer. I'm very confused with order matters/not and with identical and different cells etc. I will come back with questions if I don't understand. got like 7 courses apart from discrete :( $\endgroup$ – Ilan Aizelman WS Dec 12 '15 at 0:55
  • $\begingroup$ Overloaded! Yes, do ask questions. This question has an unusual character, since order in the cells matters. In most ball and urn counting problems you will meet, it doesn't. $\endgroup$ – André Nicolas Dec 12 '15 at 1:07
  • $\begingroup$ I still didn't get it 100%, but kinda got it. I'll ask my teacher to explain me further. About the Bonus, it is your answer and I need to divide it by (n-1)! ? $\endgroup$ – Ilan Aizelman WS Dec 15 '15 at 22:23
  • $\begingroup$ I think it is by $n!$. $\endgroup$ – André Nicolas Dec 15 '15 at 22:29
  • 1
    $\begingroup$ If there is no significance of the order in the cells? The problem in the OP explicitly says order in the cells is significant. The problem then becomes more complicated. We can use Inclusion/Exclusion. The answer will involve Stirling numbers of the second kind (for details please see Wikipedia). $\endgroup$ – André Nicolas Dec 16 '15 at 16:01

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.