推 windlike01 :非常清楚，十分感謝！ 08/16 19:49
※ 編輯: oNeChanPhile 來自: 114.27.8.196 (10/21 17:02)
※ 引述《windlike01 (全力衝刺)》之銘言：
: Q:若有n個人圍圓桌而坐,欲從中選取k(n≧2k)個人,使得彼此
: 原來的位置皆互不鄰,請問有多少種選取法?
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 140.113.25.202
: 推 XII :C(n-k-1,k-1)+C(n-k,k) 08/16 17:07
圖解：
把環從1號人(以下稱球)處截斷，排成直線
１２３４................n
○○○○○○○○○○○○○
選取的情況分兩種：
(i)選到1號球（必不選n號球）
１２３４................n
●○○●○●○○●○○●○
╰┬╯╰╯╰┬╯ ╰╯
x1 x2 x3 xk
如圖，假設第 i 個被選到的球，加上與其後緊跟著的未選球數為 xi。
因為題目要求被選到的球不能相鄰，所以 xi≧2 (i=1~k)
所以 x1 + x2 + ... + xk = n, xi≧2 (i=1~k) 之條件可以改寫成
y1 + y2 + ... + yk = n-2k, yi≡xi-2 ≧0 (i=1~k)
球的選法數目，即為上式的非負整數解個數 H(k,n-2k)
(ii)不選1號球（可選n號球）
１２３４....................n
○○●○○●○●○○●○○●○
╰╯╰┬╯╰╯╰┬╯ ╰╯
x0 x1 x2 x3 xk
假設第一個被選到的球之前面有 x0 個球，其餘同(i)
則 xi 的限制式為
x0≧1, xk≧1(因n號球可以被選取), 其餘xi≧2
所以 x0 + x1 + x2 + ... + xk = n 可以改寫成
y0 + y1 + y2 + ... + yk = n-2-2(k-1) = n-2k
其非負整數解個數為 H(k+1,n-2k)
綜合(i)(ii)之情況
總選法數＝H(k, n-2k) + H(k+1, n-2k) = C(n-k-1, k-1) + C(n-k, k)
= (n/k) C(n-k-1, k-1)
#
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.39.225.13