作者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/cn.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