5个M、5个S、5个T约束排列问题：统计M与T不相邻、首尾为M和T的合法排列数

核心约束梳理 #

先明确已知条件：

• 共5只猴子(M)、5条蛇(S)、5只老虎(T)，同物种不可区分
• 队列首字符固定为M，尾字符固定为T
• 不允许出现MT或TM的相邻组合（M和T不能相邻）

解法1：数学组合推导 #

关键逻辑推导 #

因为M和T不能直接相邻，所有M块（连续的M）、T块（连续的T）之间必须被至少1个S隔开，且同物种的连续个体合并为一个块后，非S块的序列必然是M、T交替的：

1. 队列首是M块、尾是T块，交替序列下M块的数量必然等于T块的数量，记为k
2. k个M块 + k个T块共有2k-1个缝隙，每个缝隙至少放1个S，共需要2k-1个S
3. 总共有5个S，因此2k-1 ≤5，即k最大为3，k的取值范围是1、2、3
4. 剩余可自由分配的S数量为5 - (2k-1) = 6-2k，用隔板法分配到2k-1个缝隙中，每个缝隙可放0个或多个

分情况计算 #

k=1（1个M块，1个T块）

• 5个M分1块：组合数C(4,0)=1（n个元素分k块的组合数为C(n-1,k-1)）
• 5个T分1块：组合数C(4,0)=1
• 剩余S数量：6-2*1=4，分配到1个缝隙的组合数C(4 +1-1,1-1)=1
• 本情况总排列数：1*1*1=1

k=2（2个M块，2个T块）

• 5个M分2块：组合数C(4,1)=4
• 5个T分2块：组合数C(4,1)=4
• 剩余S数量：6-2*2=2，分配到3个缝隙的组合数C(2 +3-1,3-1)=C(4,2)=6
• 本情况总排列数：4*4*6=96

k=3（3个M块，3个T块）

• 5个M分3块：组合数C(4,2)=6
• 5个T分3块：组合数C(4,2)=6
• 剩余S数量：6-2*3=0，分配到5个缝隙的组合数C(0 +5-1,5-1)=1
• 本情况总排列数：6*6*1=36

最终结果 #

所有情况相加：1+96+36=133

解法2：回溯剪枝编程实现 #

暴力枚举9万种排列效率低，用回溯+剪枝可以提前排除不合法分支，计算速度极快，Python实现代码如下：

count = 0

def backtrack(prev_char, rem_m, rem_s, rem_t, cur_len):
    global count
    # 已经填了14个字符，最后一个必须是T，且前一个字符不能是M
    if cur_len == 14:
        if rem_t == 1 and prev_char != 'M':
            count += 1
        return
    # 尝试放M：还有剩余M，且前一个不是T（避免TM相邻）
    if rem_m > 0 and prev_char != 'T':
        backtrack('M', rem_m-1, rem_s, rem_t, cur_len+1)
    # 尝试放S：还有剩余S，无相邻限制
    if rem_s > 0:
        backtrack('S', rem_m, rem_s-1, rem_t, cur_len+1)
    # 尝试放T：剩余T至少留1个放末尾，且前一个不是M（避免MT相邻）
    if rem_t > 1 and prev_char != 'M':
        backtrack('T', rem_m, rem_s, rem_t-1, cur_len+1)

# 初始状态：第一个字符是M，剩余M=4，S=5，T=5，当前长度1
backtrack('M', 4, 5, 5, 1)
print(count)

运行代码输出结果为133，和数学推导结果一致。

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