Re: [其他] 女生小圈圈

[yueayase (scrya)]

※ 引述《rtyxn ()》之銘言：
: ※ 引述《QQrrr (巧顆粒)》之銘言：
: : 剛剛在八卦板看到
: : https://i.imgur.com/QcoDXLt.jpg
: : https://i.imgur.com/LRzUAbY.jpg
: : 想請問一下為什麼好多人都回答32！
: : 這是一個梗嗎？
: : 如果不是的話
: : 是什麼思考方式才會得出這個答案
: : 認真好奇
: 雖然我後來說 2^32 - 1 是錯的，但想了想又覺得還是對的：
: 總人數為1的時候，顯然只有1個團體。
: 總人數為2的時候，這會有3個團體，這3個怎麼來呢？由於這個問題想要凸顯女生之間彼
: 此競爭又合作、勾心鬥角的關係，因此這2人可能結合成1個團體，但彼此又在心裡為自
: 己的利益盤算，所以也要考慮1人成1團的狀況，這樣就有3個團體了。
: 總人數為3的時候，我們仿造上例，分別考慮1人1團、2人1團、3人1團的情況，這樣會得
: 到7個團體。需注意的是，甲、乙、丙三人分團的時候，有可能會出現(甲乙)、(乙丙)的
: 關係，當然，就如前面所說，乙其實也可看成自己1團，她只是為了某種利益，表面上各
: 自與甲、丙交好，最後，她們三人也可能表面上一派和氣形成3人1團，實則內部波濤洶
: 湧、各自暗藏心機。
: 以此類推，當總人數為32的時候，我們可得到 2^32 - 1 個的分團方式。
: Aside: 其實男生也是很會鬥的...

我想到，如果有所謂的主從關係的話... 組成一個小圈圈的可能組合數有多少?
也許可以想成k個人，可以形成多少種forest的問題...
而這個我找到的答案是:
https://reurl.cc/o0VRa3
那麼可以變成選出k個人*k個人有幾個forest，然後加總起來
也就是
 n
Σ C(n, k)*S(k), S(k)如上面連結
k=1

就可以寫成以下程式碼:
if __name__ == '__main__':
    n = int(input('Enter n: '))
    c = [[1 if j == 0 or j == i else 0 for j in range(n+1)] for i in
range(n+1)]
    for i in range(2, n+1):
        for j in range(1, i):
            c[i][j] = c[i-1][j] + c[i-1][j-1]
    k_pow = [0 if i == 0 else int(i**(i-2)) for i in range(n+1)]
    s = [1 if i == 0 else 0 for i in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, i+1):
            s[i] += c[i-1][j-1]*k_pow[j]*s[i-j]

    total = 0
    for i in range(1, n+1):
        total += c[n][i]*s[i]
    print(total)

這裡同樣用dynamic programming節省運算時間
n=32時得到: 3785663207985408304804860909707100592991771168

但這個我就不確定合不合理了...

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.47.87.231 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1679393034.A.362.html
推 QQrrr       : 過幾天來研究這個看看 感謝
目前有個問題是Cayley formula的圖中

 1    2     3
/ \  / \   / \  為k=3的3種可能
2 3  1 3  1   2

但有趣的是:

1
 \
  2 這個也許可以視為跟上面第一個是一樣的
 /
3

不過邊如果有向就不同的話...

是否應該再乘上2^2 = 2^(3-1)? (表示進出2種不同的方向，對每一個邊考慮)

那也許 k^(k-2)這項，應該要再乘上2^(k-1)?(k個點的tree有k-1條邊)
※ 編輯: yueayase (114.47.87.231 臺灣), 03/22/2023 00:20:39