数学 / 排列组合 · 从计数原理到 P(n,k) 与 C(n,k) / 带约束的排列 待审核 5 / 25
constrained · 插空法 / 捆绑法

带约束的排列

现实里的排列常带一句附加条件，最常见的两类是「某些元素两两不相邻」与「某些元素必须相邻」。它们各有一个对偶的标准技巧，插空法与捆绑法。两者都不是新公式，只是乘法原理与排列数的组合运用：把无约束的部分先排好，再用一步受控的选位安置受约束的部分。

1 · 插空法

non-adjacent · k! × P(k+1, m)

要让 mm 个元素两两不相邻，正面逐个排布很难保证这个条件。换个角度：先把其余 kk 个可以相邻的元素排成一列作骨架，这一步有 k!k! 种。骨架排好后，元素之间与两端一共形成 k+1k+1 个空隙；只要让每个受约束元素各占一个不同的空隙，它们就被骨架天然隔开。从 k+1k+1 个空隙里有序地放入 mm 个，正是 P(k+1,m)P(k+1, m)，故总数为

k! ×P(k+1, m)k!\, \times P(k+1,\, m)
图 1-1 · 骨架长度与空隙数的对应。可拖动滑块，观察空隙数如何随骨架长度变化，以及总方案数的两个因子各自的来源。
图 1-2 · 固定骨架时的全部插法。骨架不再排它的 k!k! 种顺序，只枚举把受约束元素插入空隙的 P(k+1,m)P(k+1, m) 种结果；每行里高亮的插入元素之间至少隔着一个骨架元素。

2 · 捆绑法

adjacent · (k+1)! × m!

对偶的问题是让 mm 个元素必须相邻。既然它们必须连在一起，就把这 mm 个捆成一个整体当作单独一个元素，与其余 kk 个自由元素一起排，共 k+1k+1 个单元，有 (k+1)!(k+1)! 种；捆内部这 mm 个元素自己还能换序，再乘 m!m!：

(k+1)! ×m!(k+1)!\, \times m!
图 2-1 · 受约束元素捆成整体后参与排列的过程。可拖动滑块，观察捆作为一个单元如何进入全排列、捆内换序又贡献多少。

插空与捆绑是一对互补的思路：不相邻用插空，把受约束元素拆开塞进不同空隙；相邻用捆绑，把受约束元素合并成一个整体。两者都把带约束的排列化归为一次普通全排列加一步选序，本质仍是排列。若要按字典序真正生成这些排列，见算法系列排列生成。

3 · 参考文献

  1. Permutation. Wikipedia. 排列与 P(n,k)P(n, k)，带约束排列是其常见变体。https://en.wikipedia.org/wiki/Permutation
  2. Inclusion–exclusion principle. Wikipedia. 约束更复杂时（多组不相邻）插空之外还需容斥。https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle