Esther asked in 科學及數學數學 · 6 years ago

counting problem

1) Six people are seated around a round table.

a) how many ways can they be reseated, so everyone moves to a new chair?

b) how many ways can they be reseated, so everyone has new neighbors on both sides?

2) there are three ways to cut a hexagon into two quadrilaterals. how many ways are there to cut a 12-gon into five quadrilaterals?

Please explain in details. Thank you so much!

3 Answers

Rating
  • 6 years ago
    Favorite Answer

    1b)

    If BAC changing to CAB , is it a case of A has new neighbors on both sides?

    2014-02-12 18:48:06 補充:

    1a)Let f(6) be the number of ways.

    For 2 people, let (12) be the first case, the only way is (21) , so f(2) = 1.

    For 3 people, let (123) be the first case, they can be reseated as (213) or (312),

    2 ways. So f(3) = 2.For 4 people, let (1234) be the first case and (r1 r2 r3 r4) be a required reseated way.Case 1 :

    r1 = k , (k = 2,3,4) and 1 = rk.

    There are 3f(2) ways since r1 = k have 3 possible people and there are f(2) ways for 2 remain people (excluding k and 1) moves to a new chair.Case 2 :

    r1 = k and 1 ≠ rk.

    There are 3f(3) ways since r1 = k have 3 possible people and there are f(3) ways for 3 remain people (excluding k) moves to a new chair.Therefore f(4) = 3f(2) + 3f(3) = 3(1) + 3(2) = 9.

    Similarly , f(5) = 4f(3) + 4f(4) = 4(2) + 4(9) = 44 and

    f(6) = 5f(4) + 5f(5) = 5(9) + 5(44) = 265.

    1b)For 5 people , let (↔123451↔) be the 1st case,

    only 2 ways (not consider chairs) :

    (↔142531↔) , note that we can join two "↔" upward and downward. For 6 people , let (↔1234561↔) be the 1st case. Case 1 (5 is not a neighbor of 1) :

    Consider 5 people case on condition that at most 1 pair are old neighbors, only 2 ways : (↔142531↔) , note that there are 0 way for exactly 1 pair.

    Then 6 can only be between 4 and 2 :

    (↔14 6 2531↔) , 2 ways.Case 2 (5 is a neighbor of 1) :

    (↔1364251↔) and (↔1426351↔) , 4 ways.The required number of ways = 6(2 + 4) = 36 for six chairs.

    2)Let f(12) be the number of ways to cut a 12-gon into five quadrilaterals.

    There are (6 - 3) = 3 ways to cut a hexagon into two quadrilaterals , so

    f(6) = 3.

    There are (8 - 3) = 5 ways to cut a 8-gon into a quadrilateral and a hexagon.

    So f(8) = 5f(6) = 5(3) = 15.

    There are (10 - 3) = 7 ways to cut a 10-gon into a quadrilateral and a 8-gon.

    f(10) = 7f(8) = 105.

    There are (12 - 3) = 9 ways to cut a 12-gon into a quadrilateral and a 10-gon.

    f(12) = 9f(10) = 9(105) = 945.

  • 6 years ago

    很有意義,謝謝您~

    ╭∧---∧╮

    │ .◕‿◕ │

    ╰/) ⋈ (\╯

  • 6 years ago

    Nope. if "BAC" were to be the first case, B and C can't be neighbors of A anymore.

Still have questions? Get your answers by asking now.