0
$\begingroup$

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"?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Does it turn out to be something like: $(2^n-1)^r-\underbrace{\binom{n}{n-1}(2^{n-1}-1)^r}_{\text{1 item does not get distributed}} +\underbrace{\binom{n}{n-2}(2^{n-2}-1)^r}_{\text{2 items does not get distributed}} - ... \pm\underbrace{\binom{n}{1}(2^{1}-1)^r}_{\text{n-1 items does not get distributed}}$$=\sum_{i=0}^{\color{red}{n-1}}(-1)^i\binom{n}{n-i}(2^{n-i}-1)^r$$=\sum_{i=0}^{\color{red}{n}}(-1)^i\binom{n}{n-i}(2^{n-i}-1)^r$. (click on the equation to align it one below other instead of one long like, dont know why chrome browser require this to be done) $\endgroup$ – anir Apr 12 '18 at 10:59
  • $\begingroup$ It looks like taking form of Sterling number (which happen for same above distribution conditions except repetitions are disallowed), except for $(2^{n-i}-1)$ $\endgroup$ – anir Apr 12 '18 at 11:01
  • $\begingroup$ Yes, your first comment is correct. $\endgroup$ – Ross Millikan Apr 12 '18 at 13:58

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.