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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.61.76 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1679330053.A.D31.html