※ 引述《ilovecat5566 (....)》之铭言：
: 问一个数学问题
: 如果一个team有32个女生
: 会有几个小团体呢？
: 有没有机率高手可以来算一下
: 有没有卦？0.0
我觉得应该要用Stirling Number of the Second Kind和Bell Number:
(1) https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
代表把n个物品分成k个非空子集合的组合数S(n,k), 其中
k k-j n
S(n,k) = Σ(-1) C(k,j)j / k!, 0≦k≦n
j=0
(2) https://en.wikipedia.org/wiki/Bell_number
代表把n个物品分成数个非空子集合的组合数Bn
n
Bn = Σ S(n,k)
k=0
例如: n=4可分割成
{{1,2,3,4}} => k = 1
{{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}} => k = 2
{{1,4},{2},{3}}、{{1},{2,4},{3}}、{{1},{2},{3,4}}、{{1,3},{2},{4}}、
{{1},{2,3},{4}}、{{1,2},{3},{4}} => k = 3
{{1},{2},{3},{4}} => k = 4
=> S(4,1) = 1, S(4,2) = 7, S(4,3) = 6, S(4,4)=1
B = S(4,1)+S(4,2)+S(4,3)+S(4,4) = 15
4
32
所以原问题的答案就是B = Σ S(n,k)
32 k=0
这个大概用程式跑会比较适合...
但如果用上面的explicit formula会比较没有效率，
所以会用S(n,k)的recurrence relation来计算:
S(n,k) = k*S(n-1,k)+S(n-1,k-1), 0 < k < n
= 1, n = k
= 0, n = 0 or k = 0
这样就可以用计算C(n,k)一样的技巧，用dynamic programming做:
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)
当n=32时，答案是:
128064670049908713818925644
还蛮多的XD