I am struggling with finding closed form or even non-closed form of following count:
The number of ways for distributing $n$ distinguishable items to $n$ distinguishable groups, where
- order of distribution does not matters
- each cell gets at least one item
- an item can be distributed to multiple groups (i.e. repetition allowed)
- any item should not be left undistributed
I am able to come up with the count that disregards last point, i.e. any item should not be left undistributed:
Each group can get items in $\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}=2^n-1$ ways. There are $r$ groups. So final count will be $(2^n-1)^r$.
But how can accommodate last criteria: "any item should not be left undistributed"?
You deal with that by inclusion-exclusion. Start with your answer of $(2^n-1)^r$ and subtract the cases where an item is not distributed. If one item is not distributed, there are $(2^{n-1}-1)^r$ ways to distribute the rest, so subtract those out. Unfortunately, you have subtracted twice the cases where two items are not distributed, so you need to add them back in once. Now you will have counted the ones where three are not distributed once in the initial count, subtracted them three times, and added them three times, so subtract them once. Keep going.