Re: [其他] 女生小圈圈

[yueayase (scrya)]

※ 引述《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://www.ptt.cc/bbs/Math/M.1679323594.A.B15.html
推 QQrrr       : 他應該是要問最多可以同時有幾個小團體
→ QQrrr       : 這個解法應該是問如果每個人只能參加一個小圈圈 存
→ QQrrr       : 在幾種分類方式
嗯? 我怎麼覺得是可以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
推 j0958322080 : 也可以 1,2,3 一個，2,3,4 一個，1,3,4 又一個
什麼意思? {{1,2,3},{4]}} {{1},{{2,3,4}} {{1,3,4},{2}我不是列出來了?
※ 編輯: yueayase (61.227.61.76 臺灣), 03/21/2023 01:14:15
推 sunev       : 小圈圈不一定是要disjoint的partition，你可以想成
→ sunev       : line群
推 QQrrr       : 應該對題目的理解不同
→ QQrrr       : 一個是求最多有幾個小圈圈
→ QQrrr       : stirling是求分組的可能數
這個我真的有點好奇小圈圈的定義了...
如果每個人一定要選邊站，不能同時在2邊，那應該就是bell number
我查了一下小圈圈，也是有人覺得要選邊站...
所以... 我不知道XD
※ 編輯: yueayase (61.227.61.76 臺灣), 03/21/2023 02:19:35