Re: [問卦] 一個team有32個女生，會有幾個小團體？

※ 引述《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

--