3
$\begingroup$

Suppose there are $20$ kids. $10$ boys and $10$ girls.

What is the probability that the kids will arrange in this way: the circle will include exactly $5$ separate couples of girls and between each $2$ girls couple there will be at least one boy.

What I tried to do is to separate the kids to $10$ groups The first $5$ groups will be groups of $3$ people - $2$ girls and a boy where the boy sits on the right and the girls in the middle and left. And other $5$ groups will include only one boy in each group. Then we have $(10-1)!$ permutations of the arrangements of the groups in the circle. Then I include the internal permutations of each group For the first group I have a choice of $10 \choose 2$ and $10\choose1$ for the boy, and the also multiply by the number of different arrangments inside the group - $2$ and thus we have ${10 \choose 2}{10 \choose 1}2 $ for the first group, ${8 \choose 2}{9 \choose 1}2$ for the second group until the last group (${2 \choose 2}{6 \choose 1}2 $) And for the boys we add ${5 \choose 1}{4 \choose 1}{3 \choose 1}{2 \choose 1}{1 \choose 1}$ Since we have $(20-1)!$ permutations of all the kids in the circle then the desired probability should be $$\frac{9!{10 \choose {2,2,2,2,2}}{2^5}{10!}}{19!}$$ What is the problem in my logic?

$\endgroup$
1
$\begingroup$

It looks like you have arranged the boys twice, once when you arrange the groups and once when you select which boy is in which group. In my solution, I decide where the boys will be placed, then arrange them in the chosen seats.

Suppose Anne is one of the girls. Seat her first. There are $19!$ ways to arrange the remaining $19$ children as we proceed clockwise around the table.

As for the favorable cases, there are two ways to choose on which side of Anne another girl will sit. Once that choice is made, the positions of the girls are determined by how many boys sit between each pair of girls. Let $x_k$ be the number of boys in the $k$th group to Anne's left as we proceed clockwise around the table. There must be five such groups, one to the left of each pair of girls. Thus, $$x_1 + x_2 + x_3 + x_4 + x_5 = 10 \tag{1}$$ Since there must be at least one boy between each pair of girls, equation 1 is an equation in the positive integers. A particular solution of equation 1 corresponds to the placement of four addition signs in the nine spaces between successive ones in a row of $10$ ones. $$1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1 \square 1$$
For instance, the choice $$1 1 + 1 1 1 + 1 + 1 + 1 1 1$$ corresponds to the solution $x_1 = 2$, $x_2 = 3$, $x_3 = x_4 = 1$, and $x_5 = 3$. The number of solutions of equation 1 in the positive integers is the number of ways we can select four of the nine spaces between successive ones in a row of ten ones, which is $$\binom{9}{4}$$ Once the seats for the boys have been selected, they can be arranged in those $10$ seats in $10!$ ways as we proceed clockwise around the circle from Anne. The remaining girls can be seated in $9!$ ways as we proceed clockwise around the circle from Anne. Hence, the number of favorable cases is $$2\binom{9}{4}10!9!$$ giving a probability of $$\frac{2\binom{9}{4}10!9!}{19!}$$

$\endgroup$
  • $\begingroup$ @ChristianBlatter Thank you for catching the error, which I have now corrected. $\endgroup$ – N. F. Taussig Mar 7 '18 at 13:57
0
$\begingroup$

I think you're overcounting because of calculating all the permutations in the circle as well as multiplying afterwards ${5 \choose 1}{4 \choose 1}{3 \choose 1}{2 \choose 1}{1 \choose 1}$ for each of the boys.

To see why this is the case, let's label our groups as $ G_1, G_2, B_1$, followed by $G_3, G_4, B_2$, and so on... up to $G_9, G_{10}, B_5$ and having the remaining groups be $B_6$ and $B_7$ up to $B_{10}$.

One of the $9!$ permutations you list has the following sequence of people in it: $B_6, B_7, G_1, G_2, B_1$ and the remaining 15 kids are in some order. Consider another permutation which has $B_7, B_6, G_1, G_2, B_1$, and the remaining 15 kids in the same order as the previous permutation.

Now note that when you're considering the ${5 \choose 1}{4 \choose 1}{3 \choose 1}{2 \choose 1}{1 \choose 1}$ for assigning each of the single group boys to $B_7, B_6, B_8, B_9, B_10$, in one possible assignment, you'll have Boy 6 be Alex and Boy 7 be Joe and in another assignment, you can have Boy 6 be Joe and Boy 7 be Alex.

In the case that Boy 6 is Alex and Boy 7 is Joe, consider the first permutation presented, which was: $B_6, B_7, G_1, G_2, B_1$. This will end up being Alex, Joe, $G_1, G_2, B_1$ followed by the 15 other kids in some set order. Now consider the case that Boy 6 is Joe and Boy 7 is Alex, and consider the second permutation presented, which was: $B_7, B_6, G_1, G_2, B_1$. This will also end up being Alex, Joe, $G_1, G_2, B_1$ followed by the 15 other kids in the same set order, which shows that you're overcounting.

I'm not yet sure if that's the only flaw in your logic, and I'll continue working on this to see if I find any others.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.