PTT推薦

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

看板Gossiping標題Re: [問卦] 一個team有32個女生,會有幾個小團體?作者
yueayase
(scrya)
時間推噓 6 推:6 噓:0 →:1

※ 引述《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留言評論
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.227.61.76 (臺灣)
PTT 網址

eminem2003 03/21 00:35會X4好性感>///<

fly0204 03/21 00:37感覺好強

funyang 03/21 00:39感覺好閒

makinoyui 03/21 00:39嗯嗯 跟我想的一樣

ctw01 03/21 01:00會python就是一下 會chatgpd就是一下下下

bingripplw 03/21 01:522的32次方 之後減一 減32

ilovecat5566 03/21 08:08XDD