作者yueayase (scrya)
看板Math
標題Re: [其他] 女生小圈圈
時間Tue Mar 21 18:03:52 2023
※ 引述《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://webptt.com/m.aspx?n=bbs/Math/M.1679393034.A.362.html
1F：推 QQrrr : 過幾天來研究這個看看 感謝 03/21 22:53
目前有個問題是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