數學女孩秘密筆記：排列組合篇

本書重點 
日本数学会出版賞獲獎
前師大數學系主任——洪萬生◎審訂

排列組合有幾種呢?
排列、組合、環狀排列、念珠排列、
重複元素的排列、卡特蘭數、第2類Stirling數……
延續《數學女孩》作品，新系列《數學女孩祕密筆記》排列組合篇
徜徉多采多姿的排列組合世界，發現數學樂趣！


神啊～請賜給我萬能的數學解題法！
我只能用最普通的窮舉法，把解法全部列出來。
但是，圓桌座位的安排，不小心就會重複喔！
所以，排列組合，一起來作圖吧。

著名的美國數學教育家波利亞（G. Polya）
在《怎樣解題》一書中教我們：
●真的看懂題目嗎？
●能另外舉一個例子嗎？
●能作圖嗎？
●能列表整理嗎？
●知道未知物是什麼嗎？
●是否完整考慮所有情況？
●是否有類似問題？
●如果這樣會怎樣呢？
●反過來想會怎樣呢？
●如果數字太大，想一想，數字小會怎樣？
●想得極端一點會怎樣？
●重讀一次題目吧。

讓我們跟著書中的主人翁，
和米爾迦、蒂蒂、由梨，
把排列組合的圖畫出來，
列成一張表，
解題完成！

解題就像游泳一樣，
需要模仿與練習才能牢記。
——波利亞（G. Polya）

結城 浩
1963年生。日本数学会出版賞得主，2014日本数学会出版賞。執筆寫作有關程式語言、設計模式、密碼、數學等等領域的入門書。最新著作是「數學女孩系列」。是一個最喜歡巴哈的「賦格的藝術」作品的新教基督徒。出版有2011《數學女孩／費馬最後定理》，2012《數學女孩／哥德爾不完備定理》，2013《數學女孩／隨機演算法》、2014《數學女孩／伽羅瓦理論》（世茂出版）、2016—2017《數學女孩祕密筆記》系列。

譯者簡介
陳朕疆
自由譯者。清華大學生命科學系畢業，曾在京都大學交換留學一年。曾在中研院生醫所作過研究助理，目前在政治大學就讀財務管理研究所碩士班一年級。
在日本時有感於日本出版業的蓬勃，希望能夠把好書介紹給更多人認識，而有了成為譯者的想法，歡迎批評指教。譯有《世界第一簡單實驗設計》、《世界第一簡單護理統計學》。

審訂者簡介
洪萬生
美國紐約城市大學（CUNY）科學史博士，國立台灣師範大學數學系學士、碩士。國立台灣師範大學數學系教授兼主任（2007/8/1-2009/7/31）、台灣數學教育學會理事長（2007-2009）、國際科學史學院通訊會員、Historia Mathematica（國際數學史雜誌）編輯委員、《HPM通訊》發行人、台灣數學（虛擬）博物館創始人之一。

前言
序章
第1章 別責怪Lazy Susan
1.1 在頂樓
1.2 中華餐館問題
1.3 回到原來的問題
1.4 有沒有相似的東西呢
1.5 一般化
1.6 念珠問題
1.7 米爾迦
1.8 放學後，在圖書室
1.9 另一種想法
● 第1章的問題

第2章 好玩的組合
2.1 寫完作業之後
2.2 一般化
2.3 對稱性
2.4 觀察首項與末項
2.5 計算個數
2.6 帕斯卡三角形
2.7 找出公式
2.8 有幾條算式
● 第2章的問題
 
第3章 凡氏圖的變化
3.1 我的房間
3.2 集合
3.3 求數量
3.4 寫出數學式
3.5 文字與符號
● 第3章的問題

第4章 你會牽起誰的手？
4.1 在頂樓
4.2 再回到中華餐館問題
4.3 蒂蒂的思路
4.4 用較小的數字試試看
4.5 想想看數列的情形
4.6 算算看
4.7 整理式子
● 第4章的問題

第5章 繪製地圖
5.1 在頂樓
5.2 蒂蒂在意的事
5.3 波利亞的提問
5.4 找尋對應關係
5.5 有無「區別」
5.6 重複程度
5.7 換個說法
5.8 圖書室
● 第5章的問題
尾聲
 
解答
給想多思考一點的你
後記
索引

