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

[woieyufan (微淋管)]

※ 引述《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:高一時，三井對安西說他所有位置都可以打
推 starya:只要三井的手上有球
推 askaiverson:誰都打不死他......
→ dq0327:那三井什麼時候沒有球?
→ devilcavalry:木暮投三分球的時候
--
※ 發信站: 批踢踢實業坊(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   : 喔喔必須分完
推 steve1012   : 想請教一下 若給n個點的話 理論上應該共有(n-1)^N
→ steve1012   : 種排列組合吧?
→ XII         : 不一定只有一條尾巴吧?
→ XII         : n nodes有Σ_{k=2..n} (n!/(n-k)!)*n^{n-k-1}種
推 steve1012   : 請問是指n node的小social network 有這麼多種嗎
→ steve1012   : 還是指總共應該有這麼多種
→ steve1012   : 若是講總共的話 不是應該是每個node都可以選一個別o
→ steve1012   : 所以每個人都有(n-1)種選擇 共n^(n-1)總
→ XII         : 當然是 n node 的小 social network的個數
推 steve1012   : 太神了 可以請教思考的方向嗎
推 XII         : Prufer code
→ woieyufan   : 真的忽略了多尾....
推 steve1012   : 不過似乎跟答案對不太起來 我在原本那篇重打題目好