每日一题[1979]塑料兄弟

${\rm Ayako}$, $\rm Billy$, $\rm Carlos$, $\rm Dahlia$, $\rm Ehuang$, $\rm Frank$ 六个人按顺序坐在一排六把椅子上看演出. 表演中场, 他们离开去买了一些零食, 回来时按如下规则入座: 离开相邻的两人重新落座后都不相邻. 那么重新落座的不同方法数为_______.

答案    $090$．

解析    记六个人分别为 $A,B,C,D,E,F$. 用 $(MN)$ 表示 $M,N$ 相邻, 考虑用容斥原理, 列举如下

$$\begin{array}{c|c|c}\hline \text{情形}&\text{方法数}&\text{符号}\\ \hline \text{全集}&6!=720&+\\ \hline (AB) + (BC) + (CD) + (DE) + (EF)&5\cdot(2\cdot 5!)=1200&-\\ \hline (AB)\cap(BC)+(AB)\cap(CD)+\cdots&4\cdot (2\cdot 4!)+6\cdot (2^2\cdot 4!)=768&+\\ \hline (AB)\cap(BC)\cap(CD)+(AB)\cap(BC)\cap(DE)+\cdots&3\cdot(2\cdot 3!)+6\cdot (2^2\cdot 3!)+2^3\cdot 3!=228&-\\ \hline (AB)\cap(BC)\cap(CD)\cap(DE)+\cdots&2\cdot (2\cdot 2!)+3\cdot (2^2\cdot 2!)=32&+\\ \hline (AB)\cap(BC)\cap(CD)\cap(DE)\cap(EF)&2&-\\ \hline \end{array}$$ 因此所求排法数为 $$720-1200+768-228+32-2=90.$$