混亂時鐘是寡人原創的不等目弈棋,規則見這裏。它的開局要求每一個棋子都不能處於正位。
那麼問題來了,混亂時鐘到底有多少種開局?
這在數學上叫「錯位排序」,轉化成數學語言:
將1〜12這十二個數字排列,要求每個數字都不能處於正位,有多少種排列方式?
下面寡人的講解將可能是全網最容易理解的。如果你一直看不懂別人的講解,那你就來看我的吧!(說實話我至今都看不懂別人在講錯位排序時說的是甚麼……)
步驟
- 排列組合
- 容斥原理
- 總結規律
一,排列組合
要搞懂錯位排序,就首先要了解排列組合的基本知識。因為「錯位排序」也是一種排列。
可參見本網講解排列組合。
二,容斥原理
假設在18個人中,衣服上面有黑色或紅色或藍色的人不是臥底。
則計算臥底數量的方法是:
- 所有的人數(18)
- 減去含有黑、紅、藍(-6-6-7)
- 加上同時含有黑紅、黑藍、紅藍(+3+4+3)
- 減去同時含有紅藍黄(-2)
總計全部人數,之後減去一些,減多了又加回來,加多了再減回去。最終結果是7,經目視答案正確。
這就是容斥原理,各位可以自行找些小紙片來做下實驗以加深理解。
三,規律總結
那麼「容斥原理」跟混亂時鐘的開局數量有何關係?
混亂時鐘的開局數量要這樣算:所有十二個數字的可能排列(12!),先減去至少有一個數字在正位的情況(-C_{12}^{1}\cdot 11!),之後要加上至少有兩個數字處於正位的情況(+C_{12}^{2}\cdot 10!)……最終加上十二個數字都處於正位的情況(+C_{12}^{12}\cdot 0!)。
則用數學公式總結為:
\sum_{k=0}^n(-1)^k C_n^k (n-k)!根據「組合」的定義,上式簡化為:
n!\sum_{k=0}^n\frac{(-1)^k}{k!}再由e^{x}的泰勒展開(將在下一頁講解),上式簡化為:
\big[n!/e\big][x]表示對x四捨五入取整。則將n=12代入上式,可得結果為176214841。