集合S分组方案

abababa

给定集合$S$，元素个数记为$\abs{S}$。再给定一个正整数$k$，满足$k$能整除$\abs{S}$。对$S$分组，每组有$k$个无重复的元素，全部分完时记为一个方案。例如$S=\{1,2,3,4\},k=2$，则$\{1,2\},\{3,4\}$是其中一个方案。那么这样的方案有几种？要怎么全部列出来？

这个问题有没有什么名字？全部列出来那个是需要编程吧，我目前只懂一点点javascript，要怎么才能做出来？比如就令$S$是从1到1000的所有整数，$k=5$这样。

kuing

记 `n=\abs S`，则方案数为
\[\frac{C_n^kC_{n-k}^kC_{n-2k}^k\cdots C_k^k}{(n/k)!},\]
（即每次取 k 个元素至取完，但各组无需考虑顺序，所以除以组数的全排列 (n/k)!）
化简为
\[\frac{n!}{(k!)^{n/k}(n/k)!}.\]
（这个式子也可以这样理解：
所有元素的全排列，在每组的内部重复计算了 k!，组也重复计算了 (n/k)!，所以这样除）

abababa

kuing 发表于 2023-12-27 18:40
记 `n=\abs S`，则方案数为
\[\frac{C_n^kC_{n-k}^kC_{n-2k}^k\cdots C_k^k}{(n/k)!},\]
化简为

谢谢，看这样，感觉是不能用编程列出$\abs{S}=1000,k=5$的情况了。

kuing

abababa 发表于 2023-12-27 20:58
谢谢，看这样，感觉是不能用编程列出$\abs{S}=1000,k=5$的情况了。

哦，你指的是数量太多了是吗😅确实，别说1000，20都已经上亿……

我用 mma 写了一个数字比较小的 |S|=12, k=3：

1. n = 12;
2. s = Range[n];
3. k = 3;
4. fzs = {};
5. w1 = Subsets[Range[2, n], {k - 1}];
6. w2 = Subsets[Range[2, n - k], {k - 1}];
7. w3 = Subsets[Range[2, n - 2 k], {k - 1}];
8. Do[z1 = {s[[1]]}~Join~s[[w1[[i]]]];
9. s2 = Complement[s, z1];
10. z2 = {s2[[1]]}~Join~s2[[w2[[j]]]];
11. s3 = Complement[s2, z2];
12. z3 = {s3[[1]]}~Join~s3[[w3[[p]]]];
13. z4 = Complement[s3, z3];
14. fzs = Append[fzs, {z1, z2, z3, z4}], {i, Length[w1]}, {j, Length[w2]}, {p, Length[w3]}]
15. Length[fzs]
16. Export["D:/0.txt", fzs]

Copy the Code

运行约 3 秒出数字 15400 即一共 15400 种分组方案，然后去 D 盘打开生成的 0.txt 就是具体分组结果。

abababa

kuing 发表于 2023-12-28 01:55
哦，你指的是数量太多了是吗😅确实，别说1000，20都已经上亿……

我用 mma 写了一个数字比较小的 |S|=12 ...

是的，数太大，用Mathematica算了那个1000,5的，得到一长串，我一看那么长还以为是分组结果，后来才意识到只是方案个数。