1
$\begingroup$

I came across the following problem and the answer to that problem:

Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, $(1,2,3)$ and $(3,2,1)$ are considered the same.

As an example, if $m = 3$ and $n = 2$, you should return 2, since there are two possibilities: $(1,2)$ and $(3,0)$.

Here is a recurrence which seems to work: $$ f(m,n) = \begin{cases} 1 & \text{if } m = 0 \text{ or } n = 1 \\ f(m,m) & \text{if } n > m \\ f(m,n-1) + f(m-n, n) & \text{if } 1 < n \leq m \end{cases} $$

This solution seem to work. However I don't understand how $f(m,n-1) + f(m-n,n)$ works. Why is it considering $m-n$ balls into $n$ bins?

$\endgroup$
1
$\begingroup$

An assignment of balls into $n$ bins falls into either one of the following two cases.

  • Every bin has as last one ball. So let us assign one ball to each bin first. What remains to do is to assign the remaining balls to the bins.
  • Otherwise. That is, there is at least one bin that has no ball. This case is the same as assigning all balls into $n-1$ bins.

Exercise. Verify that we are counting without duplicates and without missing assignment.

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