Distribution into different groups if blank groups are not permissible

509 Views Asked by At
  1. The number of ways in which $n$ different things can be distributed into $r$ different groups if blank groups are not allowed is: $r^n-{}^rC_1(r-1)^n+{}^rC_2(r-2)^n-\cdots+(-1)^{r-1}.{}^rC_{r-1}$

  2. The number of ways in which $n$ identical things can be distributed into $r$ different groups is: ${}^{n-1}C_{r-1}$ according as blank groups are not admissible.

  3. The number of ways in which $n$ different things can be arranged into $r$ groups is $n!.{}^{n-1}C_{r-1}$ if blank groups are not admissible.

These are the statements found in my reference. Similar questions have been asked before so it is highly likely to be a duplicate. So I will try to be as specific as possible about my doubts.

My Understanding

Statement 1: It is similar to finding number of onto function. We need to find the number of ways to partition $n$ objects into $r$ groups and multiply by $n!$, ie. $n!.S(n,r)$, where $S(n,r)$ is the Stirling numbers of second kind. All derived from Inclusion-Exclusion principle.

Statement 2 and 3: A good explanation can be found at How to deduce the formula for arrangement in groups? It looks like ${}^{n-1}C_{r-1}$ counts the number of ways $n$ things can be partitioned into $r$ groups.

What is the difference between statements 1 and 3 ?

To me it seems like the Stirling numbers $\color{red}{S(n,r)}$ counts the number of partition of $n$ distinct objects into $r$ groups, whilst $\color{red}{{}^{n-1}C_{r-1}}$ counts the number of partition of $n$ identical objects into $r$ groups. Even if thats the case, still $\color{red}{n!.{}^{n-1}C_{r-1}}$ makes no sense to me.

Example: $n=4$ identical elements can be distributed into $r=3$ groups, in ${}^{n-1}C_{r-1}={}^{3}C_{2}=3$ ways, if blank groups are not allowed.

ident

Example: $n=4$ distinct elements can be distributed into $r=3$ groups, in $S(4,3)=6$ ways, if blank groups are not allowed.

stirling

In this example, as per statement 3, $n!.{}^{n-1}C_{r-1}=4!.{}^{3}C_{2}=24.3$, right ?. What does it gives, don't understand ?

1

There are 1 best solutions below

6
On BEST ANSWER

The formulation of statement $3$ is quite unclear. Reverse-engineering from the result, we can surmise that the intended meaning (perhaps indicated by the word “arrange”, as opposed to “distribute” in the other two statements) is to count the linear arrangements of $n$ elements in $r$ groups. There are $n!$ different arrangements of the $n$ elements, and in each of them we can place separators in $r-1$ out of $n-1$ possible positions between the elements to divide the linear arrangement into $r$ groups, for a total of $n!\binom{n-1}{r-1}$ grouped arrangements.