1
$\begingroup$

The full questions:

How can I distribute $n$ distinguishable items to $r$ indistinguishable groups such that

  • items can be repeated
  • no item should be left undistributed
  • each group can contain zero or more items

I want to know if there can be any closed formula or summation series which can give the total number of distributions possible in above case.

An example of distribution

Let $n=3$. Items $=\{1,2,3\}$ and $r=2$

The distributions are:

| 123 |     | No number is repeated hence forth
| 1   | 23  |
| 12  | 3   |
| 13  | 2   |
| 123 | 1   | One number is repeated hence forth
| 123 | 2   |
| 123 | 3   |
| 12  | 23  |
| 13  | 23  |
| 12  | 13  |
| 123 | 23  | Two numbers are repeated hence forth
| 12  | 123 |
| 13  | 123 |
| 123 | 123 | All three numbers are repeated
$\endgroup$
1
$\begingroup$

Partial answer covering only the case of $r=2$ for now:

Assume without loss of generality that the items are the numbers $\{1,2,3,\dots,n\}$

Looking at the case for $r=2$ for now, notice that with the exception of the case where all numbers appear in both groups there would be some smallest number such that it appears in only one of the groups. Let that number be called $k$. Note that $k$ can range from $1$ to $n$.

All numbers less than $k$ will appear in both groups since $k$ is the smallest number that appears in only one of the groups. Each of the numbers greater than $k$ will have three options: either they appear only in the group with $k$, they appear only in the group without $k$, or they appear in both groups.

Applying multiplication principle and ranging over all possible values of $k$ and remembering the case where all numbers can appear in both groups, we get a total number of arrangements as

$$1+\sum\limits_{k=1}^n 3^{n-k}=1+\frac{1}{2}(3^n-1)$$

As a check, by plugging in $n=3$ we do arrive at $1+\frac{1}{2}(3^3-1)=14$ arrangements.

$\endgroup$
  • $\begingroup$ I have to admit this was creative approach I never seen in counting. Also was guessing what I can replace that $3$ with in order to generalize this solution for any $r$. Also can there be any other generalized solution... $\endgroup$ – anir Apr 22 '18 at 16:37

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.