Q.Three girls a,b,c and five boys d,e,f,g,h are seated around a circular table.How many different arrangements are possible if no two girls are to sit together?

Printable View

- Aug 9th 2006, 03:58 AMkodirlNumder theory
Q.Three girls a,b,c and five boys d,e,f,g,h are seated around a circular table.How many different arrangements are possible if no two girls are to sit together?

- Aug 9th 2006, 04:27 AMOReillyQuote:

Originally Posted by**kodirl**

There can be five possible places in table where each girl can seat:

1 d 2 e 3 f 4 g 5 h

Totally possible combinations of a,b,c are 3*2*1 = 6 so there can be totally 6 arrangements of girls in 5 places.

Since each arrangement of girls (for example a,b,c) can be arranged in table in totally 9 combinations around table so that no two girls are together then its totally 6*9 = 45 combinations of girls around table.

Now there can be 5*4*3*2*1 = 120 combinations of boys arrangement.

Multiply total combinations of boys and girls 120*45 and you get that is totally 5400 arrangements if no two girls are siting together. - Aug 9th 2006, 11:19 AMThePerfectHacker
Consider the table,

Code:`1`

8 2

7 3

6 4

5

The other girl cannot sit at 2 or 8.

The possibilities for the other two girls are:

Code:`73`

74

75

63

64

53

And 2*1 possibilities for girls 2 and 3.

For the other 5 positition there are 5!=120 arrangentments for boys.

Thus in total for any seating arragement you have,

$\displaystyle 3! \cdot 5!=720$

Times the number of different seatings. Which is 6.

$\displaystyle 6\cdot 720=4320$ - Aug 9th 2006, 02:38 PMSoroban
Hello, kodir!

Wow . . . I got yet another answer.

Quote:

Three girls $\displaystyle a,b,c$ and five boys $\displaystyle d,e,f,g,h$ are seated around a circular table.

How many different arrangements are possible if no two girls are to sit together?

There are__two__seatings in which no girls are adjacent.Code:`G * G *`

* G * G

* * * *

* G G *

All others are rotations of these two arrangements.

In both arrangements, the three girls can be seated in $\displaystyle 3!$ ways.

. . and the five boys can be seated in $\displaystyle 5!$ ways.

Hence, there are: .$\displaystyle 2 \times 3! \times 5! \:=\:\boxed{1440\text{ ways.}}$

- Aug 9th 2006, 02:44 PMThePerfectHackerQuote:

Originally Posted by**Soroban**

- Aug 9th 2006, 02:50 PMgalactus
Yes, it would appear I certainly over-complicated it. :o

- Aug 9th 2006, 03:46 PMgalactus
You know, I was thinkin' , if we only want different order we can use the previous method. Suppose, though, that we wanted to include the arrangements of everyone keeping the same order but in different seats. That is, everyone slides over a chair right or left. That would be 1440*8=11520 arrangements.

Using the 2 arrangements from Soroban's post, we'd have 8*2=16 possible seating arrangements. 16*720=11520.

Whatcha think?. - Aug 10th 2006, 02:24 AMOReillyQuote:

Originally Posted by**galactus**

11 is possible seating arrangements of girls in table.

6 is number of combinations a,b,c.

120 is number of combinations d,e,f,g,h. - Aug 10th 2006, 04:22 PMOReillyQuote:

Originally Posted by**galactus**

11520 is definitely correct answer.

There is 16 possible seating arrangements around table of a,b,c.

6 is number of combinations a,b,c.

120 is number of combinations d,e,f,g,h.

So, 16*6*120=11520 - Aug 10th 2006, 05:19 PMThePerfectHackerQuote:

Originally Posted by**OReilly**

$\displaystyle 7!=5040$

So how can you possibly have more with some limitation on the seating!

(Look how well Soroban explained his answer). - Aug 10th 2006, 05:41 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

1: a*b*c***

2: a*b**c**

3: a*b***c*

4: a**b*c**

5: a**b**c*

6: a***b*c*

7: *a*b*c**

8: *a*b**c*

9: *a*b***c

10: *a**b*c*

11: *a**b**c

12: *a***b*c

13: **a*b*c*

14: **a*b**c

15: **a**b*c

16: ***a*b*c - Aug 10th 2006, 05:49 PMThePerfectHacker
But some of them are the same. Look at #1 and #16 there is not "head" of the table.

- Aug 10th 2006, 05:53 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

- Aug 11th 2006, 02:22 PMThePerfectHacker
Although OReilly's method was not entirely correct, it has insipired me to solve this problem with group theory. Let $\displaystyle X$ be the set of all possible arrangements of the seatings from seat #1 to seat #8 (Which is 11520 look at OReilly's post). The problem is that these arrangements are the same if you consider rotations. Let,

$\displaystyle G=\{r_0,r_1,...r_7\}$ be a group of rotations. Define the action of G on X to be $\displaystyle r_i(x)$ is a new arragentment obtained to moving everyone counterclockwise 1 person. Under these definitions we see that X is a G-set. Now, question is finding distinct seatings up to rotations. Which is the same as counting the number of orbits in X under G. Using, the Burnside Formula we have, that that number is,

$\displaystyle \frac{1}{|G|}\sum_{g\in G}|X_g|$. Note, that $\displaystyle X_g=\{gx=x\}$ can only be the same when $\displaystyle g=r_0 \mbox{ (identity element) }$. Thus, you have,

$\displaystyle \frac{1}{|G|}\left( |X|+0+0+... \right)$

Which is,

$\displaystyle \frac{1}{8}(11520)=1440$ - Aug 11th 2006, 03:59 PMOReillyQuote:

Originally Posted by**ThePerfectHacker**

But looking at distinctive seating arrangements in terms how girls can be positioned then my answer is not correct.