[中學] 排列組合一題

[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
比如說我們現在有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的
注意我們並不會有任何一個functional digraph 有一個cc是三個node的
因為每個node都不能連到自己!

以下為我原本寫的
==========================================================

假設我們現在有一堆點 （點皆不同）
每個點可以任選一個（只能選一個)其他的點連結
連完以後會產生一堆set
我們定義只要有連到的就算一個set （類似connected component的概念)
舉例來說 假設現在有ABCD 四個node
A->C
B->C
D->C
C->B

則會變成一個總共有四個node的set

舉另外一個例子來說
A->C
C->A
B->D
D->B
則會變成兩個set 各有兩個元素

我想要算每個大小的set各有幾個
因為跟自己有學過的排列組合都稍有不同  一時間想不到什麼方法
上網稍微查了各種排列組合問題以後
覺得partial ordered set似乎有點關聯 但又不確定
懇請大家給點方向

另外也有想到recurrence的關係 設有n個node
則在多一個node的時候(n+1個node) 情況為
所有n node的set 都多一個node


補充:
看了回文推的關鍵字找到的paper以後
("The number of structures of finite relations")
我想重新寫一下我想講的東西
就是現在有一堆node 那每個node可以想成一個人
每個人只想跟一個人有關聯(一條edge)
所以每個人都會有一個out degree
假設有關聯的人同屬一個set (小的social network)
我想要知道最大的set大小的期望值
所以我就需要算這個set的大小 與個數
因為每個人都會有一條edge出去 所以不會有單個node的情形

其實paper好像可以延伸出解答. 但我不是本科系的看得有點不太懂 還在理解中
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 199.119.244.15
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1469066501.A.342.html
※ 編輯: steve1012 (199.119.244.15), 07/21/2016 10:16:05
→ softseaweed : 單純看set的話 {A->B, B->C} 跟 {B->A, C->A}產生出
→ softseaweed : 來的不都是{A,B,C}? 還是我的理解錯誤?
→ softseaweed : 這樣不就n choose r?
每一點都一定要連一個edge 出去 所以這樣你c起碼要連回去
再舉個例子 要有一個set 有四個node的話可以
A->C, B->C, C->A, D->C
也可以把C->A換成A->C
所以每一種有很多方法

※ 編輯: steve1012 (199.119.244.15), 07/21/2016 11:19:42
※ 編輯: steve1012 (199.119.244.15), 07/21/2016 11:21:35
推 yclinpa     : Try "functional digraph"
大感恩 雖然只有查到paper但有些基本的想法了
正因為每個set都只會有一個loop 以三個element的set為例
有可能有一個互聯的pair(cycle) 配上一個node連過去任何一點
也有可能是一個大的cycle
所以可以按照cycle以外的點的數量來分類
另外任意兩個structure要isomorphism 的條件就是要找得到一一對應的permutation
這兩個配合起來可能就有答案了!
想請教y大是怎麼學到的呢？ 我查functional digraph只有一本很舊的書跟一堆論文lol
※ 編輯: steve1012 (199.119.244.15), 07/21/2016 12:36:00
→ XII         : 你的set是指集合?還是就只是連的方式?
我補充在上面了！
應該是集合 但我想要知道有幾個集合
※ 編輯: steve1012 (199.119.244.15), 07/22/2016 13:44:02
→ XII         : 你說你的set是小的network,那應該就不是指集合吧?
對 就是有哪些人也是很重要的
因為我要算總共有幾種不同的情形
※ 編輯: steve1012 (199.119.244.15), 07/22/2016 14:08:48
推 XII         : n nodes有Σ_{k=2..n} (n!/(n-k)!)*n^{n-k-1}種
我剛對了一下答案還是不太對
以四個node ABCD來說 總共有3^4=81種
其中兩組2node的pair共有 C(4,2)/2 = 3 種
就是 A<->B C<->D
A<->C B<->D
跟A<->D B<->C
其他4node的小socianl network 有78種
※ 編輯: steve1012 (68.180.36.254), 07/24/2016 01:11:05
※ 編輯: steve1012 (68.180.36.254), 07/24/2016 06:58:51
推 XII         : 4!(4^1/2!+4^0/1!+4^ﴭ1)/0!）=78
→ XII         : 剛用手機推文..有點怪怪的...