※ 引述《LKJX (LKJX)》之銘言:
: 各位大大您們好,
: 請問:
: 問一:(圖到底要如何畫 > < "" )
: (1) 3 對夫婦環狀排列,若男女相間隔,夫婦不相鄰的方法。
: (2) 4 對夫婦環狀排列,若男女相間隔,夫婦不相鄰的方法。
: (3) 5 對夫婦環狀排列,若男女相間隔,夫婦不相鄰的方法。
: (4) 6 對夫婦環狀排列,若男女相間隔,夫婦不相鄰的方法。
: (5) n 對夫婦環狀排列,若男女相間隔,夫婦不相鄰的方法。
先排 n 女, 有 (n-1)! 種排法
再排 n 男, 排法可視為在 n*n 的方格中, 各行各列恰選一格, 但不可選到 x 格
(如下圖, 此為 n = 6 的例子)
xxoooo
oxxooo
ooxxoo
oooxxo
ooooxx
xoooox
又各行各列恰選一格, 但選到 k 個 x 格的方法數
= 在 2n 個相異物的環狀排列中取 k 個不相鄰物的方法數
= (2n)*C(2n-3-(k-1)+1,k-1)/k
= 2n*C(2n-k,k)/(2n-k)
故由排容原理可得所求方法數
= (n-1)!*Σ_{k=0}^n (-1)^k*(2n)*C(2n-k,k)/(2n-k)*(n-k)!
=(n-1)!*Σ_{k=0}^n (-1)^k*C(2n-k,k)*(n-k)!*(2n)/(2n-k)
-----------------------------------------------------------
e.g.
n = 6 時
所求為 5!(720-1440+1296-672+210-36+2)=5!*(80)=9600
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.136.81
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1486561867.A.FFC.html
※ 編輯: XII (140.122.136.81), 02/08/2017 22:09:42
※ 編輯: XII (140.122.136.81), 02/08/2017 22:14:15