2
$\begingroup$

I have just learnt some great things about using Stirlings number of 2nd kind to emulate inclusion exclusion principle to find distribution of distinguishable objects to distinguishable groups from the answer given on my question. Let me put it here again:

Number of distributions for distributing $n$ distinguishable items to $r$ distinguishable groups $=r!\begin{Bmatrix}n\\r \end{Bmatrix}$
$= r!\times \frac{1}{r!}\sum_{i=0}^{r}(-1)^{i}\binom{r}{i}(r-i)^n$
where $\begin{Bmatrix}n\\r \end{Bmatrix}$ is Stirling's number of second kind.

Now I also came across the fact that

Number of ways to distribute $n$ distinguishable items to $r$ indistinguishable groups is $\begin{Bmatrix}n\\r \end{Bmatrix}$

But now I feel a lot tangled about using inclusion exclusion for counting distribution of distinguishable items to indistinguishable groups.

Doubts

  1. Question 1
    So distinguishable-indistinguishable (DI) distribution lacks $r!$ in comparison to distinguishable-distinguishable (DD) distribution; i.e. $\begin{Bmatrix}n\\r \end{Bmatrix}$ versus $r!\begin{Bmatrix}n\\r \end{Bmatrix}$. Can we attribute this to the fact that it makes no sense to permute $r$ indistinguishable groups and hence striping away $r!$?
    My analysis
    The answer may be NO, because if we look at how we got $r!\begin{Bmatrix}n\\r \end{Bmatrix}$ for DD distribution, we can get that the final solution is $\sum_{i=0}^{r}(-1)^{i}\binom{r}{i}(r-i)^n$ which is obtained applying inclusion and exclusion. We express this solution as $r!\begin{Bmatrix}n\\r \end{Bmatrix}$ by multiplying it with $r!\frac{1}{r!}=1$ for convenience.

    Thus, the original solution does not contain multiplication by $r!$, but it exists out of need of mere convenience to express the solution in terms of Stirling number of second kind and it does not exist because it makes sense to permute $r$ distinguishable groups. As a result, we are not striping away $r!$ from DD distribution coutn to get DI distribution count merely because it does not makes sense to permute $r!$ indistinguishable groups.

    My Counter analysis
    Even though we have added $r!\frac{1}{r!}$ to the solution of DD distribution out of convenience to express the solution in terms of Stirling number, striping away $r!$ from it does still give us number of ways to perform DI distributions. It can be seen as again dividing DD distribution count by $r!$ to obtain DI distribution count: $\frac{1}{r!}r!\begin{Bmatrix}n\\r \end{Bmatrix}=\begin{Bmatrix}n\\r \end{Bmatrix}$, essentially striping away $r!$ from $r!\begin{Bmatrix}n\\r \end{Bmatrix}$

  2. Question 2
    If my couter analysis is correct, then I have more doubts:

    • Q2.1. Can we logically get DI distribution count formula only from DD distribution formula? That is, by first realizing number of DD distribution count is $r!\begin{Bmatrix}n\\r \end{Bmatrix}$ and then striping away $r!$? Cant we find the formula for DI distribution count directly from DD distribution logic (explained in Q2.2)?
    • Q2.2. It seems that inclusion exclusion can be applied only when groups are distinguishable (since intersections can only be formed by distinguishable groups). For example, in the standard inclusion exclusion venn diagram given below, the sets $A,B$ and $C$ are distinguishable. If they were same, we cannot apply inclusion exclusion to them, as there will not be any different groups to form intersections to include and exclude. Thus, is it possible to obtain DI distribution count without following inclusion exclusion principle or by modifying inclusion exclusion performed by Stirling number? Say for example eliminating $\binom{r}{i}$ in Stirling number as it does not makes sense to select $i$ groups out of $r$ when all groups are identical.
      enter image description here
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.