推 steve1012 : 喔喔因為規定要分完 所以要是abca的話 d沒人可連 07/24 23:44
推 steve1012 : 真的是太厲害了 我再仔細研究一下 還有prufer code 07/24 23:48
→ XII : 沒注意到你最後是在說4 node的情況 07/24 23:56
文長恕刪
※ 引述《steve1012 (steve)》之銘言：
: 想要請教一題排列組合
: 因為沒什麼方向 想請大家指點一些方向的 就算只有關鍵字也好
: 重寫一下題目
: 其實這個題目可以看成是 functional digraph 的個數
: 一個functional digraph 就是說在這個graph 裡面 每一點只能連到一個node
: (directed graph) 因為每一點都只能連到一個node 所以我們可以用function
: 的方式去描述 比如說給定一個node v_1則他會連到 f(v_1)
: 我這個題目跟傳統functional digraph 不同的地方在於 node不能連到自己
: 那現在我關心的是 functional digraph 裡面最大的connected components的size
: 我用CC代表connected component
先給好 n 點, 則這 n 點形成 connected component 的方法數為
Σ_{k=2,...,n} (n!/(n-k)!)*n^{n-k-1}
eg. 4 個 node 的 connected component 有
4!(4^1/2!+4^0/1!+4^{-1}/0!) = 48+24+6 = 78 個
(若可連到自己, 則 connected component 連的方法數中改為 Σ_{k=1,...,n})
: 比如說我們現在有4個node. 我們就會有 (4-1)^4 種不同的functional di-graph.
: 其中有3種function digraph的 "最大的CC" 是有兩個node的:
: 1. A<->B C<->D
: 2. A<->C B<->D
: 3. A<->D B<->C
: 然後會有78種functional digraph 的最大cc是有四個node的
4 點的
4 => (4!/4!)*78
2+2 => 4!/(2!2!2!)*1 = 3
total = 81 = 3^4
5 點的
5 => (5!/5!)*{5!(5^2/3!+5^1/2!+5^0/1!+5^{-1}/0!)} = 944
3+2 => (5!/(3!*2!))*{3!(3^0/1!+3^{-1}/0!)}*{2!(2^{-1}/0!)} = 80
total = 1024 = 4^5
6 點的
6 => 1*13800
4+2 => 15*78*1
3+3 => 10*8*8
2+2+2 => 15*1*1*1
total = 15625 = 5^6
: 注意我們並不會有任何一個functional digraph 有一個cc是三個node的
: 因為每個node都不能連到自己!
a -> b -> c -> a 不就是三個 node?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.122.136.75
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1469341510.A.943.html
※ 編輯: XII (140.122.136.75), 07/24/2016 14:32:23