n色无限气球分配给k人的组合计数问题（两类约束）

嘿，这个组合数学问题我来给你拆解清楚，分两种约束情况逐一分析：

约束1：任意两人的颜色组合对均不相同 #

我们可以把问题拆成三个步骤来算：

• 第一步：先算单个用户能拿到的不同颜色组合数。因为要给每个人分2种不同颜色的气球，不考虑顺序的话，就是从n种颜色里选2种的组合数：$\binom{n}{2}$。
• 第二步：要给k个人分配完全不重复的组合对，得先从所有可能的组合里挑出k个不一样的，这一步的方式数是 $\binom{\binom{n}{2}}{k}$——也就是从$\binom{n}{2}$个组合中选k个的组合数。
• 第三步：因为k个人是不同的个体，选出来的k个组合还要对应分配给不同的人，这相当于对k个组合做全排列，方式数是 $k!$。

把这三步的结果相乘，就是约束1下的总分配方式数：
$$\binom{\binom{n}{2}}{k} \times k!$$

约束2：任意两人的颜色均无重复 #

这个约束比第一个严格得多——所有人用到的颜色都不能有重叠，相当于每个人的两个颜色和其他人的所有颜色都完全不重复（这里要注意：如果$2k > n$，那根本没法满足，分配方式数直接为0）。

同样拆成步骤推导：

• 第一步：先确定需要用到的颜色总数。每个人用2种不同颜色，且所有颜色不重复，所以总共需要 $2k$ 种颜色（前提是 $2k \leq n$）。
• 第二步：从n种颜色里选出这2k种颜色的方式数是 $\binom{n}{2k}$。
• 第三步：把这2k种颜色分成k个无序的颜色对（因为每个用户的两个颜色不区分顺序），分对的方式数是 $\frac{(2k)!}{2^k k!}$——这里解释下：2k个元素全排列是$(2k)!$，每个颜色对内部的两种颜色顺序不影响（比如红+蓝和蓝+红是同一个分配），所以要除以$2^k$；同时这k个颜色对本身的顺序不影响（还没分配给人），所以再除以$k!$。
• 第四步：把分好的k个颜色对分配给k个不同的人，这一步是全排列，方式数是 $k!$。

把这些步骤相乘，化简后得到约束2的总分配方式数：
$$\binom{n}{2k} \times \frac{(2k)!}{2^k}$$
也可以等价写成：
$$\frac{n!}{(n-2k)! \times 2^k}$$

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