點算的奧秘:含不動點或繼續點的排列問題


《點算的奧秘:廣義容斥原理》中,筆者推導了「廣義容斥原理」的公 式。在本節中,筆者將把這些公式應用於兩類特殊的排列問題。這些排列問題可以視為具有某些特殊限制的排 列問題,這些特殊限制有兩種:分別為「不動點」和「繼續點」。

首先我們須假設被排列的元素有一個既定的排序,各元素有一個既定的位置,例如數字、26個英文字母等就屬 於這類元素。所謂「不動點」(Fixed Point),是指在排列過程前後其位置不變的元素。舉例說,如 果對英文字母A、B、C、D排序,那麼以C為「不動點」的排列便包括以下6個:A-B-C-D;A-D-C-B;B-A-C-D; B-D-C-A;D-A-C-B;D-B-C-A。「不動點」的數目可以不只一個,例如在上例中若同時以A和C為「不動點」,所 得排列便只有以下兩個:A-B-C-D和A-D-C-B。

顯而易見,如果「不動點」是指定的元素,那麼這些「不動點」的存在實際已確定了某些元素的位置。例如對 於上面第一個例子,由於C是「不動點」,它必然處於第3個位置,因此我們只需考慮其餘3個字母的排列,而根 據「全排列」公式,應共有3! = 6種排列。一般地,如對n個元素排序,並且指定其中s個(0 ≤ s ≤ n)元 素為「不動點」,那麼所得排列的總數為

(n − s)!    (1)

在某些應用中,我們要求含有任意s個「不動點」(而非s個指定的「不動點」)的排列總數。現 在我們把這個數稱為F(n, s),以下筆者運用「廣義容斥原理」推導F(n, s)的計算公式。

設我們的論域是對n個元素進行全排列的各種排法組成的集合,Si為對n個元素排序並以第i個元素 為「不動點」的排列總數(1 ≤ i ≤ n)(註1),那麼F(n, s)就是屬於S1 ... Sn 中剛好s個集合的那些元素的個數。套用《點算的奧秘:廣義容斥原理》中 的定義,這個數就是N(n, s),即F(n, s) = N(n, s)。由於S1 ... Sn顯然是「可交換 集合」,我們可以運用上述網頁的公式(4)求解(以下重新編號為公式(2)):

N(n, s) = C(n, s) Σ0 ≤ r ≤ n−s(−1)r C(n − s, r) nr+s    (2)

為了應用公式(2),我們須先求nk的值,這個值就是從S1 ... Sn中抽k個 出來構成的交集的元素個數。由於S1 ... Sn是「可交換集合」,對於任何k個集合構 成的交集,其元素個數都是一樣的,因此我們可以把這k個集合當作指定的集合,而這k個集合構成的交集的元 素就是含有k個指定的「不動點」的排列。套用上面公式(1),得nk = (n − k)!,由此亦得 nr+s = (n − r − s)!。把此一結果代入公式(2),便得

F(n, s) = C(n, s) Σ0 ≤ r ≤ n−s(−1)r C(n − s, r) (n − r − s)!    (3)

為化簡上式,我們首先把C(n, s)放入Σ符號右面,然後展開以下乘積:

 C(n, s) × C(n − s, r) × (n − r − s)!
 n! (n − s)!   
=-----------------× ----------------------×(n − r − s)!
 (n − s)! × s! (n − s − r)! × r!  
 n!
=--------------
 s! × r!

由於n和s不等於式(3)中的求和符號r,我們可以把以上結果中的n! / s!抽回到Σ符號的左邊。這樣式(3) 便最終變成

F(n, s) = (n! / s!) Σ0 ≤ r ≤ n−s(−1)r / r!     (4)

上式就是「含不動點的排列」問題的公式。

當s = 0時,F(n, 0)代表「不含任何不動點的排列」總數,在這樣的排列中沒有一個元素被安於原位。在「點 算組合學」上,這樣的排列稱為「亂序」(Derangement)。容易看到,只要把s = 0代入上面公式(4), 便可得到「亂序」的計算公式:

F(n, 0) = n! Σ0 ≤ r ≤ n(−1)r / r!    (5)

