带约束条件的5字母可重复12长度组合数求解咨询

咱们可以把这个问题拆成A使用5次和A使用6次两个独立场景来分析，最后把两个场景的结果加起来就是总数了。

场景1：A用5次 #

这时候还需要凑7个字母（12-5=7），由B、C、D、E来分配，要求每个字母用1-3次，同时得遵守「如果B用3次，那C只能用1次」的规则。

先算无额外约束（仅满足1-3次）的总组合数 #

首先得找出B、C、D、E的次数分配方案，满足b+c+d+e=7且每个数在1-3之间。通过变量替换（把每个数减1，转化为非负整数解），再用容斥原理算出共有16种分配方案，分成两类：

• 类型1：3,2,1,1：有一个字母用3次，一个用2次，剩下两个用1次。这种分配的排列方式有C(4,1)*C(3,1)=12种（先选哪个字母用3次，再选哪个用2次）。对应的多重排列数是：

  12!/(5!×3!×2!×1!×1!) = 479001600/(120×6×2) = 332640
  

  这部分总组合数是12×332640=3991680。
• 类型2：2,2,2,1：三个字母用2次，一个用1次。排列方式有C(4,1)=4种，对应的多重排列数是：

  12!/(5!×2!×2!×2!×1!) = 479001600/(120×8) = 498960
  

  这部分总组合数是4×498960=1995840。

无约束的总组合数就是3991680+1995840=5987520。

再减去违反约束的组合数 #

违反约束的情况是B用3次且C用≥2次。当B=3时，剩下的C+D+E=4，同时C≥2、D≥1、E≥1。试一下就知道，只有C=2,D=1,E=1这一种分配（如果C=3，那D+E=1，满足不了D和E至少1次的要求）。这种分配对应的组合数就是上面的332640。

所以场景1的有效组合数是5987520-332640=5654880。

场景2：A用6次 #

这时候需要凑6个字母（12-6=6），根据规则，B、C、D、E每个最多用2次，且至少用1次。同样做变量替换，转化后得到分配方案是2,2,1,1：两个字母用2次，两个用1次。这种分配的排列方式有C(4,2)=6种（选哪两个字母用2次）。

对应的多重排列数是：

12!/(6!×2!×2!×1!×1!) = 479001600/(720×4) = 166320

场景2的总组合数是6×166320=997920。

最终结果 #

把两个场景的结果加起来：5654880+997920=6652800。

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