3
$\begingroup$

How many ways are there to arrange 6 girls and 15 boys in a circle such that there are at least 2 boys between any 2 adjacent girls? Please help me how to proceed with this.

My approach:

Arrange first the girls in $5!$ ways, now we must choose $12$ boys from the $15$ in $15 \choose 12$ ways, and these boys will be arranged such that each girl has $2$ boys next to them in $12!$ Ways, then the remaining $3$ boys are left. We have already placed $18$ people, so we have $19$ position left for first boy, then $20$ position for 2nd boy and $21$ position for 3rd. So I get it as,

$5!$$15 \choose 12$($12!$)($19*20*21$)

But this looks clumsy and I'm not sure if its correct.

I searched for similar circular permutation questions on this site, but it was mostly regarding equal number of boys and girls, and since this question is different I couldn't co relate. If question is repeated, apologies and kindly redirect me to such duplicate question, else please help me find the solution. Thank you

$\endgroup$
2
$\begingroup$

First place some girl and let's say that her name is Alice.

Now place the other girls (indeed $5!$ possibilities).

The boys must be placed in an row/arrangement ($15!$ possibilities) in the understanding that the first will be placed at the right side of Alice, the second boy next to the first boy, et cetera.

To meet the condition that at least $2$ boys are present between $2$ adjacent girls we must find the number of sums: $$k_1+k_2+k_3+k_4+k_5+k_6=15$$ where every $k_i$ is an integer $\geq2$.

Setting $n_i:=k_i-2$ we find that this is the same as finding the number of sums:$$n_1+n_2+n_3+n_4+n_5+n_6=3$$ where every $n_i$ is a nonnegative integer.

Applying stars and bars we find $\binom{3+5}5=\binom85$ possibilities for that.

So we end up with a total of $$5!15!\binom85$$possibilities.

$\endgroup$
  • $\begingroup$ Thanks for such a lucid explanation, the stars and bars approach didn't strike for me.. $\endgroup$ – Csj Apr 10 at 15:22
2
$\begingroup$

HINT (in case this is homework)

First of all, your method over-counts. E.g. if a segment is Amy - Bob - Charles - David - Emma, then you would have counted this $3$ times: once when you place B & C between A & E and then inserted D later, once when you place B & D between A & E and then inserted C later, and once when you place C & D between A & E and then inserted B later. If a segment has $4$ boys you would have over-counted even more. Unfortunately the "degree of over-counting" is not uniform so you cannot just divide by a factor.

It might be easier to count the case of indistinguishable girls and boys first. Since there are only $3$ boys leftover after assigning $2$ per "gap", you can probably do this by hand. You can also do this formally via stars and bars. Then you can permute the girls $5!$ ways the boys $15!$ ways.

BTW, if you consider reflections to be equivalent (unclear for a circle), then you need to also divide by $2$ at the end.

Do you think you can finish from here?

$\endgroup$
  • $\begingroup$ Yes I understood why I'm over counting, it was an Institute written test question, I can do it from here. Thanks! $\endgroup$ – Csj Apr 10 at 15:21

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.