# Simple combinatorics problem - assigning people to groups

$$20$$ people that A, B and C belong to are to be randomly seperated in groups of 4. I have a few questions about this problem:

Q1: What is the probability, that A, B and C place in the same group?
My intuition would be, that the person A has a $$4/20=1/5$$ chance to land in group 1 and then person B has a $$3/19$$ chance to land in the same group and finally person C has a $$2/18$$ chance to do the same. Because there are $$5$$ groups, this means that $$\mathbb{P}(Q1)=5\frac{1}{5}\frac{3}{19}\frac{2}{18}=\frac{1}{57}$$.

Q2: What is the probability that they all are placed in different groups?
Place person A in group $$a$$ (probability $$1/5$$). Then place person B in group $$b\neq a$$ - probability $$4/19$$. Finally place person C in group $$c\notin\{a,b\}$$ - probability $$4/18$$. There are $$\binom{5}{3}$$ ways to choose $$a,b,c$$, so $$\mathbb{P}(Q2)=\binom{5}{3}\frac{1}{5}\frac{4}{19}\frac{4}{18}$$
This somehow seems wrong to me, because it does not account for the other $$17$$ people.

Q3: What is the conditional probability, that A,B,C land in different groups if it is already known that two of them are in different groups?
This one I really struggle with. My attempt: Because there are three groups to choose from and $$18$$ people to match, I think that $$\mathbb{P}(Q3)=3\frac{4}{18}$$.

Please check my solutions and tell me what is wrong.

EDIT: Thank you to everyone for the discussion and solutions, especially to @chrslg for even throwing together a little simulation. Also, Q3 is for sure related to conditional probability, so $$\mathbb{P}(Q3)=\frac{\mathbb{P}(Q1)}{1-\mathbb{P}(Q2)}$$, as pointed out by you all.

$$\require{cancel}$$

What I consider the simplest approach is given below.

Consider $$20$$ slots in $$5$$ groups of $$4$$,

$$\quad\boxed{o o o o}\quad\boxed{o o o o}\quad\boxed{o o o o}\quad\boxed{o o o o}\quad\boxed{o o o o}$$

• (1) The first person can be anywhere, the remaining two can be placed in the same group with $$Pr =\frac{3}{19}\frac{2}{18} = \frac1{57}$$

• (2) The first person can be anywhere, the other two can be placed in different groups with $$Pr = \frac{16}{19}\frac{12}{18} = \frac{32}{57}$$

• (3) Two blocks are already occupied, $$12$$ "good" slots are available, $$\cancel{Pr =\frac {12}{18}}$$

Correction to part (3)

Since this is a conditional probability question,

$$Pr = \frac{All \;in \;different\; groups}{All \;not\; in\; same\; group} = \frac{32}{57}\big/\frac{56}{57} = \frac47$$

• I upvoted, since I struggled to write a similar answer explaining why accepted answer was incorrect for Q2. Your answer is. (Plus, it fits the result of a Monte-Carlo simulation I ran). Nevertheless, your (3) is the answer to "conditional probability that all 3 are in different group, knowing that A and B are in 2 different groups". The question could be interpreted that way I guess. But my understanding is that Q3 is "conditional probability that A,B,C are in different groups knowing that 2 of them, that is either A and B, or A and C or B and C, are in different groups" Commented Oct 1, 2022 at 19:41
• In other words, I think that considered cases for Q3 should not only be the 18 possibilities for C when A and B occupy 2 slots in different groups. But also the cases when A and B are in the same group, but C isn't. It is rather difficult to visualize with your (otherwise very efficient and clarifying) modelisation. Commented Oct 1, 2022 at 19:44
• @chrslg: The point is that you have already placed two in different groups. Whichever two you thus placed, there is just one unplaced person, it doesn't matter whether the person is $A,B,$ or $C$ Commented Oct 1, 2022 at 19:45
• I get that. That is not my point. Using your paradigm, Q3, for me, could be described that way: Commented Oct 1, 2022 at 19:49
• So, altogether, answer to Q3 is 16×12/(16×18+3×16) Commented Oct 1, 2022 at 19:54

