Basic combinatorics: How many ways can 4 boys and 4 girls sit in a row such that no 2 girls sit together?

[tellmesomething]

Homework Statement

There are 4 boys and 4 girls. In how many ways can they sit in a row such that no two girls sit together.

Relevant Equations

Gah

I tried this for a long time but im not getting there, not even close. So far I tried finding out the total number of ways you could sit these boys and girls if there were no restriction, that came out to be 40320.

Then I found the number of ways you could have with two girls sitting next to each other, this came out to be 5040. Next I found out the number of ways you can seat them with 3 girls together which came out to be 2880. Then I found out the number of ways you can seat them with all of the girls together which came out to be 2880 again.

My plan was to add the latter up and subtract it from the total, soon enough I noticed that i'll be counting the 2 girls thrice in the addition and then the three girls twice. If this is even close to what the approach could be , please continue my train of thought and help me out here, if this is completely wrong please explain why so, and provide an alternate hint. Thankyou, have a nice day.

 

[pbuk]

I tried this for a long time but im not getting there, not even close. So far I tried finding out the total number of ways you could sit these boys and girls if there were no restriction, that came out to be 40320.

Please show how you got to that number (it is out by a factor of over 150).

Edit: and then consider tackling the problem the other way round: can you write down one such arrangement?

 

[jambaugh]

You should first determine the number of configurations of boys and girls that satisfy the condition, then multiply by the 4!x4! ways of rearranging the individual boys and individual girls. The number of configurations should be easily list-able. Between 2 and 10.

 

[tellmesomething]

Please show how you got to that number (it is out by a factor of over 150).

Edit: and then consider tackling the problem the other way round: can you write down one such arrangement?

