作者RichLowkey56 (有錢低調56)
看板Grad-ProbAsk
標題[理工] [離散] 組合問題
時間Wed May 11 00:27:02 2011
不好意思我一直有個疑問
就是圖論中的K(m,n)相異HC個數
標準答案是n!(n-1)!/2
但我自己算的結果是n!n!/2
--------
n
a ----> a
/
n-1
n-1
b ----> b
/
n-2
c c
. .
. .
. .
n n
--------
黃色是從左到右每個數的選擇
紅色是從右到左每個數的選擇
上面這個圖算出來是標準答案
但我想問的是
為什麼一開始的點不用選!?
我的想法是一開始的起始點要選 所以還要乘C(n,1)
這算出來就是我的n!n!/2
謝謝解答
--
[黑特] 騎機車為甚麼要抽菸
#1CzuRiEf (Hate)
1F:噓 Dontco:[黑特] 有捷運不坐 其甚麼機車 汙染空氣12/02 19:49
2F:→ joker5330:[黑特]有腳不走路 做什麼捷運 浪費銀兩12/02 19:51
3F:→ YamazakiG:[黑特]有機車不騎 走什麼路 浪費體力12/02 19:52
4F:→ FightYourMom:我們屏東人都騎山豬的12/02 19:52
5F:→ YamazakiG:幹我也屏東人為什麼沒山豬騎12/02 19:54
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.13.191
6F:推 aoqq12:照你的算法 你會重複n次喔 所以要除n 05/11 01:44
7F:→ aoqq12:因為每一種可能相當於一個cycle 05/11 01:48
8F:→ aoqq12:由於是對稱兩邊 所以此cycle重複只有 n個點 05/11 01:50
9F:→ aoqq12:也就是一個cycle 有n個相同可能會出現 05/11 01:51
10F:→ aoqq12:n!n!/n*2 除2的話則是反向皆可 05/11 01:51
11F:→ RichLowkey56:謝謝a大~~我了解了:D!! 05/15 00:19