seating arrangement variation

galactus · #1 $Old$ August 17th, 2006, 10:58 AM

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.

ThePerfectHacker · #2 $Old$ August 17th, 2006, 01:33 PM

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.

galactus · #3 $Old$ August 17th, 2006, 02:32 PM

My I ask, what exactly is an Orbit?.

Plato · #4 $Old$ August 17th, 2006, 03:10 PM

"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.

ThePerfectHacker · #5 $Old$ August 17th, 2006, 05:27 PM

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.

galactus · #6 $Old$ August 17th, 2006, 05:34 PM

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.

Plato · #7 $Old$ August 17th, 2006, 05:48 PM

BUT the point is that ‘group theory’ cannot solve this counting problem.
Given 10 blue beads and four red beads, how many ways can one form a ring of the beads no the red beads are adjacent?

ThePerfectHacker · #8 $Old$ August 17th, 2006, 06:32 PM

Quote:

Originally Posted by Plato

BUT the point is that ‘group theory’ cannot solve this counting problem.
Given 10 blue beads and four red beads, how many ways can one form a ring of the beads no the red beads are adjacent?

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$

Plato · #9 $Old$ August 17th, 2006, 06:42 PM

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!
The answer is 21.
What did you did you do?

ThePerfectHacker · #10 $Old$ August 17th, 2006, 06:45 PM

Quote:

Originally Posted by Plato

You are once again wrong!

How?
You simply take the total of all premutations and divide it by 28

galactus · #11 $Old$ August 19th, 2006, 10:08 AM

ThePerfectHacker · #12 $Old$ August 19th, 2006, 06:13 PM

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.

galactus · #13 $Old$ August 19th, 2006, 06:23 PM

Another way:

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