I have $m$ balls and $n$ bins. I would like to find the number of all possible combinations of putting the balls into the bins including empty assignments, i.e., a bin maybe empty (see the example below).
For example, for $m=n=2$, I found:
1 x bin 1 contains ball 1, bin 2 contains nothing.
x 1 bin 1 contains nothing, bin 2 contains ball 1.
2 x bin 1 contains ball 2, bin 2 contains nothing.
x 2 bin 1 contains nothing, bin 2 contains ball 2.
1,2 x bin 1 contains balls 1 and 2, bin 2 contains nothing.
x 1,2 bin 1 contains nothing, bin 2 contains balls 1 and 2.
1 2 bin 1 contains ball 1, bin 2 contains ball 2.
2 1 bin 1 contains ball 2, bin 2 contains ball 1.
x x bin 1 contains nothing, bin 2 contains nothing.
So, I got $9$ combinations.
For $n=2$ and $m=3$, I got $27$ combinations. Thus, I suppose there are $$(n+1)^m,$$ combinations.
How to prove this? Is this known somewhere?
Another Problem: Suppose now we have an additional constraint: each ball can go to only a subset of the bins, i.e., ball $i$ can be put into bins $S_i\subseteq\{1,2,\ldots,n\}$. How many ways to assign the balls into the bins $S_1, S_2, \ldots, S_m$ including empty assignments?
Best Answer
You might have wanted to word the question a bit more clearly. We're not quite counting the number of ways to put $m$ balls into $n$ bins, because, judging by your example, we allow for the possibility that a ball does not end up in a bin at all.
We can identify each way of doing this as a function $f:[m] \to [n] \cup \{\varnothing\}$ where $f(k) = j$ iff ball $k$ is in bin $j$, and $f(k) = \varnothing$ if ball $k$ does not end up in a bin. This works out to $|[n] \cup \{\varnothing\}|^{|[m]|} = (n+1)^m$.
Edit: to address your second question, the answer is simply $$\prod_{i=1}^{m} (1 + |S_i|)$$ by a straightforward combinatorial argument. Namely, for each ball $i$ we have $1 + |S_i|$ choices, including the empty assignment.