I want to distribute $n$ distinguishable items to $r$ distinguishable groups. However there are certain restrictions. Each group can have exactly one item. Items can be repeated. And no item can be left undistributed.
Since no item can be left undistributed, following should hold: $n\leq r$. For $n=r$, $n!$ is the desired count. I am struggling to come up with the closed formula for the desired count when $n<r$.
I applied following logic:
Without using inclusion and exclusion
Each of $n$ items will appear at least once. This will take up $n$ positions out of $r$ and can be done in $\binom{r}{n}n!$ ways. Remaining $(r-n)$ positions can be taken up by any items, which can be done $(r-n)^n$ ways. So I felt the final count will be $\binom{r}{n}n!(r-n)^n$. However this seems to count certain distributions multiple times. How can I refine this formula to get correct final count?Using inclusion and exclusion
- Count such that any number of items left undistributed is $n^r$.
- Count such that at least one item left undistributed is $\binom{n}{1}(n-1)^r$.
- Count such that at least two item left undistributed is $\binom{n}{2}(n-2)^r$.
- And so on.
- By inclusion exclusion, we can get final count as $\binom{n}{0}(n-0)^r-\binom{n}{1}(n-1)^r+\binom{n}{3}(n-3)^r-...\pm\binom{n}{n}(n-n)^r=\sum_{i=0}^n(-1)^i\binom{n}{i}(n-i)^r$
- Even this count is giving wrong answers when I tried out some examples. For $n=2,r=3$, by using this formula, I get $$\binom{2}{0}(2)^3-\binom{2}{1}(1)^3+\binom{2}{2}(0)^3=8-2+1=7$$ But when I manually enumerate it, I get only six:
{1,2,1},{2,1,2}
{1,2,2},{2,1,1}
{1,1,2},{2,2,1}
How can I refine this equation to give correct result?
Or am I completely wrong in both approaches?