Re: [中學] 排列組合一題

看板Math作者woieyufan (微淋管)時間9年前 (2016/07/22 00:24)推噓6(6推 0噓 8→)

留言14則, 3人參與討論串11/23 (看更多)

※ 引述《steve1012 (steve)》之銘言： : 想要請教一題排列組合 : 因為沒什麼方向想請大家指點一些方向的就算只有關鍵字也好 : 假設我們現在有一堆點（點皆不同） : 每個點可以任選一個（只能選一個)其他的點連結 : 連完以後會產生一堆set : 我們定義只要有連到的就算一個set （類似connected component的概念) 舉例可以看到一個Set要終結就是最後一個未重複的node連到一個重複的node 所以最小單位是ABA型重複A不算兩個nodes組成一個set 2-node set: C(n,2)*C(1,1)/2! 任選2 選重複 ↑如果我沒有誤會的話ABA=BAB 3-node set: ABCA循環型 C(n,3)*3!*C(1,1)/(3!/2!) 任選3排列尾接首 ↑ABCA=BCAB=CABC≠ACBA ABCB拖尾型 C(n,3)*3!*C(2,1) 任選3排列尾接腹沒有異構 k-node set: 循環型 C(n,k)*k!/k 拖尾型 C(n,k)*k!*(k-1) 以上都蠻簡單共有n個node組成p個set (set1有k1個node,set2有k2個...) ↑這部分要用大小排序種類 k1≧k2≧k3... n=k1+k2+k3+.... 例如10=10=9+1=8+2=8+1+1=7+3=7+2+1=7+1+1+1.... p=1 p=2 p=2 p=3 p=2 p=3 p=4 (不知道含1的分法需不需要剔除，你沒規定必須要分完) 而這部分就是相同物組合經典問題無公式解結論是[C(n,k1)*(k1-1)!*[1+k1*(k1-1)]]*[C(n-k1,k2)*(k2-1)!*[1+k2*(k2-1)]]*..... : 假設 f(n,r) 代表n個node 裡面最大的set是r個這句我看不懂有n有r之後f代表什麼總之只要你確定set的大小就算得出種類數 -- 文章代碼(AID): #1DEd_TUP (Hunter) [ptt.cc] [非關] 湘北隊身高排第四高的是

推

ketoimo

01/22 19:42,

01/22 19:42

推

starya

01/22 21:08,

01/22 21:08

推

askaiverson

01/22 22:51,

01/22 22:51

→

dq0327

01/22 23:24,

01/22 23:24

→

devilcavalry

01/23 00:16,

01/23 00:16

-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.216.161.190 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1469118269.A.71A.html ※ 編輯: woieyufan (61.216.161.190), 07/22/2016 00:33:10

推

steve1012

07/22 00:44, , 1^F

07/22 00:44, 1^F

推

steve1012

07/22 11:16, , 2^F

07/22 11:16, 2^F

→

steve1012

07/22 11:16, , 3^F

07/22 11:16, 3^F