Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - seating arrangement

  1. #1
    Newbie
    Joined
    Aug 2006
    Posts
    12

    Numder 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by kodirl
    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?

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Consider the table,
    Code:
                1
            8      2
          7           3
            6      4
                5
    Now a girl need to take up a seat call that 1.
    The other girl cannot sit at 2 or 8.
    The possibilities for the other two girls are:
    Code:
    73
    74
    75
    63
    64
    53
    3 possibilities for girl 1.
    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,
    3! \cdot 5!=720
    Times the number of different seatings. Which is 6.
    6\cdot 720=4320
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614
    Hello, kodir!

    Wow . . . I got yet another answer.


    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?

    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 3! ways.
    . . and the five boys can be seated in 5! ways.

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

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Soroban

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

    I agree with you, it seems I did not consider rotations as part of the problem. In that case if you divide by the number of girls by rotations (3) you get 1440 also.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Yes, it would appear I certainly over-complicated it.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    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?.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by galactus
    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?.
    I think that (hopefully i am right!) possible seating arrangements is 11*6*120=7920

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by galactus
    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?.

    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by OReilly
    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
    The number different ways to place 8 people at a round table is,
    7!=5040
    So how can you possibly have more with some limitation on the seating!
    (Look how well Soroban explained his answer).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    The number different ways to place 8 people at a round table is,
    7!=5040
    So how can you possibly have more with some limitation on the seating!
    (Look how well Soroban explained his answer).
    These are possible seating arrangements for one combination of girls (for example abc, * are boys):


    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    But some of them are the same. Look at #1 and #16 there is not "head" of the table.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    But some of them are the same. Look at #1 and #16 there is not "head" of the table.
    I don't understand. They are not the same. In #1 a,b,c are in 1,3,5 seats and in #16 they are in 4,6,8 seats.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Although OReilly's method was not entirely correct, it has insipired me to solve this problem with group theory. Let 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,
    G=\{r_0,r_1,...r_7\} be a group of rotations. Define the action of G on X to be 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,
    \frac{1}{|G|}\sum_{g\in G}|X_g|. Note, that X_g=\{gx=x\} can only be the same when g=r_0 \mbox{ (identity element) }. Thus, you have,
    \frac{1}{|G|}\left( |X|+0+0+... \right)
    Which is,
    \frac{1}{8}(11520)=1440
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member OReilly's Avatar
    Joined
    Mar 2006
    Posts
    340
    Quote Originally Posted by ThePerfectHacker
    Although OReilly's method was not entirely correct, it has insipired me to solve this problem with group theory. Let 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,
    G=\{r_0,r_1,...r_7\} be a group of rotations. Define the action of G on X to be 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,
    \frac{1}{|G|}\sum_{g\in G}|X_g|. Note, that X_g=\{gx=x\} can only be the same when g=r_0 \mbox{ (identity element) }. Thus, you have,
    \frac{1}{|G|}\left( |X|+0+0+... \right)
    Which is,
    \frac{1}{8}(11520)=1440
    My mistake is that I looked at all seating arrangements of girls not distinctive seating arrangements of girls. So from that point of view my answer is correct.
    But looking at distinctive seating arrangements in terms how girls can be positioned then my answer is not correct.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Seating arrangement
    Posted in the Statistics Forum
    Replies: 5
    Last Post: September 30th 2010, 09:49 AM
  2. [Probability] Seating arrangement & Selection
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2009, 05:01 PM
  3. Seating arrangements
    Posted in the Statistics Forum
    Replies: 4
    Last Post: February 19th 2009, 02:03 PM
  4. Seating Arrangement Problem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: December 4th 2007, 12:45 PM
  5. seating arrangement variation
    Posted in the Statistics Forum
    Replies: 12
    Last Post: August 19th 2006, 05:23 PM

Search Tags


/mathhelpforum @mathhelpforum