指定元素相对位置的排列计数

题型说明

题面长这样：$n$ 个互不相同的对象排成一排，另加一句只涉及指定的 $k$ 个对象彼此之间的位置关系——

• $A$ 排在 $B$ 前面；
• $A$、$B$ 都在 $C$ 的同一侧；
• $C$ 不夹在 $A$、$B$ 之间；
• 甲、乙、丙三人从左到右身高递增。

关键在于：条件不点名具体位次，也不牵扯其余 $n-k$ 个对象。 一旦题面出现「第一位不能是……」 「甲乙必须相邻」这类话，就不再是纯相对位置，得另配捆绑法或插空法。

三个入口

• 相对次序等分（最快）：$k$ 个元素的 $k!$ 种次序把 $n!$ 个排列均分，数出合格次序数即可一步得数， 见只看几个元素的相对次序。
• 按关键元素的位置分类（最稳）：让那个”分界”的元素（上面例子里的 $C$）依次站到第 $1,2,\dots,n$ 位， 每种位置下用排列数数一遍再相加。左右对称时只算一半再乘 $2$。
• 补集：合格的情形分好几类而不合格的只有一类时，用总数减，见正难则反用补集。

这类题的关口

• 「同侧」不是「相邻」：同侧只要求都在左边或都在右边，中间隔多少个都行，两者的算法完全不同。
• 分类要不重不漏：按位置分类时，$C$ 站在中间几位会同时有”都在左”和”都在右”两支， 漏掉其中一支是这类题最常见的失分点，见分类计数重复或遗漏。
• 对称性只是省力，不是免检：用「左右对称，算一半乘 $2$」之前，要确认条件本身左右对称 （「$A$、$B$ 在 $C$ 同侧」对称，「$A$ 在 $C$ 左边」不对称）。
• 不要去排其余元素的细节：那 $n-k$ 个元素永远贡献一个公因子 $(n-k)!$，把它提出来能让式子短一大截。