這題的答案是14*15!
2.There are eight people, denoted A,B,....,H be seated about the square table, and two of the eight people, say A and B, do not get along well, how many different seatings are possible with A and B not sitting next to each other ?
這題是7200
雖然有答案，就是想不通是怎麼算的，麻煩請高手幫忙解答一下，感謝
11 則留言:
第二題我在課本看到一樣的題目
他是減去坐在同一側＋坐在桌腳兩側
他的解答是8!/4 - (2*6!+2*6!) = 7200
可是我的想法是
8!/4 - (6!/2 + 6!/2) = 9360
因為是方桌所以各除以四
拍謝,我也不是很清楚,給你參考一下
感謝你提供參考資料，看解答的解釋，原來坐在桌角2邊也有算，難怪我怎麼算都比較多
第一題跟我朋友討論出來一種解法,
給你參考,
兩個書櫃,每個書櫃至少一本書,
我假設「」「」為兩個書櫃,
所以有「1」「14」,「2」「13」,…
…「13」「2」,「14」「1」,
十四種擺法。
而每種擺法的排列數為15!,
[而且C(15,1)*1!*14!+C(15,2)*2!*13!+…
…+C(15,13)*13!*2!+C(15,14)*14!*1!
= 14*15!]
故解為14*15! 。
1. 就像裴寫的, 若第一個櫃子取 r 本書, 則第二個櫃子會有 15-r 本書, 總數就是 r!(15-r)!, 因為從 15 本書裡取 r 本書有 c(15,r)種取法, 所以總數就是
Σc(15,r)*r!(15-r)!, r 從 1 到 14
= Σ(15!/r!(15-r)!)r!(15-r)!
= Σ15!
= 14*15!
不過這裡也可以很簡單的把它想成, 15 本書做排列, 然後要決定再哪兩本書之間放一個版子把這些書分成兩堆, 總共有 14 種切隔的方法
2. 裴的想法問題出在當我們在算2*6!時, 是把 A 和 B 固定在某一個桌邊或桌腳上了, 而不像是在算 8! 時有把每個桌邊都視為是不一樣, 所以並沒有多考慮, 因此不用再除以 4
除了老師在書上習題 3-20 提供的方法以外, 另一種想法是先固定 A 在某個桌邊的左邊上, 也就是 A 的右手邊位置可坐人, 此時 B 有兩個位置不能坐, 得從其他的 5 個位置選一個坐, 然後剩下的 6 個人做排列就是 6!, 同理若一開始是固定 A 的位置使得 A 左手邊的位置可以坐人, 方法數也是 5*6!, 所以總數就是 2*5*6! = 7200
請問一下助教,
我會搞混是因為有一個類題,
2*3的長方形,
題目為,
In how many of the arrangements of rectangular table are A and B seated on longer sides of the table across from each other?(有10人為A,B,....,I,J)
當初老師解為,
(8!*2/2)*3 ＝ 8!*3
我的問題是為什麼這時候又要除以2？
照你的解法,
AB固定,
所以解為,
(8!*2)*3 = 8!*6,
是因為長方形的關係嗎！？
麻煩可幫解嗎？謝謝。
In how many of the arrangements of rectangular table are A and B seated on longer sides of the table across from each other?(有10人為A,B,....,I,J)
長方桌問題我剛好有聽到
其中的8!*2!是那八個人加上A與B的排列
之後會再除以2!是因為長方桌的關係
而最後因為A,B各有三個位置可選,但決定了A相對的B的位置也決定了,故考慮一邊就好,所以再*3
可是上面那題正方形,
排容要排掉的那塊,
為什麼不用除四,
而長方形要除二,
想不通....
嗯, 新版書上 p3-17 那一題和這題的想法是差不多的, 不過如果按照你說的考慮 A,B 互調為 2*8!, 該除以 2 的原因和你想的可能稍微有點不一樣, 這裡容易搞混的地方可能還是在於究竟什麼時候會把同一個排列重複算到
舉個小例子, 假設今天只有 4 個人 A,B,C,D 要打麻將
(a) 位置總共的坐法會有 4!/4 = 6 種
(b) 若限制 A 不可以是 B 的上一家或下一家,
我們的算法就是叫 A 先隨便找個位置坐, 然後因為 B 只能是 A 的對家, 剩下 C,D 分別可選 A 的上家和下家, 所以總共就是 1*2 = 2 種坐法
再比較一下(a)和(b), 在(a)中, 譬如像是A-C-B-D分別坐在東-南-西-北, 南-西-北-東,... 這些都會被我們算進去, 所以要除以 4, 可是我們在算(b)時, 一組合法的排列A-C-B-D只被算了一次而已, 因為我們本來就沒有限定 A 要坐在哪個方位, 所以不用除以 4
回到原來的問題, 在長桌上, 因為把 A-B 對放放在長桌的上方, 然後再互調再旋轉180度, 和把 A-B 對放放在長桌的下方, 這兩種情況其實都被我們算到了, 所以要再除以 2, 但是在正方形桌那一題中不會有這樣的情形, 因為將 A-B 放再同一桌邊, 然後再互調, 怎麼轉也轉不回原來的那種排列方式, 所以除以 2 其實不是考慮整體, 而是考慮那兩個人, 希望這樣的說明可以讓你更了解這種類似環狀排列的特性
謝謝 懂了！
張貼留言