1.1 在頂樓
蒂蒂「學長！原來你在這裡啊！」
我「是蒂蒂啊。」

這裡是高中校舍的頂樓，正值午休時間。
在我啃著麵包的時候，學妹蒂蒂也到了頂樓。

蒂蒂「好舒服的風喔！可以和學長一起在這裡吃嗎？」
我「當然可以囉。你在找我嗎？」
蒂蒂「沒、沒有啦……不是特別來找學長，只是剛好經過這裡而已。」

蒂蒂邊說著，在我的旁邊坐下。
（不過，為什麼會剛好經過屋頂呢——）
我咬下一口麵包，開始思索這個問題。

我「你的午餐呢？」
蒂蒂「嗯，午餐已經吃過了。……對了，學長，人家最近一直在想一件事。」
我「什麼事呢？」
蒂蒂「這個嘛，『思考』這件事本身到底是怎麼一回事呢……」
我「這是個相當深奧的問題呢。」
蒂蒂「啊、不對，我不是這個意思！」

蒂蒂拼命揮動雙手否認。

蒂蒂「不是那種深奧的問題啦，我是指在解數學題目時的那種思考。」
我「能再說詳細一點嗎？」
蒂蒂「人家……人家自認在數學這科上下了不少工夫，但在解題的時候常會有種『怎麼沒想到要這麼做！』的感覺。」
我「是嗎？」
蒂蒂「人家一直想不通，要怎樣才能想到要解題方法。學長的話應該不會碰到這種情形吧？解數學題的時候，究竟該怎樣思考才對呢？」
我「不不不，蒂蒂，我也常有『怎麼沒想到要這麼做！』的感覺喔。」
蒂蒂「咦，學長也會有這種感覺嗎？」
我「是啊，當我碰上解不出來的題目，跑去翻解答後常會有兩種反應。一種是覺得『這種解法太厲害了』而深感佩服，另一種則是覺得『這種解法怎麼可能想得到啊！』而覺得莫名其妙。」
蒂蒂「原來是這樣啊。」
我「會覺得莫名其妙，多半是因為這類解法過於特殊——讓我不由得心想『這種解法根本沒辦法應用在別的題目上嘛！』，才覺得莫名其妙。」
蒂蒂「嗯，人家覺得自己應該還沒有達到那樣的境界，不過……學長，你有聽過這樣的問題嗎？」
我「什麼問題呢？」

1.2 中華餐館問題
蒂蒂「前陣子我在電視上看到一家中華餐廳店內的擺設。」
我「嗯。」
蒂蒂「其中一個圓桌上面有Lazy Susan……」
我「Lazy Susan是什麼啊？」
蒂蒂「就是圓桌上可以轉來轉去的旋轉台。」
我「哦……原來那個東西叫做Lazy Susan啊。」
蒂蒂「然後，客人們坐在圓桌的周圍。」
我「是啊，坐在周圍吃飯。」
蒂蒂「坐在圓桌旁客人可以和旁邊的客人彼此聊天，不過要是座位相隔遠一點的話，要交談不是很不方便嗎？」
我「沒錯。」
蒂蒂「如果想要和所有人都說到話，就要時不時的換座位才行囉。於是我就有了一個想法，拿剛才講的當例子，要是有5個人繞圓桌坐成一圈，共有幾種可能的入座方式呢？」

問題1（中華餐館問題）
有一個圓桌，周圍有5個座位。有5個人欲坐在這些座位上，共有幾種入座方式？