例題1:有5個人參加交換禮物遊戲。他們首先交出自己帶來的禮物,然後把自己的名字寫在紙條上並 投入一盒子中。接著每個人從盒子中抽一張紙條出來,並取得擁有紙條上所示名字的那個人的禮物(請注意,被 抽出的紙條不會再放回盒子)。問有多少種抽法可令每個人都不會取回自己帶來的禮物?

答1:我們可以假定這5個人的名字有一種既定的排序方式,例如按他們名字的筆劃序或字母順序排列 。那麼從盒子中逐一抽這5個人的名字出來便等於把這5個名字重新排序,而本題的「不動點」就相當於剛好抽 中自己名字並因而取回自己禮物的人。因此本題要求的答案就是F(5, 0)。把n = 5代入上面公式(5),便求得答 案為

F(5, 0)= 5! Σ0 ≤ r ≤ 5(−1)r / r!
 = 120 × (1/1 − 1/1 + 1/2 − 1/6 + 1/24 − 1/120)
 = 44 □

以上筆者介紹了「不動點」,接下來筆者將介紹「繼續點」。設我們把n個有既定順序的元素重新排序後,在新 序列中,第i個元素(1 ≤ i ≤ n − 1)與第i + 1個元素剛好是在既定順序上前後相繼的一對元素, 我們便稱這第i個元素為「繼續點」(Sucession)。舉例說,如果對英文字母A、B、C、D排序,那麼新 序列D-B-C-A含有1個「繼續點」(即B),而新序列A-B-C-D則含有3個「繼續點」(即A、B和C)。

顯而易見,如果「繼續點」是指定的元素,那麼這些「繼續點」的存在實際是把「繼續點」與在既定順序中緊 接其後的那個元素「黏」在一起。在進行排序時,這對元素被當作一個「單位」參加排序。舉例說,如果對英 文字母A、B、C、D排序,並指定B為「繼續點」,那麼由於B後面必須是C,B與C構成一個「單位」B-C,因此實 際參與排序的不是4個元素,而是A、B-C和D這3個「單位」,而所得排列應有3! = 6個,即A-B-C-D;A-D-B-C; B-C-A-D;B-C-D-A;D-A-B-C;D-B-C-A。

當「繼續點」不只一個時,情況便較為複雜,以下我們首先考慮一個具體例子,然後嘗試總結出一般規律。

例題2:假設我們對A、B ... L這12個字母排序,並指定A、B、C、F、G、I、K這7個字母為「繼續點」 。問有多少種不同排法?

答2:我們可以把這7個「繼續點」分為兩類,其中A、B、C和F、G構成一類,它們是兩組連續的字母 ,而I、K則構成另一類,它們是單個不連續的字母。對於A、B、C和F、G而言,它們本身已「黏」在一起,此外 再加上緊接C之後的D和緊接G之後的H,分別組成兩個單位:A-B-C-D和F-G-H參加排序。對於I和K而言,它們各 自與緊接其後的字母J和L「黏」在一起組成兩個單位:I-J和K-L參加排序。此外,還剩下字母E,它不與任何字 母「黏」在一起,自成一個單位。因此在這個排序中,共有5個單位:A-B-C-D、E、F-G-H、I-J和K-L參加排序 ,故應有5! = 120種不同排法。□

接著我們把上題的推理推廣至一般情況。假設我們對n個元素排序,並指定其中s個為「繼續點」。我們可以把 這s個「繼續點」分為兩類:連續的元素和單個不連續的元素。我們並假設第一類「繼續點」可分為p組,第一 組共有r1個連續元素、第二組共有r2個連續元素 ... 第p組共有rp個連續 元素;而第二類「繼續點」則共有q個,並且r1 + r2 + ... rp + q = s 。

對於第一類p組「繼續點」而言,各組內的元素本身已「黏」在一起,此外再加上緊接各組最後一個元素之後的 元素,分別組成p個單位參加排序。這p個單位合共含有r1 + r2 + ... rp + p個元素。對於第二類q個不連續的「繼續點」而言,它們各自與緊接其後的元素「黏」在一起組成q個單位參 加排序。這q個單位合共含有2q個元素。此外,還剩下n − r1 − r2 − ... rp − p − 2q = n − s − p − q個元素,它們不與 任何元素「黏」在一起,各自構成一個單位。因此在這個排序中,共有p + q + n − s − p − q = n − s個單位參加排序,所得排列總數為

