# seating arrangement variation

• Aug 17th 2006, 09:58 AM
galactus
seating arrangement variation
I would like to extend our old circular permutation problem to 10 boys and 4 girls.

That is, "how many arrangements are possible with 10 boys and 4 girls if no 2 girls can set together?".

Anyone wanna tackle this one. It's a little rougher than the 5 boys and 3 girls.

We know there are 13! possible arrangements, altogether. Big number.
• Aug 17th 2006, 12:33 PM
ThePerfectHacker
Quote:

Originally Posted by galactus
I would like to extend our old circular permutation problem to 10 boys and 4 girls.

That is, "how many arrangements are possible with 10 boys and 4 girls if no 2 girls can set together?".

Anyone wanna tackle this one. It's a little rougher than the 5 boys and 3 girls.

We know there are 13! possible arrangements, altogether. Big number.

Extending the concept of counting orbits you have,
$\frac{1}{14}S\cdot 4!\cdot 10!$
Where, $S$
The the number of different position without rotations, for example,
Code:

G*G*G*G****** G*G*G**G***** G**G**G**G*** AND SO ON
The problem reduces to finding S.
• Aug 17th 2006, 01:32 PM
galactus
My I ask, what exactly is an Orbit?.
• Aug 17th 2006, 02:10 PM
Plato
"Where, S (is) the the number of different position without rotations"
But that is the whole point of this new question. Finding S is the hard part.
With 5 & 3, it was easy by listing. But in this case it is more difficult.
• Aug 17th 2006, 04:27 PM
ThePerfectHacker
Quote:

Originally Posted by galactus
My I ask, what exactly is an Orbit?.

If you studied group theory I would be happy to give you a lecture on the concept of G-sets.
• Aug 17th 2006, 04:34 PM
galactus
Thanks for the offer, PH, but I haven't studied much group theory. Wish I could say I had. Fields, rings and the occasional -morphism.

Could you recommend a good introductory text on group theory?. I have a nice abstract algebra text.

You don't need that to figure this problem up, though, but it is an interesting approach.
• Aug 17th 2006, 04:48 PM
Plato
BUT the point is that ‘group theory’ cannot solve this counting problem.
• Aug 17th 2006, 05:32 PM
ThePerfectHacker
Quote:

Originally Posted by Plato
BUT the point is that ‘group theory’ cannot solve this counting problem.

Yes group theory can solve this problem. You need to consider flips as well as rotations. This gives you a full dihidrel group $D_{14}$ having order of $2(14)=28$
• Aug 17th 2006, 05:42 PM
Plato
Quote:

Originally Posted by ThePerfectHacker
Yes group theory can solve this problem. You need to consider flips as well as rotations. This gives you a full dihidrel group $D_{14}$ having order of $2(14)=28$

You are once again wrong!
What did you did you do?
• Aug 17th 2006, 05:45 PM
ThePerfectHacker
Quote:

Originally Posted by Plato
You are once again wrong!

How?
You simply take the total of all premutations and divide it by 28
• Aug 19th 2006, 09:08 AM
galactus
$10\cdot{9}\cdot{4}\cdot{3!}\cdot{8!}\cdot{21}$
• Aug 19th 2006, 05:13 PM
ThePerfectHacker
Quote:

Originally Posted by galactus
$10\cdot{9}\cdot{4}\cdot{3!}\cdot{8!}\cdot{21}$

What is that?
It cannot be "S".
Because "S" represents the different possible seating positions.
Since there are 14 different slots for the girls. The number of different assigments is,
$S={14 \choose 4}$, S cannot exceed this number.
---
Here is my method of Finding S,
Find the total possible positions which is given above by the combination. Then subtract the undesired. For example, subtract when all girls are together. There are 11 such instances. Then subtract 3 girls together 1 seperate.... This method which I posted before might be slightly time consuming because you need to count S but S is not such a large number.
• Aug 19th 2006, 05:23 PM
galactus
Another way:

$C(10,4)9!4!=1,828,915,200$