我「原來如此，這個問題啊……」
蒂蒂「學長！請等一下！」
我「咦？」
蒂蒂「學長！不要馬上告訴我答案啦。」
我「好好好，那麼蒂蒂又是怎麼想的呢？」
蒂蒂「把5個人拿來排排看，算算看總共有幾種可能的排列方式。」
我「哦哦——」
蒂蒂拿出了筆記。
蒂蒂「就像這樣，不過算到一半的時候開始有點混亂……」
我「我明白了。蒂蒂想用窮舉法，一一列舉出所有可能對吧。這也是許多可行方法之一啦。」
蒂蒂「是的。」
我「可是，你有按照一定的順序來計算有多少可能情形嗎？」
蒂蒂「有啊。我假設有A、B、C、D、E等5個人坐在圓桌旁，畫成圖後就像這樣。首先，讓A、B、C、D、E照著順時鐘方向入座（1）」
我「嗯，基本上沒錯。這個A和B之間的連線是什麼意思呢？」
蒂蒂「是的，這條線表示接下來要把這兩個人的座位對調。A和B之間的座位對調之後又是另一種入座方式對吧，這就是（2）。」
我「這樣啊……咦？」
蒂蒂「再來則是要考慮這兩個人不相鄰的情況，假設A和B之間夾了一個C，就是（3）的情形。」
我「嗯，是沒錯……」
蒂蒂「然後就像剛才一樣，把這兩個人座位交換，得到（4）的情形。」
我「蒂蒂……」
蒂蒂「接下來要考慮的是這兩個人之間夾了C和D的情形，也就是（5），然後一樣把這兩個人的座位交換得到（6）。」
我「蒂蒂，可是……」
蒂蒂「不過呢，當我想在A和B之間夾進C、D、E，也就是（7）的時候，發現了一件事。」
我「……」
蒂蒂「（7）的入座方式稍微轉個角度，就和（2）的入座方式一模一樣了！」
我「是啊。這種計算方式不太好，會重複計算喔。」
蒂蒂「沒錯，學長說的對，這種方式並不好。我原本以為只要讓夾在A和B之間的人逐漸增加，就可以列出所有可能的情形了。沒想到圓桌居然是個陷阱！一不小心，同樣的入座方式就會重複出現！」
我「正是如此。逐漸增加人數這個想法還不錯，但要是出現重複的情形就麻煩了。」
蒂蒂「於是我就被困在這裡了。碰到這種情形的時候，要怎麼思考才能找到解答呢？該怎麼做，才能確實解出數學題的答案呢？」
蒂蒂看向我，睜大了她的眼睛等著我的回答。
我「嗯……這麼說吧，蒂蒂，能解出所有的數學題目的萬能解題法，並不存在喔。」
蒂蒂「啊，這麼說——這麼說也是啦，不好意思。但這樣的話，不就要把各式各樣的解題方法都死背下來才行嗎？這樣當我們碰到各種不同的數學題目時，才有辦法解出答案。不過要把所有解題方式都背下來實在有點困難……」
我「嗯，相當困難喔。能解出所有數學題目的萬能解題法並不存在，當然，也不可能把所有數學題的解法都背下來。」
蒂蒂「沒錯，就是這個意思！不僅不存在萬能的工具，要把所有工具都收集齊全也很困難，那該怎麼辦才好呢？」
我「我說蒂蒂啊，這個想法會不會太極端了呢？你想到的解決方式過於兩極，實際的情形則常常介於兩者之間喔。」
蒂蒂「這是什麼意思呢？」
我「解數學問題的時候，通常不會只用到死背下來的解題方式。當然，還是會用到記憶中的解法，把自己以前所有解題經驗全都拿來試試看。但解題時，還是要詳讀題目，理解內容，整理解題條件——這樣才能逐漸推導出答案喔。」
蒂蒂「聽、聽起來好複雜……」
我「確實把某些解法死背下來也是個方法，不過要如何使用這些解法也很重要喔。在波利亞的『怎樣解題』*這本書中也提到許多解題方式。至於我自己的解題經驗嘛——也只是許多順利解出答案與被難題困住解不出來的經驗一一堆疊起來而已。真要說的話，我在解題的時候常常會這麼對自己《提問》。」

●仔細閱讀題目了嗎？
●能試著想一個例子嗎？《舉例說明可驗證自己是否理解》
●能試著作圖嗎？
●能整理成表格嗎？
●能為未知事物命名嗎？
●是否考慮到所有狀況？沒有遺漏？
●有沒有類似的問題？
●會不會覺得「如果是這樣就好了」？
●反過來想的話又會怎麼樣呢？
●如果數字太大的話，想想看數字小的情況會如何？
●想想看極端的情形會如何？
●再仔細閱讀一次題目

蒂蒂「原來如此……學長剛才所說的《提問》，雖然聽起來很抽象，但卻也很具體喔。和直接解出答案比起來，這些提問好像很抽象，但就對自己的要求而言，卻是很具體的提問。」
蒂蒂一邊點著頭一邊說著，很快便接受了我的說法。
我「沒錯！面對題目的時候，這樣的《提問》很有效喔。在想怎麼解題時，自問自答是很有用的方法。」
*波利亞『怎樣解題』
 

