# 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

- ☂雨後晴空☀Lv 76 years agoFavorite 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.