※ 引述《rtyxn ()》之铭言： : ※ 引述《QQrrr (巧颗粒)》之铭言： : : 刚刚在八卦板看到 : : https://i.imgur.com/QcoDXLt.jpg : : https://i.imgur.com/LRzUAbY.jpg : : 想请问一下为什麽好多人都回答32！ : : 这是一个梗吗？ : : 如果不是的话 : : 是什麽思考方式才会得出这个答案 : : 认真好奇 : 虽然我後来说 2^32 - 1 是错的，但想了想又觉得还是对的： : 总人数为1的时候，显然只有1个团体。 : 总人数为2的时候，这会有3个团体，这3个怎麽来呢？由於这个问题想要凸显女生之间彼 : 此竞争又合作、勾心斗角的关系，因此这2人可能结合成1个团体，但彼此又在心里为自 : 己的利益盘算，所以也要考虑1人成1团的状况，这样就有3个团体了。 : 总人数为3的时候，我们仿造上例，分别考虑1人1团、2人1团、3人1团的情况，这样会得 : 到7个团体。需注意的是，甲、乙、丙三人分团的时候，有可能会出现(甲乙)、(乙丙)的 : 关系，当然，就如前面所说，乙其实也可看成自己1团，她只是为了某种利益，表面上各 : 自与甲、丙交好，最後，她们三人也可能表面上一派和气形成3人1团，实则内部波涛汹 : 涌、各自暗藏心机。 : 以此类推，当总人数为32的时候，我们可得到 2^32 - 1 个的分团方式。 : Aside: 其实男生也是很会斗的... 我想到，如果有所谓的主从关系的话... 组成一个小圈圈的可能组合数有多少? 也许可以想成k个人，可以形成多少种forest的问题... 而这个我找到的答案是: https://reurl.cc/o0VRa3 那麽可以变成选出k个人*k个人有几个forest，然後加总起来 也就是 n Σ C(n, k)*S(k), S(k)如上面连结 k=1 就可以写成以下程式码: if __name__ == '__main__': n = int(input('Enter n: ')) c = [[1 if j == 0 or j == i else 0 for j in range(n+1)] for i in range(n+1)] for i in range(2, n+1): for j in range(1, i): c[i][j] = c[i-1][j] + c[i-1][j-1] k_pow = [0 if i == 0 else int(i**(i-2)) for i in range(n+1)] s = [1 if i == 0 else 0 for i in range(n+1)] for i in range(1, n+1): for j in range(1, i+1): s[i] += c[i-1][j-1]*k_pow[j]*s[i-j] total = 0 for i in range(1, n+1): total += c[n][i]*s[i] print(total) 这里同样用dynamic programming节省运算时间 n=32时得到: 3785663207985408304804860909707100592991771168 但这个我就不确定合不合理了... --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.47.87.231 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1679393034.A.362.html 目前有个问题是Cayley formula的图中 1 2 3 / \ / \ / \ 为k=3的3种可能 2 3 1 3 1 2 但有趣的是: 1 \ 2 这个也许可以视为跟上面第一个是一样的 / 3 不过边如果有向就不同的话... 是否应该再乘上2^2 = 2^(3-1)? (表示进出2种不同的方向，对每一个边考虑) 那也许 k^(k-2)这项，应该要再乘上2^(k-1)?(k个点的tree有k-1条边) ※ 编辑: yueayase (114.47.87.231 台湾), 03/22/2023 00:20:39