作者yueayase (scrya)
看板Math
標題Re: [其他] 女生小圈圈
時間Mon Mar 20 22:46:32 2023
※ 引述《QQrrr (巧顆粒)》之銘言：
: 剛剛在八卦板看到
: https://i.imgur.com/QcoDXLt.jpg
: https://i.imgur.com/LRzUAbY.jpg
: 想請問一下為什麼好多人都回答32！
: 這是一個梗嗎？
: 如果不是的話
: 是什麼思考方式才會得出這個答案
: 認真好奇
不覺得是2^32-1這個所有{1,2,...,32}的非空子集合數...
應該是Strinling number of the second kind的和, ie. Bell number
(1)
https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
(2)
https://en.wikipedia.org/wiki/Bell_number
所以答案我覺得是:
32 32
B =Σ { }
32 k=0 k
32 1 k k-j k 32
{ } = ---Σ(-1) ( ) j
k k!j=1 j
要用程式算，我可能會用recurrence relation:
n+1 n n
{ } = k{ } + { } 做
k k k-1
這樣可以用dynamic programming的技巧
節省很多運算
下列python程式10行收工:
if __name__ == '__main__':
n = int(input('Enter n: '))
s = [[1 if i == j else 0 for j in range(n+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, i):
s[i][j] = j*s[i-1][j]+s[i-1][j-1]
bn = 0
for k in range(n+1):
bn += s[n][k]
print(bn)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.61.76 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1679323594.A.B15.html
1F：推 QQrrr : 他應該是要問最多可以同時有幾個小團體 03/20 22:54
2F：→ QQrrr : 這個解法應該是問如果每個人只能參加一個小圈圈 存 03/20 22:55
3F：→ QQrrr : 在幾種分類方式 03/20 22:55
嗯? 我怎麼覺得是可以partition成數個group，然後每一種partition代表一種可能?
eg: n = 4
{{{1,2,3,4}},
{{1,3,4},{2}, {{1},{{2,3,4}}, {{1,3}, {2,4}}, {{1,4},{2,3}}, {{1,2,4},{3}},
{{1,2},{3,4}, {{1,2,3},{4]}},
{{1,4},{2},{3}}, {{1},{2,4},{3}}, {{1},{2},{3,4}, {{1,2},{3},{4}},
{{2},{1,3},{4}}, {{2},{3},{1,4}, {{1},{2},{3},{4}}
}
每一個元素應該代表不同的情況?
}
※ 編輯: yueayase (61.227.61.76 臺灣), 03/20/2023 23:56:15
4F：推 j0958322080 : 也可以 1,2,3 一個，2,3,4 一個，1,3,4 又一個 03/21 00:47
什麼意思? {{1,2,3},{4]}} {{1},{{2,3,4}} {{1,3,4},{2}我不是列出來了?
※ 編輯: yueayase (61.227.61.76 臺灣), 03/21/2023 01:14:15
5F：推 sunev : 小圈圈不一定是要disjoint的partition，你可以想成 03/21 01:39
6F：→ sunev : line群 03/21 01:39
7F：推 QQrrr : 應該對題目的理解不同 03/21 01:40
8F：→ QQrrr : 一個是求最多有幾個小圈圈 03/21 01:40
9F：→ QQrrr : stirling是求分組的可能數 03/21 01:41
這個我真的有點好奇小圈圈的定義了...
如果每個人一定要選邊站，不能同時在2邊，那應該就是bell number
我查了一下小圈圈，也是有人覺得要選邊站...
所以... 我不知道XD
※ 編輯: yueayase (61.227.61.76 臺灣), 03/21/2023 02:19:35