推 kh749 : 好厲害！ 08/16 21:02
推 alan23273850: PUSH 08/17 01:20
推 raymond92928: 太強了~ 08/17 14:48
推 JKLee : 推 08/19 13:15
※ 引述《raymond92928 (raymond)》之銘言：
: https://goo.gl/7qJZdq
: 第一題無從入手
: 解答也完全看不懂
: 求高人解釋一下
: 或者有其他的解法也可以
a b c d e
A o x o x x
B x o o x x
C o x x x o <===> 視為 10 個點的二分圖 (bipartite graph)
D x o x o x
E x x x o o 點集為 {A,B,C,D,E,a,b,c,d,e}
邊集為 {Aa,Ac,Bb,Bc,Ca,Ce,Db,Dd,Ed,Ee}
(有放 o 的對應的兩點要連邊)
因每點恰連兩條邊, 故必為 cycle 的聯集
eg. 上例的圖為 10 個點的 cycle: A--a--C--e--E--d--D--b--B--c
╰─────────────╯
注意到這些 cycle 的長度必為 4 以上的偶數
故只可能為 10 cycle 或 6 cycle∪4cycle
10 cycle 個數有 (5!*5!)/(5*2) = 1440
6 cycle∪4 cycle 個數有 C(5,3)*C(5,3)*{(3!*3!)/(3*2)}*{(2!*2!)/(2*2)} = 600
故共有 1440 + 600 = 2040 種
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.25.103
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1502886663.A.221.html