带约束条件的7矮人分配7项任务的方案数计算问题

这是一个带约束的全排列计数问题，我们可以通过分情况讨论结合容斥原理来逐步计算合法方案数，下面是具体的拆解过程：

问题回顾 #

我们有7名矮人（D1-D7）和7项任务（T1-T7），每名矮人仅承担一项任务，约束条件为：

• D1不能做T1
• D4不能做T2
• D5不能做T6
• D6不能做T3和T7

情况1：任务T1分配给D4 #

当T1确定分配给D4时，我们需要为剩下的6名矮人（D1、D2、D3、D5、D6、D7）分配剩下的6项任务（T2-T7），此时原约束中“D4不能做T2”自动满足，剩余有效约束为：

• D5不能做T6
• D6不能做T3、T7

我们用容斥原理计算这种情况的合法方案数：

1. 总排列数：6! = 720
2. 减去不符合约束的情况：
   • 设A为D5做T6的分配集合，|A|=3×4! =72（D5固定T6后，D6有3种可选任务，剩余4人全排列）
   • 设B为D6做T3的分配集合，|B|=4×4! =96（D6固定T3后，D5有4种可选任务，剩余4人全排列）
   • 设C为D6做T7的分配集合，|C|=4×4! =96（和B对称）
3. 加回重复减去的重叠情况：
   • |A∩B|=4! =24（D5固定T6且D6固定T3，剩余4人全排列）
   • |A∩C|=4! =24（和A∩B对称）
4. 不存在三重重叠的情况（D6不能同时做T3和T7），所以无需额外调整

最终情况1的合法方案数为：
720 - (72+96+96) + (24+24) = 504

情况2：任务T1不分配给D4 #

此时T1只能从D2、D3、D5、D6、D7这5名矮人中选择，我们再细分3种子情况：

子情况2a：T1分配给D5（1种选择） #

剩余矮人：D1、D2、D3、D4、D6、D7；剩余任务：T2-T7
原约束中“D5不能做T6”自动满足，剩余有效约束为：

• D4不能做T2
• D6不能做T3、T7

计算逻辑和情况1完全一致，合法方案数为：504

子情况2b：T1分配给D6（1种选择） #

剩余矮人：D1、D2、D3、D4、D5、D7；剩余任务：T2-T7
原约束中“D6不能做T3、T7”自动满足，剩余有效约束为：

• D4不能做T2
• D5不能做T6

用容斥原理计算：

1. 总排列数：6! =720
2. 减去D4做T2的情况（5! =120）和D5做T6的情况（5! =120）
3. 加回同时满足D4做T2且D5做T6的情况（4! =24）

合法方案数为：720 -120 -120 +24 =504

子情况2c：T1分配给D2、D3或D7（共3种选择，对称等价） #

以T1分配给D2为例，剩余矮人：D1、D3、D4、D5、D6、D7；剩余任务：T2-T7，所有原约束都有效：

• D4不能做T2
• D5不能做T6
• D6不能做T3、T7

用容斥原理计算单种选择的合法方案数：

1. 总排列数：6! =720
2. 减去不符合约束的单个情况：120×4=480（D4做T2、D5做T6、D6做T3、D6做T7各120种）
3. 加回重复减去的两两重叠情况：24×5=120（除了D6同时做T3和T7的不可能情况，其余5种两两组合各24种）
4. 减去重复加回的三重重叠情况：6×2=12（仅D4做T2+D5做T6+D6做T3、D4做T2+D5做T6+D6做T7这两种可能，各6种）

单种选择的合法方案数为：720 -480 +120 -12 =348
3种选择的总方案数为：3×348=1044

总合法方案数 #

将所有情况的方案数相加：
504（情况1） +504（子2a） +504（子2b） +1044（子2c）=2556

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