1.3 回到原來的問題
蒂蒂「那回到剛才的中華餐館旋轉台，學長會怎麼解這個問題呢？嗯……我想問的不是『答案本身』，而是想問學長該怎麼思考這題，或者說是解題時的思考方式。」

問題1（中華餐館問題）
有一個圓桌，周圍有5個座位。有5個人欲坐在這些座位上，共有幾種入座方式？

我「嗯，如果是我的話，大概會像蒂蒂一樣，先《以圖表示》，也就是畫出5個人坐在不同座位上的示意圖。接著為這5個人《命名》為A、B、C、D、E，這個部分也和蒂蒂做的一樣。」
蒂蒂「都和人家一樣……」
我「嗯，不過這5個人的排列順序可能會和蒂蒂不太一樣就是了。然後，當我寫出幾種入座方式時，應該會有和蒂蒂一樣的發現。」
蒂蒂「和我一樣的發現……」
我「沒錯，我也會想到要讓5人繞成一圈坐下，不過大概不會真的畫出可以旋轉的5個位子，而是想像另一種比較簡單的表現方式，並使其可以對應到這5個位子。因為可以旋轉的座位在計算的時候很容易搞混。」
蒂蒂「是的，我也覺得這樣不太好算。」
我「是啊，這時就會用到這個提問：『會不會覺得《如果是這樣就好了》？』」
蒂蒂「如果是這樣就好了……？」
我「沒錯，像我就會覺得《要是座位不能旋轉就好了》。」
蒂蒂「原來如此！……可是，實際上還是可以轉啊。」
我「為什麼我們會覺得座位旋轉不好呢？因為我們原先可能會以為某兩種入座方式是《不同情形》，但稍微轉一下後卻發現它們其實是《相同情形》，這樣就重複計算了。」
蒂蒂「是啊。」
我「《要是座位不能旋轉就好了》——所以我們要想辦法禁止它旋轉。要達到這個目的，只要固定其中1人的座位就行了！」
蒂蒂「啊！！」
我「若固定其中1人的初始座位，即使旋轉座位，這個人的座位一定會改變，入座方式一定與先前不同，所以不會重複計算。」
蒂蒂「也就是讓其中1人當《國王》囉！」
我「哈哈，這樣講也沒錯。把其中1人當作國王，固定他的座位，再來數數看有幾種入座方式。《如果是這樣就好了》，善用這個提問便能對解題大有助益。」
蒂蒂「原來如此。從《要是座位不能旋轉就好了》，進一步推論到《固定其中1人的座位就行了》……」
我「蒂蒂剛才的解法中，最上面的座位會變來變去的不是嗎？一下是A一下是B。」
蒂蒂「是的，因為我有時候會把A和B互相交換。」
我「別再用這個方法了。如果改成固定其中1人的話，入座情形的計算會簡單一些。」

1.4 有沒有相似的東西呢
蒂蒂「原來如此。」
我「接著，似乎也可以試著提問《有沒有相似的東西呢》？」
蒂蒂「相似的東西？」
我「我們剛才一直在思考這些人排成環狀時的樣子不是嗎？也就是在問，這些人排成環狀時有幾種可能的情形。」
蒂蒂「幾種可能……的確如此。」
我「雖然我們之前沒碰過排成環狀的問題，但我們應該有做過類似的題目吧。也就是排成一列時的情形！」
蒂蒂「……」
我「其實仔細想想，如果固定其中1人，並把其他人照順時鐘順序排下來，和一般的排列不是很相似嗎？」
蒂蒂「咦、咦……所以就是……一般的排列問題嗎？」
我「沒錯，我們可以把排成環狀的人們視為排成一列，就成了一般的排列問題。還記得排列問題吧？」
蒂蒂「請等一下，這樣不就表示《排成環狀》和《排成一列》一模一樣了嗎？」
我「不，不一樣喔。你想想看，因為我們先把其中1人固定下來了，所以這個問題中，我們實際可以改變位置的人數會少一人。」
蒂蒂「！！」
我「排成環狀的有5人，若我們固定A的座位，則剩下的4人就可以當作一般的排列。」
蒂蒂「原來如此！」
我「接著來想想看，固定A的座位後，剩下的座位該怎麼排吧，照順時鐘的順序一個一個看。先決定A的下一個座位是由其它4人中的哪一位入座，再決定再下一個座位是其它3人中的哪一位入座，再決定再下一個座位是其它2人中的哪一位入座，而最後一個座位便是最後一個人入座。」
蒂蒂「真的耶，真的耶，原來要這樣算！」
我「這樣就解出來囉。要計算5個人排成環狀共有幾種可能的排法，只要先固定其中一人，再將剩下的4人視為一般的排列，也就是計算排成一列的4人有幾種可能的排法就行了。因此答案就是4! = 4 × 3 × 2 × 1，答案是24種可能。」

