※ 引述《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 ※ 编辑: oNeChanPhile 来自: 114.27.8.196 (10/21 17:02)