kn元集上各等价类大小为n的等价关系数目猜想验证

这是个挺有意思的组合计数问题，咱们一步步拆解清楚：

首先明确问题定义：

• 给定正整数k、n，集合S的大小为kn；
• M是S上满足每个元素的等价类大小恰好为n的等价关系数目（等价关系对应集合的划分，所以M本质是把S分成k个互不相交的n元子集的无序划分的数目）。

你的猜想推导与问题所在 #

你猜想$ M = \prod_{i=1}^{k} \binom{in}{n} $，咱们先展开这个乘积看看结果：

• 当i=1时，$\binom{n}{n}=1$
• i=2时，$\binom{2n}{n}=\frac{(2n)!}{n!n!}$
• i=3时，$\binom{3n}{n}=\frac{(3n)!}{(2n)!n!}$
• ...
• i=k时，$\binom{kn}{n}=\frac{(kn)!}{((k-1)n)!n!}$

把这些项相乘，中间的阶乘会依次抵消，最终得到：
$$\prod_{i=1}^{k} \binom{in}{n} = \frac{(kn)!}{(n!)^k}$$

但这里有个关键问题：等价关系对应的划分是不区分等价类的顺序的。比如把S分成{A,B}和{C,D}，跟分成{C,D}和{A,B}，这是同一个等价关系，但你的推导是按顺序选取等价类（先选第一个n元子集，再选第二个，以此类推），相当于给这些等价类赋予了顺序，这样就多计算了k!倍（k个等价类共有k!种排列方式）。

正确的M表达式 #

要得到无序划分的数目，需要把有序划分的数目除以k!，所以正确的M应该是：
$$M = \frac{(kn)!}{(n!)^k k!} = \frac{1}{k!}\prod_{i=1}^{k} \binom{in}{n}$$

小例子验证 #

咱们用具体数值验证一下：

• 当k=2，n=1时，kn=2，正确的等价关系数目是1（只有一种方式让两个元素等价）。按你的猜想计算得$\binom{1}{1}*\binom{2}{1}=2$，是正确值的2倍（即k!倍）；
• 当k=2，n=2时，kn=4，正确的划分数目是3（{1,2}&{3,4}、{1,3}&{2,4}、{1,4}&{2,3}）。按你的猜想计算得$\binom{2}{2}*\binom{4}{2}=6$，同样是正确值的2倍。

这完全符合咱们的结论，说明你的猜想因为没有考虑等价类的无序性，多算了k!倍，因此并不成立。

内容的提问来源于stack exchange，提问作者IMK