排列組合奇妙冒險：如何優雅地避開"數字CP"？

——容斥原理教你破解連續數對排列難題

📜 問題描述

題目：求$1,2,3,4,5,6,7,8$的排列個數，使得排列中不出現連續的$12,23,34,45,56,67,78$．

通俗版：把數字1到8排成一隊，但禁止任何兩個相鄰數字"秀恩愛"（比如$1$和$2$不能手拉手出現，$2$和$3$也不行……）．問有多少種"單身狗友好型"排列？

---

💡 破題思路：逆向思維yyds！

第一反應：直接算"不連續"的排列數？頭皮發麻！
靈光一閃：不如先算"有連續CP"的排列數，再用總排列數減去它！（容斥原理狂喜）

核心工具：

1. 捆綁法：把連續數對（如$12$）看作一個"超級數字"，減少排列對象．
2. 容斥原理：處理多個集合的交并時，"加加減減"避免重復計數．

---

🔍 關鍵推導：容斥魔法

Step 1：定義"違規集合"

設$A_i$為包含$i(i+1)$這一對連續數的所有排列（$i=1,2,\dots ,7$）．
例如：$A_1$包含所有出現$12$的排列，$A_2$包含所有出現$23$的排列……

Step 2：計算交集大小

關鍵結論：若同時有$k$個連續數對（比如$12$和$23$），相當于把$k+1$個數字"黏成"$8?k$個整體．
公式：$|A_{i_1}\cap A_{i_2}\cap \dots \cap A_{i_k}|=(8?k)!$．

💡 舉例：同時滿足$12$和$23$的排列，相當于把$1,2,3$捆成一個"大粽子"，剩下數字自由排列，共$(8?2)!=720$種．

Step 3：容斥原理展開

總"違規排列數"為所有$A_i$的并集大小，展開計算：
$$\begin{array}{rl}\left|\underset{i=1}{\overset{7}{?}}{A}_i\right|& =\sum _{k=1}^7(?1{)}^{k?1}\sum _{1\le i_1<i_2<\dots <i_k\le 7}\left|A_{i_1}\cap A_{i_2}\cap \dots \cap A_{i_k}\right|\\ & =\sum _{k=1}^7(?1{)}^{k?1}\sum _{1\le i_1<i_2<\dots <i_k\le 7}(8?k)!\\ & =\sum _{k=1}^7(?1{)}^{k?1}?C_7^k?(8?k)\\ & =\sum _{k=1}^7(?1{)}^{k?1}?(8?k)?\frac{7!}{k!}\\ & =7?5040?6?2520+5?840?4?210+3?42?2?7+1?1\\ & =23633\end{array}$$

Step 4：求合法排列數

總排列數$8!=40320$，減去違規數：
$$\text{合法排列數}=40320?23633=16687．$$

---

🎯 總結：解題套路三連

1. 逆向思維：復雜限制→求補集．
2. 容斥原理：處理多條件交集，"奇加偶減"防漏算．
3. 捆綁法：連續數字視為整體，降維打擊．

適用題型：禁止特定子串的排列、錯位問題、概率中的互斥事件．

---

🍰 課后彩蛋

延伸問題：若額外禁止$21,32,\dots ,87$（即所有相鄰差值為±1），答案是多少？

互動提問：如果數字$1$到$8$排成一個環，且禁止連續數對，又該怎么算？

評論區留下你的思路！