I was going through the combinatorial problem finding number of ways to distribute $n$ distinguishable items to $r$ distinguishable groups. It turns out to be $r!S(n,r)$, where $S(n,r)$ is a Stirlings number of second kind. I got how it came. I realized that the whole solution is not taking into consideration the order of distribution. At first I didn't get why so. But after little bit of more thinking, I realized that Stirlings number is doing nothing but applying principle of inclusion and exclusion in series form. And principle of inclusion and exclusion does not take into consideration the order as it is applied in case of combinations/selections but not in case of permutations. Q1. Is it the reason we don't consider the order of distribution here?
Q2. Isn't it technically possible to take order of distribution too into consideration? For example, above distribution can be proves as follows:
- There are $(r-0)^n$ ways to distribute $n$ items to $r$ groups such that every one will get at least one item (no one get zero items which can be selected in ${}^rC_0=1$ ways).
- There are $(r-1)^n$ ways to distribute $n$ items to $(r-1)$ groups such that one group does not get any item which can be selected in ${}^rC_1$.
- There are $(r-2)^n$ ways to distribute $n$ items to $(r-2)$ groups such that two groups do not get any item which can be selected in ${}^rC_2$.
- And so on.
- There are $(r-r)^n=0$ ways to distribute $n$ items to $(r-r)=0$ groups such that no group get any item which can be selected in ${}^rC_r$.
By the principle of inclusion and exclusion, the desired count is
$${}^rC_0(r-0)^n-{}^rC_1(r-1)^n+{}^rC_2(r-2)^n-...\pm {}^rC_r(r-r)^n\hspace{1 cm}...(I)$$
$$=(-1)^0\times{}^rC_0(r-0)^n+(-1)^1\times{}^rC_1(r-1)^n+(-1)^2\times{}^rC_2(r-2)^n-...+(-1)^r\times{}^rC_r(r-r)^n$$
$$=\Sigma_{i=0}^r(-1)^i\times{}^rC_i(r-i)^n$$
$$=r!\frac{1}{r!}\Sigma_{i=0}^r(-1)^i\times{}^rC_i(r-i)^n$$
$$=r!S(n,r)$$
If here we have to take order into consideration, then equation $(I)$ would have been
$${}^rC_0(r-0)^n\color{red}{r!}-{}^rC_1(r-1)^n\color{red}{(r-1)!}+{}^rC_2(r-2)^n\color{red}{(r-2)!}-...\pm {}^rC_r(r-r)^n\color{red}{(r-r)!}$$
Am I correct with this?
Q3. If I am correct in Q2, why no one talks about principle of inclusion-exclusion or distribution of distinguishable objects to distinguishable groups with distribution (or selection) order into consideration? (I almost never came across such problem)