Well if there were no restrictions then you could arrange the boys and girls like this - the first place could be filled with any of the 8 people second place with 7 (because repitition with people wouldn't make sense) third place with 6 fourth place with 5 fifth place with 4 sixth place with 3 seventh place with 2 eighth place with 1 so basically factorial 8.

 

[WWGD]

Notice the ways two girls can sit together: 1st and 2nd spot, 2nd and third spots. And we can do similar for the other two.Then we can select which of the 2 girls sit together, etc.

But 40320=8! is the total way in which the 8 people can sit.

Maybe you can use inclusion/exclusion if you've seen it. To start with all ways of sitting, then considering when 2,3, or all 4 girls sit together.

 

[vela]

Given the number of boys and girls in the problem, you're going about it the hard way. I recommend you consider @jambaugh's suggested approach.

 

[PeroK]

If I was totally stuck with 4 of each, then I would try only 3 of each, or even only 2 of each, to get some insight into possible solutions.

 

[WWGD]

It seems we can consider the fact that the only way to avoid two girls next to each other is alternating them. So, I guess like Jambaugh said, 4!4! total. Though the solution doesn't seem to generalize to the case of B boys and G girls, where B$\neq$G

 

[tellmesomething]

If I was totally stuck with 4 of each, then I would try only 3 of each, or even only 2 of each, to get some insight into possible solutions.

i tried that i always try to find a simpler solution and generalize it but im just losing my train of thought on this one maybe i should eat some almonds......

 

[tellmesomething]

th

You should first determine the number of configurations of boys and girls that satisfy the condition, then multiply by the 4!x4! ways of rearranging the individual boys and individual girls. The number of configurations should be easily list-able. Between 2 and 10.

this makes sense it could be BGBGBGBG OR GBGBGBGB OR GBGBBGBG OR GBGBGBBG OR GBBGBGBG . Hmm am i missing something. Also here it is listable but what if it wasnt? Say with 10 ggirls and 10 boys

 

[tellmesomething]

Notice the ways two girls can sit together: 1st and 2nd spot, 2nd and third spots. And we can do similar for the other two.Then we can select which of the 2 girls sit together, etc.

But 40320=8! is the total way in which the 8 people can sit.

Maybe you can use inclusion/exclusion if you've seen it. To start with all ways of sitting, then considering when 2,3, or all 4 girls sit together.

Yes. I know my post is long but thats what i did (and wrote) i found out 2 girls 3 girls 4 girls but after that im nt so sure. And sorry for my ignorance but whats inclusion/exclusion?

Also if you know how to correctly complete this method please let me know

 

[WWGD]

Yes. I know my post is long but thats what i did (and wrote) i found out 2 girls 3 girls 4 girls but after that im nt so sure. And sorry for my ignorance but whats inclusion/exclusion?

Also if you know how to correctly complete this method please let me know

You count all possible arrangements, subtract those where two girls sit next to each other, then add those where 3 girls sit next to each other, ultimately, subtract those where 4 girls sit next to each other.
There's a bit of an involved argument to show you end up with all arrangements were no two girls sit to each other.

But, more simply, I think Jambaugh uses this, in order to not have 2 girls together, you must alternate them, boy girl, boy, etc.
Then you first select 4 spots for girls( boys), after which girls spots are determined, then permute the boys , girls , in the designated spots.

 

[WWGD]

But, if you want a nicer exercise, generalize a solution of the same sitting problrm for a group of G girls, B boys, G different from B.

 

[vela]

this makes sense it could be BGBGBGBG OR GBGBGBGB OR GBGBBGBG OR GBGBGBBG OR GBBGBGBG . Hmm am i missing something. Also here it is listable but what if it wasnt? Say with 10 ggirls and 10 boys

Think of it this way. The girls have to be separate from each other, right? So they partition the line into three slots in between them and two on the ends, i.e., _G_G_G_G_. Then you're just figuring out how many ways you can fill those spots with the boys. The interior slots need at least one boy whereas the ends can have no one.

You should be able to generalize that to different numbers of boys and girls.

 

[tellmesomething]

You count all possible arrangements, subtract those where two girls sit next to each other, then add those where 3 girls sit next to each other, ultimately, subtract those where 4 girls sit next to each other.
There's a bit of an involved argument to show you end up with all arrangements were no two girls sit to each other.

But, more simply, I think Jambaugh uses this, in order to not have 2 girls together, you must alternate them, boy girl, boy, etc.
Then you first select 4 spots for girls( boys), after which girls spots are determined, then permute the boys , girls , in the designated spots.

Okay I know where my approach is wrong I fixed the places pf two girls and a boy but I didnt consider that there are 4 girls so all the possible combinations of the girls have to be included I have made changes yet im getting a weird answer because I over counted? Im really interested in knowing how to get the solution bu this way can you help me out I can send you my approach so far, ive some doubts maybe you can clear them up (only if you have some free time ofcourse)

Also you say add the 3 girls ways whys that?

In my country theres a 1 week vacay for a festival else I would have asked my teacher. Sorry for the inconvenience, I hope you do not feel obligated to reply.

 

[tellmesomething]

Think of it this way. The girls have to be separate from each other, right? So they partition the line into three slots in between them and two on the ends, i.e., _G_G_G_G_. Then you're just figuring out how many ways you can fill those spots with the boys. The interior slots need at least one boy whereas the ends can have no one.

You should be able to generalize that to different numbers of boys and girls.

Ill try that thankyou very much. Y'all are very helpful:)

 

[erobz]

I don't know how streamlined the inclusion/exclusion principle would be. It seems like figuring out which subsets of combinations to subtract and add back world still be a problem.

This is NOT the OP's original problem

Just scaling back a bit imagine 3 girls , 2 boys. There is only one string that achieves it:

$$ G,B,G,B,G = 3! \cdot 2! = 12 $$

So we have the answer to this without much difficulty. If, however, we were going to start from the whole set and cut away we have:

$$ \overbrace{(5,2)}^{ \begin{array} ~ \text{choose position} \\ \text{ of boys} \end{array}} \cdot \overbrace{2!}^{ \text{order boys}} \cdot \overbrace{3!}^{\text{order girls}} = 120 $$

Then we would subtract away strings where exactly 3 girls $G_3$ sat next to each other:

$$ \underline{G_3} ~\underline{\quad} ~\underline{\quad} $$

$$ \overbrace{( 3,1)}^{ \text{choose slot}} \cdot \overbrace{3!}^{ \text{Order}~ G_3} \cdot \overbrace{2!}^{ \text{order boys}} = 36 $$

Then subtract away strings where exactly 2 girls $G_2$ sit next to each other which can happen in 4 cases ( i.e. $G_2$ can be placed in any of the 4 available positions):

$$ \underline{G_2} ~\underline{ \quad } ~\underline{\quad} ~\underline{\quad} $$

Where $G_2$ is in the first slot a boy must immediately follow:

$$ \overbrace{( 3,2)}^{ \begin{array} ~\text{choose girls} \\ \text{in G_2} \end{array} } \cdot \overbrace{2!}^{ \text{order}~ G_2} \cdot \overbrace{2!}^{ \begin{array} ~\text{ select adjacent } \\ \text{ boy} \end{array} } \cdot \overbrace{2}^{ \begin{array} ~\text{order remaining} \\ \text{boy/girl} \end{array}} = (3,2) \cdot 2 \cdot 4 $$

Next slot:
$$ \underline{B} ~\underline{ G_2} ~\underline{B} ~\underline{G} $$

There are $(3,2) \cdot 2 \cdot 2$ ways of making that string

Next slot:
$$ \underline{G} ~\underline{ B} ~\underline{G_2} ~\underline{B} $$

There are $(3,2) \cdot 2 \cdot 2$ ways of making that string

Lastly when $G_2$ takes the last slot, you get the same number of orderings as the first slot.

$$ (3,2) \cdot 2 \cdot 4 $$

This gives a total of:

$$ (3,2) \cdot 2 ( 4 + 2 + 2 + 4 ) = 6 \cdot 2 \cdot 12 = 72$$

Then you subtract ordering with $G_3$ and $G_2$ off of the general orderings:

$$ 120 - 36 - 72 = 12 $$

If there is a generalization for this, or if the inclusion/exclusion principle somehow requires less examination I'm all ears. That being said, people that understand combinatorics are a different breed and they usually go its "blah, blah, blah" in a single formulation and my head explodes...so I look forward to that!

 

[WWGD]

I sent think Inclusion/exclusion is that

I don't know how streamlined the inclusion/exclusion principle would be. It seems like figuring out which subsets of combinations to subtract and add back world still be a problem.

This is NOT the OP's original problem

Just scaling back a bit imagine 3 girls , 2 boys. There is only one string that achieves it:

$$ G,B,G,B,G = 3! \cdot 2! = 12 $$

So we have the answer to this without much difficulty. If, however, we were going to start from the whole set and cut away we have:

$$ \overbrace{(5,2)}^{ \begin{array} ~ \text{choose position} \\ \text{ of boys} \end{array}} \cdot \overbrace{2!}^{ \text{order boys}} \cdot \overbrace{3!}^{\text{order girls}} = 120 $$

Then we would subtract away strings where exactly 3 girls $G_3$ sat next to each other:

$$ \underline{G_3} ~\underline{\quad} ~\underline{\quad} $$

$$ \overbrace{( 3,1)}^{ \text{choose slot}} \cdot \overbrace{3!}^{ \text{Order}~ G_3} \cdot \overbrace{2!}^{ \text{order boys}} = 36 $$

Then subtract away strings where exactly 2 girls $G_2$ sit next to each other which can happen in 4 cases ( i.e. $G_2$ can be placed in any of the 4 available positions):

$$ \underline{G_2} ~\underline{ \quad } ~\underline{\quad} ~\underline{\quad} $$

Where $G_2$ is in the first slot a boy must immediately follow:

$$ \overbrace{( 3,2)}^{ \begin{array} ~\text{choose girls} \\ \text{in G_2} \end{array} } \cdot \overbrace{2!}^{ \text{order}~ G_2} \cdot \overbrace{2!}^{ \begin{array} ~\text{ select adjacent } \\ \text{ boy} \end{array} } \cdot \overbrace{2}^{ \begin{array} ~\text{order remaining} \\ \text{boy/girl} \end{array}} = (3,2) \cdot 2 \cdot 4 $$

Next slot:
$$ \underline{B} ~\underline{ G_2} ~\underline{B} ~\underline{G} $$

There are $(3,2) \cdot 2 \cdot 2$ ways of making that string

Next slot:
$$ \underline{G} ~\underline{ B} ~\underline{G_2} ~\underline{B} $$

There are $(3,2) \cdot 2 \cdot 2$ ways of making that string

Lastly when $G_2$ takes the last slot, you get the same number of orderings as the first slot.

$$ (3,2) \cdot 2 \cdot 4 $$

This gives a total of:

$$ (3,2) \cdot 2 ( 4 + 2 + 2 + 4 ) = 6 \cdot 2 \cdot 12 = 72$$

Then you subtract ordering with $G_3$ and $G_2$ off of the general orderings:

$$ 120 - 36 - 72 = 12 $$

If there is a generalization for this, or if the inclusion/exclusion principle somehow requires less examination I'm all ears. That being said, people that understand combinatorics are a different breed and they usually go its "blah, blah, blah" in a single formulation and my head explodes...so I look forward to that!

I don't think inclusion/exclusion is that hard in this question. There are 7 ways of having 2 consecutive. 1-2,2-3,..,7-8. Then there are 6 people left, to be arranged in 6! ways; then 6 ways of having 3 consecutive, 5! for the rest, 5 ways of having 4 consecutive, 4! for the rest. That's it.

 

[tellmesomething]

I don't know how streamlined the inclusion/exclusion principle would be. It seems like figuring out which subsets of combinations to subtract and add back world still be a problem.

This is NOT the OP's original problem

Just scaling back a bit imagine 3 girls , 2 boys. There is only one string that achieves it:

$$ G,B,G,B,G = 3! \cdot 2! = 12 $$

So we have the answer to this without much difficulty. If, however, we were going to start from the whole set and cut away we have:

$$ \overbrace{(5,2)}^{ \begin{array} ~ \text{choose position} \\ \text{ of boys} \end{array}} \cdot \overbrace{2!}^{ \text{order boys}} \cdot \overbrace{3!}^{\text{order girls}} = 120 $$

Then we would subtract away strings where exactly 3 girls $G_3$ sat next to each other:

$$ \underline{G_3} ~\underline{\quad} ~\underline{\quad} $$

$$ \overbrace{( 3,1)}^{ \text{choose slot}} \cdot \overbrace{3!}^{ \text{Order}~ G_3} \cdot \overbrace{2!}^{ \text{order boys}} = 36 $$

Then subtract away strings where exactly 2 girls $G_2$ sit next to each other which can happen in 4 cases ( i.e. $G_2$ can be placed in any of the 4 available positions):

$$ \underline{G_2} ~\underline{ \quad } ~\underline{\quad} ~\underline{\quad} $$

Where $G_2$ is in the first slot a boy must immediately follow:

$$ \overbrace{( 3,2)}^{ \begin{array} ~\text{choose girls} \\ \text{in G_2} \end{array} } \cdot \overbrace{2!}^{ \text{order}~ G_2} \cdot \overbrace{2!}^{ \begin{array} ~\text{ select adjacent } \\ \text{ boy} \end{array} } \cdot \overbrace{2}^{ \begin{array} ~\text{order remaining} \\ \text{boy/girl} \end{array}} = (3,2) \cdot 2 \cdot 4 $$

Next slot:
$$ \underline{B} ~\underline{ G_2} ~\underline{B} ~\underline{G} $$

There are $(3,2) \cdot 2 \cdot 2$ ways of making that string

Next slot:
$$ \underline{G} ~\underline{ B} ~\underline{G_2} ~\underline{B} $$

There are $(3,2) \cdot 2 \cdot 2$ ways of making that string

Lastly when $G_2$ takes the last slot, you get the same number of orderings as the first slot.

$$ (3,2) \cdot 2 \cdot 4 $$

This gives a total of:

$$ (3,2) \cdot 2 ( 4 + 2 + 2 + 4 ) = 6 \cdot 2 \cdot 12 = 72$$

Then you subtract ordering with $G_3$ and $G_2$ off of the general orderings:

$$ 120 - 36 - 72 = 12 $$

If there is a generalization for this, or if the inclusion/exclusion principle somehow requires less examination I'm all ears. That being said, people that understand combinatorics are a different breed and they usually go its "blah, blah, blah" in a single formulation and my head explodes...so I look forward to that!

.

Your second step where you are arranging the two girls, im getting a different answer. Please tell me where I went wrong

No. Of ways you could arrange these two girls between themselves I.e (G1 G2, G2G1) = 2!= 2.

You will have to fix the place for a boy beside these girls Therefore, _ _ BGG. Ways you could fill one up = 2 factorial

You could position them in 3 ways again
BGG__ , _BGG_, _ _ BGG.

Possible combination of boys 2C1 = 2

Possible combination of girls 3C2= 3

Multiplying that all = 2*2*2*3*3 = 48

 

[erobz]

No. Of ways you could arrange these two girls between themselves I.e (G1 G2, G2G1) = 2!= 2.

You will have to fix the place for a boy beside these girls Therefore, _ _ BGG. Ways you could fill one up = 2 factorial

You could position them in 3 ways again
BGG__ , _BGG_, _ _ BGG.

Possible combination of boys 2C1 = 2

Possible combination of girls 3C2= 3

Multiplying that all = 2*2*2*3*3 = 48

What is this replying to?

 

[tellmesomething]

What is this replying to?

To your answer sir. I edited the beginning pls check

 

[erobz]

To your answer sir. I edited the beginning pls check

You've got some quotation "inception" going on.

 

[tellmesomething]

You've got some quotation "inception" going on.

Im not really sure if I understand that

 

[tellmesomething]

You've got some quotation "inception" going on.

Anywho sorry sir 2× 2×2×3×3 is 72 indeed not 48 like I calculated. That was very silly. I can live freely now knowing my method works but ive tried this on the original question since this morning and I always end up over counting .

 

[erobz]

Im not really sure if I understand that

Sorry, you probably have not seen the movie "Inception". You have a quote of me inside a quote of me saying something I didn't say.

 

[tellmesomething]

Sorry, you probably have not seen the movie "Inception". You have a quote of me inside a quote of me saying something I didn't say.

Oh that was me trying to reply but it kept going in that quote thing, instead of the white space below. Also is that christopher nolan's movie? Its quite famous ive heard.

 

[erobz]

I sent think Inclusion/exclusion is that

I don't think inclusion/exclusion is that hard. There are 7 ways of having 2 consecutive. 1-2,2-3,..,7-8. Then there are 6 people left, to be arranged in 6! ways; then 6 ways of having 3 consecutive, 5! for the rest, 5 ways of having 4 consecutive, 4! for the rest. That's it.

I'm not seeing it. What are we adding/subtracting here? You say there are 7 ways of having 2 consecutive sit next to each other. so you pick seats 1 and 2 for example, then 6! other orderings of the remaining people, but some significant number of those orderings are other orderings where 2 girls sit together? I'm just not able to keep up here.

 

[PeroK]

Im not really sure if I understand that

I'd go back to post #14 and start from there. I wouldn't get distracted by subsequent posts.