Q3) I understand the question as "you already know that 2 of A,B,C are in different group. What is the probability that all 3 are in different group". So, calling $$k$$ the number of groups among which A,B and C are distributed $$P[k=3 | k\geq 2] = \frac{P[k=3\mbox{ and } k\geq 2]}{P[k\geq 2]}$$ Here, since there is no cases where all 3 of A,B,C are in different groups, but we can't find 2 of them that are in different groups (in other words, where $$k=3$$ but $$k<2$$), the computation simplify a little bit $$P[k=3 | k\geq 2] = \frac{P[k=3]}{P[k\geq2]}$$ @trueblueanil already computed $$P[k=3] = \frac{16×12}{19×18}$$
We just need to compute $$P[k\geq2]$$. In fact, we don't really need to (and that a virtue of writing a proper answer, because I only see that now. I wasn't seeing it while arguing in comments). Because we know that k has to be either 1, 2 or 3. And we know $$P[k=1]$$. That is the answer to Q1. $$P[k=1] = \frac{3×2}{19×18}$$ Hence $$P[k\geq 2] = 1-P[k=1] = 1-\frac{3x2}{19×18} = \frac{19×18-3×2}{19×18}$$ So, answer to Q3 is $$P[k=3 | k\geq 2] = \frac{P[k=3]}{P[k\geq 2]} = \frac{ \frac{16×12}{19×18} }{ \frac{19×18-3×2}{19×18} } = \frac{16×12}{19×18-3×2}$$ Since $19×18-3×2 = 16×18+3×16 = 336$$we are back to what I said in comments. Except that this time, I am pretty sure that this is the way it was intended by the teacher. Q3 answer is just a combination of Q1 and Q2. Classic teacher trick (being one myself...). All we had to do to answer Q3 was $$\frac{\mbox{answer to q2}}{1-\mbox{answer to q1}}$$ My initial reasoning was, from true blue anil slot system: arbitrarily choosing to place A in the first slot (we can do so. It is just a naming choice), we have $$16$$ ways to place B, and $$12$$ ways to place C to have all 3 in different groups. And to enumerate slots positioning leading to at least 2 of A,B,C in different groups, either: • B is in a different group than A (16 slots for B) and then C can be in any other slot • B is in the same group as A (3 other slots for B). Not a problem, but then C needs to be in another group (16 slots) Now, since I mentioned Monte-Carlo, here is my C code #include <stdio.h> #include <stdlib.h> int avail[20]; // Available slots (at first all 20) int nd=20; // Number of available slots int ga,gb,gc; // Groups for A, B, and C // Reset (nobody is placed) void init(){ // Just for debug, I choose not to name any slot 0. So if there is a 0, we have a bug // Initially all slots 1,2,3...,20 are available for(int i=1; i<=20; i++){ avail[i-1]=i; } nd=20; // That is 20 of them // A, B, C are placed nowhere ga=-1; gb=-1; gc=-1; } // Choose a person for each slot void distrib(){ // For all group, for all slot in all group for(int g=0; g<5; g++){ for(int i=0; i<4; i++){ // I choose a person among the nd still available int p=random()%nd; // To simplify a bit, I arbitrarily choose to place A (person 1) into 1st slot of 1st group // This is just a naming choice, so it changes nothing if((g==0) && (i==0)) { p=0; ga=g; } // If perso 2 (B) is chosen, store group in gb if(avail[p]==2) gb=g; // Likewise for (C) else if(avail[p]==3) gc=g; // At first I was litteraly distributing number into 5 arrays of 4 slots // But turns out I never used "group" in the rest of the code, so uneeded // group[g][i]=disp[p]; // p is not available any more. The last element from avail[0..nd[ takes is place // and we have one less element in avail[0..nd[ // (Just a fast way to remove an element from an array when we don't care of order) avail[p]=avail[nd-1]; avail[nd-1]=0; nd--; } } } int main(){ // Monte-Carlo simulation long long n=0; long long ndiff=0; long long nsame=0; long long nk2=0; for(;;){ // Reset and redistribution persons init(); distrib(); // Total number of cases n++; // Cases for which all are in the same group if((gb==ga) && (gc==ga)) nsame++; // Cases for which all 3 are in different groups if(ga!=gb && ga!=gc && gb!=gc) { ndiff++; } if(ga!=gb || ga!=gc || gb!=gc) nk2++; if(n%10000) continue; // Just to avoid having 99% of CPU only for writing result // Print result printf("n=%-8lld same=%lld %7.4f%% diff=%lld %7.4f%% cond=%lld/%lld %7.4f%%\r", n, nsame, (100.0*nsame)/n, ndiff, (100.0*ndiff)/n, ndiff, nk2, (100.0*ndiff)/nk2); } }  Let me know if you see any reasoning error in this (naive) simulation. (I know, there are lot of possible simplification. Some of them, just because I missed them. Some others because when I write such Monte-Carlo to check probability I avoid thinking too much, to be sure not to include bias) But well, that code is fast enough so that I need 64 bits integer to hold number of cases. And it leads to the same result I am defending. • You were right, my friend. (+1) Commented Oct 1, 2022 at 21:08 Your answer to the first question is correct. Q2: Any particular outcome has probability $$\frac{4!^5}{20!}$$, where $$n!=n\cdot(n-1)\cdots 1$$ is the factorial. The reason is that no matter what person you put in which group, you will fill up the 4 spots in the 5 groups one by one. Let's assume that A,B,C are the first three persons. Let us also fix groups $$a,b,c$$. Now, we can iterate through all possibilities where A ends up in $$a$$, B in $$b$$ and C in $$c$$. Since the probability of each outcome is the same, and equal to $$\frac{4!^5}{20!}$$, we only need to count the possible assignments of the remaining $$17$$ persons to groups, that is we have the letters $$d$$, $$e$$ four times, and the others three times, yielding $$\binom{17}{3,3,3,4,4}=\frac{17!}{3!^34!^2}$$, using the multinomial coefficient. Summing over these outcomes gives $$\binom{17}{3,3,3,4,4}\frac{4!^5}{20!}=\frac{4^3}{20\cdot 19\cdot 18}$$. Next, we sum over the choice of groups. Now, we have to choose one group for A, one for B and one for C, yielding $$\frac{5\cdot 4\cdot 3\cdot 4^3}{20\cdot 19\cdot 18}=\frac{32}{57}$$. Q3: There are several ways to consider to think of the conditional probability, in case of doubt one approach is always $$P(A|B)=P(A\cap B)/P(B)$$. In this case, the probability that all three land in different groups, and two of them land in different groups, well, is the probability that all three land in different groups (the former event is a subset of the latter, hence the intersection is the former). But this probability is exactly the probability from Q2. On the other hand, the complement of the event that there exist two that are in different groups, is the event that all three are in the same group, the event from Q1. Hence, the probability is $$\mathbb P(Q2)/(1-\mathbb P(Q_1))=\frac{57}{56}\frac{32}{57}=\frac{4}{7}$$. • Thank you, that really makes sense! Commented Oct 1, 2022 at 18:58 • I am not in agreement with you on parts two and three. Commented Oct 1, 2022 at 19:48 • Neither am I (although I am not in agreement on part three with true blue anil :-), my answer on Q3 is none of the 2 proposed ones) Commented Oct 1, 2022 at 20:01 • Thanks again! I use the approach with 20 slots, and four of each number$1$to$5$to put there. This gives$\binom{20}{4,4,4,4,4}$outcomes, as argued we have the uniform distribution. Correction for Q2 is: We can take any number for the first slot, any other for the second, and any of the remaining 3 numbers for the third, i.e. we draw without repetition and with order. The remainder works as described, i.e. distributing the remaining numbers with$\binom{17}{3,3,3,4,4}\$. Commented Oct 1, 2022 at 20:31