混亂時鐘有多少種開局︱錯位排序

混亂時鐘是寡人原創的不等目弈棋,規則見這裏。它的開局要求每一個棋子都不能處於正位。

那麼問題來了,混亂時鐘到底有多少種開局?

這在數學上叫「錯位排序」,轉化成數學語言:

將1〜12這十二個數字排列,要求每個數字都不能處於正位,有多少種排列方式?

下面寡人的講解將可能是全網最容易理解的。如果你一直看不懂別人的講解,那你就來看我的吧!(說實話我至今都看不懂別人在講錯位排序時說的是甚麼……)

步驟

  1. 排列組合
  2. 容斥原理
  3. 總結規律

一,排列組合

要搞懂錯位排序,就首先要了解排列組合的基本知識。因為「錯位排序」也是一種排列。

可參見本網講解排列組合

二,容斥原理

假設在18個人中,衣服上面有黑色或紅色或藍色的人不是臥底。

則計算臥底數量的方法是:

  1. 所有的人數(18)
  2. 減去含有黑、紅、藍(-6-6-7)
  3. 加上同時含有黑紅、黑藍、紅藍(+3+4+3)
  4. 減去同時含有紅藍黄(-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。

Leave a Comment