(n − s)!    (6)

在某些應用中,我們要求含有任意s個「繼續點」(而非s個指定的「繼續點」)的排列總數。我 們把這個數稱為S(n, s),以下筆者運用「廣義容斥原理」推導S(n, s)的計算公式。

設我們的論域是對n個元素進行全排列的各種排法組成的集合,Si為對n個元素排序並以第i個元素 為「繼續點」的排列總數(1 ≤ i ≤ n − 1),那麼S(n, s)就是屬於S1 ... Sn−1中剛好s個集合的那些元素的個數。套用《點算的奧秘 :廣義容斥原理》中的定義,這個數就是N(n − 1, s),即S(n, s) = N(n − 1, s)。由於 S1 ... Sn−1顯然是「可交換集合」,我們可以運用上面公式(2)求解。

為了應用公式(2),我們須先求nk的值,這個值就是從S1 ... Sn中抽k個 出來構成的交集的元素個數。由於S1 ... Sn是「可交換集合」,對於任何k個集合構 成的交集,其元素個數都是一樣的,因此我們可以把這k個集合當作指定的集合,而這k個集合構成的交集的元 素就是含有k個指定的「繼續點」的排列。套用上面公式(6),得nk = (n − k)!,由此亦得 nr+s = (n − r − s)!。把此一結果代入公式(2),便得

S(n, s) = C(n − 1, s) Σ0 ≤ r ≤ n−1−s (−1)r C(n − 1 − s, r) (n − r − s)!    (7)

為化簡上式,我們首先把C(n − 1, s)放入Σ符號右面,然後展開以下乘積:

 C(n − 1, s) × C(n − 1 − s, r) × (n − r − s)!
 (n − 1)! (n − 1 − s)!   
=--------------------× -------------------------× (n − r − s)!
 (n − 1 − s)! × s!  (n − 1 − s − r)! × r!  
 (n − 1)! × (n − r − s)
=----------------------------
 s! × r!

由於n和s不等於式(7)中的求和符號r,我們可以把以上結果中的(n − 1)! / s!抽回到Σ符號的左 邊。這樣式(7)便最終變成

S(n, s) = ((n − 1)! / s!) Σ0 ≤ r ≤ n−1−s (−1)r (n − r − s) / r!    (8)

上式就是「含繼續點的排列」問題的公式。當s = 0時,上式變為

S(n, 0) = (n − 1)! Σ0 ≤ r ≤ n−1(−1)r (n − r) / r!    (9)

上式就是「不含任何繼續點的排列」總數,在這樣的排列中沒有一個元素被安於原位。

例題3:5名學生每天按某一順序在操場上排隊。有一天,老師決定重新調配他們排隊的位置,使得在 新位置下,每名學生(除了原來站在最前的學生外)均發現站在他前面的學生與以前不同了。問老師有多少種重 新調配的選擇?

答3:我們可以把5名學生原來排隊的次序設定為1-2-3-4-5,重新調配位置就相當於把這5個數字重新 排序,而老師所希望的新排序方式是使得2不再緊接在1之後、3不再緊接在2之後、4不再緊接在3之後、5不再緊 接在4之後。換句話說,即新排序應不含任何「繼續點」。因此本題所求答案為S(5, 0)。應用公式(9),求得答 案為

S(5, 0)= 4! Σ0 ≤ r ≤ 4(−1)r (5 − r) / r!
 = 24 × (5/1 − 4/1 + 3/2 − 2/6 + 1/24)
 = 53 □


註1:請注意這裡所指的「第i個元素」是指按既定順序的第i個元素,而非經重新排列後的第i個元素。舉例說 ,如果我們是對A、B、C、D排序,那麼第3個元素就是指C;如果是對1、2、3、4排序,那麼第3個元素就是指3 。以下有關「繼續點」的定義,亦適用本註釋的規定。


返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898820" alt="setstats" border="0" width="1" height="1"></noscript><script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>