解答1（中華餐館問題）
有一個圓桌，周圍有5個座位。若有5人欲坐在這些座位上，則可由下列計算過程
4! = 4 × 3 × 2 × 1 = 24
得到入座方式共有24種。
（固定其中1人，再將剩下的4人視為一般的排列）

蒂蒂「咦……學長，這24種排列方式是怎麼……」
我「啊，抱歉抱歉。用樹狀圖就能列出這些排列囉。」
蒂蒂「？」
我「就是這樣的圖，用4個樹狀圖就能列出所有可能了。」
蒂蒂「這樣啊……」 
我「若想要《沒有遺漏、沒有重複》，那麼樹狀圖是很好用的工具。」
蒂蒂「原來如此。」

1.5 一般化
我「接下來，蒂蒂，既然都做到這裡了，離一般化只差一點囉。」
蒂蒂「要怎麼做呢？」
我「只要求出『當n人排成環狀時，有幾種可能的排列方式』就行了。」
蒂蒂「n人……啊，這個簡單！用相同方式做就行了，先固定其中1人，再將剩下的n - 1人排成一列！」
我「正是如此。」
蒂蒂「所以總共有(n-1) × (n-2) × … × 2 × 1種排列方式！」
我「沒錯沒錯，共有(n-1)!種可能，這就是環狀排列時的排列數。」

環狀排列的排列數
當n人排成環狀時，共有
(n-1)! 種排列方式

蒂蒂「環狀排列……原來還有名字啊！」
我「是啊，其實我一開始就想說了，不過蒂蒂說得正起勁讓我不曉得該在什麼時候打斷。」
蒂蒂「啊……十分抱歉。」
我「要不要再研究一下這個環狀排列呢？」
蒂蒂「學長，請等一下。在進行下一步研究之前……」
我「咦？」
蒂蒂「人家想把學長剛才解說的環狀排列計算方式，整理成自己看得懂的筆記。」
我「好啊。」
蒂蒂「一次看到那麼多新東西，覺得需要一點時間整理消化……」
● 欲求出n人排成環狀時，有幾種可能（環狀排列的排列數）。
● 計算時，必須《沒有遺漏、沒有重複》。
● 排列成環狀的人們沿著環旋轉後，可能會得到曾出現過的排列。這樣就會重複計算。
● 為了不讓這些人旋轉，先固定其中1人，設其為《國王》。
● 這麼一來，剩下的n-1人便可視為排成一列，並由此計算可能的排列情形。（一般排列的排列數）。
我「整理的非常好。這就是將環狀排列回歸至一般排列的情形，再求出答案喔，蒂蒂。」
蒂蒂「回歸……？」
我「沒錯。我們原先並不知道《環狀排列之排列數的計算方式》，但只要固定其中1人，就能用我們已知的《一般排列之排列數的計算方式》來求解了。」
蒂蒂「真的耶。」
我「換句話說，我們可以將環狀排列這種《沒碰過的問題》，改為一般排列這種《已知解法的問題》，再求出解答。這個過程就是所謂的《將環狀排列回歸至一般排列》。」
蒂蒂「原來如此！」
我「如果想用這種方式解數學題，一定要先熟悉自己《已知解法的問題》才行喔。」
蒂蒂「也就是說，要熟悉自己的武器對吧！」
我「沒錯，就是這個意思。要先知道自己有哪些武器可以用，這樣的話，就算碰到一時間不曉得該怎麼解的題目，也大概知道該從何處下手囉。」
蒂蒂「是的！」
我「對了，蒂蒂。這麼一來，你又多了一項武器囉。」
蒂蒂「為什麼呢？」
我「就是環狀排列啦。剛才我們把環狀排列回歸至一般排列，並解出答案，因此環狀排列也成了蒂蒂的武器。之後碰到其他相關題目時，可以試著將其回歸至環狀排列，或許就能得到答案囉。」