1
$\begingroup$

In how many ways can you divide $25$ people with the name A-Y into $5$ identical non-empty boxes if A is not allowed to end up in the same group as any of B, C or D?

I used sterlings number but I am not sure if I am correct. Here is my solution

Total = $S(25,5)$ case $1$: ABCD are in the same group, which means we can count them as one, so we have $S(22,5)$ case $2$: A is in the same group as 2 so $S(23,5)* C(3,2)$ case $3$: A is with one so $S(24,5)* C(3,1)$ Answer= Total - (case $1$ + case $2$ + case $3$) = Am I correct because my friend solved it in another way I don't understand and got a different answer.

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

We do not want such cases : $\{A,B\}$ or $\{A,C\}$ or $\{A,D\}$ . Hence , we must subtract them from the total solution , as you said. However , the missing part in your solution is to use Principle of Inclusion-Exclusion.

  • The number of distribution of $25$ people into $5$ non-empty identical boxes : $S(25,5)$ or $$\frac{25![x^{25}][ (e^x -1)^5]}{5!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ and $B$ are together : $$\frac{23![x^{23}][e^x (e^x -1)^4]}{4!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ and $C$ are together : $$\frac{23![x^{23}][e^x (e^x -1)^4]}{4!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ and $D$ are together : $$\frac{23![x^{23}][e^x (e^x -1)^4]}{4!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ ,$B$ ,$C$ are together : $$\frac{22![x^{22}][e^x (e^x -1)^4]}{4!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ ,$B$ ,$D$ are together : $$\frac{22![x^{22}][e^x (e^x -1)^4]}{4!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ ,$C$ ,$D$ are together : $$\frac{22![x^{22}][e^x (e^x -1)^4]}{4!}$$

  • The number of distribution of $25$ people into $5$ non-empty identical boxes when $A$ ,$B$ ,$C$ ,$D$ are together : $$\frac{21![x^{21}][e^x (e^x -1)^4]}{4!}$$

By P.I.E: $$\frac{25![x^{25}][e^x (e^x -1)^4]}{4!}- 3\bigg(\frac{23![x^{23}][e^x (e^x -1)^4]}{4!}\bigg)+3\bigg(\frac{22![x^{22}][e^x (e^x -1)^4]}{4!}\bigg)-\bigg(\frac{21![x^{21}][e^x (e^x -1)^4]}{4!}\bigg)$$

$\endgroup$
5
  • $\begingroup$ Sorry but I have never seen this way of rewriting S(25, 5) as 25![x25][(ex−1)5]/5! I thought sterling only had a recursive formula but anyways would you mind explaining that tho? $\endgroup$
    – First_1st
    Commented Oct 12, 2022 at 19:33
  • $\begingroup$ @First_1st the form is called generating function (actually it is exponential generating function ). It is so wide topic to talk here $\endgroup$
    – Not a Salmon Fish
    Commented Oct 12, 2022 at 19:43
  • $\begingroup$ but did you do the same thing as me but instead you used this formula? Or what is it i did wrong if we look at my solution. $\endgroup$
    – First_1st
    Commented Oct 12, 2022 at 22:25
  • $\begingroup$ I believe that (1) it can easily be solved without PIE, (2) if PIE is to be used, the denominator in your expressions should remain 5! $\endgroup$
    – true blue anil
    Commented Oct 20, 2022 at 6:14
  • $\begingroup$ @trueblueanil $5!$ is wrong in denominator , because we made them identical boxes but there are two types of dstribution in numerator $e^x$ and $(e^x -1)$ , so it is $4!$. Actually they are $4! \times 1!$ $\endgroup$
    – Not a Salmon Fish
    Commented Oct 20, 2022 at 8:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .