黑板上排列組合,你捨得解開嗎?

我們想讓你知道的是
《那些年,我們一起追的女孩》其中一幕是男女主角一起計算黑板上的排列組合問題,它們牽涉到一些香港中學課程中沒有明確教授的概念。
電影《那些年,我們一起追的女孩》曾經在亞洲地區瘋靡一時。在電影中,男主角柯景騰與女主角沈佳宜因數學問題而建立起感情,柯景騰更因此而覺得努力讀書變成了一件很熱血的事。
電影中有一幕是柯景騰與沈佳宜一起計算黑板上的排列組合問題。其實黑板上的幾條問題都非常有趣,它們牽涉到一些香港中學課程中沒有明確教授的概念,所以如果《那些年》的故事在香港上演的話,柯景騰與沈佳宜就未必解得開黑板上的問題了。
三條問題分別是:
- 用六種不同顏色塗一正方體,每一面一色,且每面顏色不同,會有多少種塗法?
- 八個人買六種飲料,每人要一種,問一共有幾種買法?
- 將五粒不同顏色的珠子串成手鐲,共有幾種串法?
1. 正方體塗顏色題
驟眼看來,第一題問題是把6種顏色分別塗上6個不同表面,那麼方法自然是6!。但細心想一下,這個正方體是可以移動的,我們把同一個正方體用不同的擺放,就可以看到不同的顏色排列,但其實它們都是由同一個顏色排列方式的立方體得出的,我們不應把它們數作不同的排列。
就如下圖,扭計骰雖然用了不同的方式擺放,但其實只是同一顆扭計骰,它顏色的排列並沒有改變過︰

懂得玩扭計骰(魔術方塊)的朋友必定知道,玩扭計骰的第一步就是扭好最底的一層。我們也可以把這技巧應用到這題排列組合問題中。我們先為正方體最底層塗上一種顏色,然後固定著它不要移動。那麼最頂的一層共有5種顏色選擇。之後把4種顏色放在剩下的4面,理應是4!個方式。
但值得留意的是,儘管我們把底部的顏色固定了,正方體還是可以如下圖般順時針逆時針轉動,做出4個不同擺放方法,所以答案應該再除以4︰

最後答案就是5x4!/4=30,跟沈佳宜的答案一樣。
2. 買飲料題
第二題就比較簡單直接,但牽涉到一個香港DSE課程沒有明確教授的方法——nHr,其實即是(n+r-1)C(n-1)。。
如果我們要從n件不同的可重覆使用的物件中抽出r件物件,那麼組合數目就是nHr了。如果覺得以上定義太過複雜難明的話,我們不妨換過另一個比較好理解的說明,設 x1 + x2 + x3 + ... + xn = r,其中 x1, x2, x3, ..., xn 都是非負整數,那麼解的數量就是nHr。
舉個例子,老師把10粒相同的糖果分給3位學生,有多少種分法?這個問題可以看成是求 x1 + x2 + x3 = 10 的非負整數解的數量,所以等如3H10 = (3+10-1)C(3-1) = 12C2 = 66。
至於《那些年》中的問題,就可以視作 x1 + x2 + x3 + … + x6 = 8 的非負整數解數量,即是︰6H8 = (6+8-1)C(6-1) = 13C5 = 1287。
至於為什麼從n件不同的可重覆使用的物件中抽出r件物件的組合數目是(n+r-1)C(n-1)呢?我們先從另一個角度思考題目,把題目理解成 x1 + x2 + x3 + ... + xn = r 的非負整數解,也就是把r種相同物件分成n組的方法,其中每一組的物件數量並沒有限制。試想想,如果我們要把把r種相同物件分成n組,我們可以把這r種物件排成一行,然後在中間加入n-1條分隔線。
例如下圖的顯示的,就是把9種相同物件分成3組的其中兩個例子,要把它們分成3組,就必須在它們中間加上2條分隔線︰

那麼組合的數量就相當於在n+r-1(編按︰即r個物件及n-1條分隔線佔據的位置總數)個位置中選擇n-1個位置放置分隔線,組合數目自然就是n+r-1Cn-1。
3. 珠子串成手鐲題
最後一題問題,驟眼看起來是把5種顏色分到5粒珠子上,那麼排列方法當然是5!。但正如剛才第一題題目,手鐲是可以如下圖般順時針或逆時針旋轉的。

為了解決這問題,我們可以先把其中一粒顏色的珠子位置固定,剩下4種顏色可以在4顆珠子中排列,排列的數目是4!。
但別忘記,手鐲除了可以順時針或逆時針旋轉,更可以把上下翻過來。為了避免重複計算,答案應該再除以2。答案是(5-1)!/2=12。

根據我們的分析,如果把n粒念珠(n>2)串成手鐲,串法排列的數量就是(n-1)!/2,這種排列的方法有個特別的名稱,叫「珠狀排列」。
排列組合的問題博大精深,更為柯景騰與沈佳宜青春時的曖昧,帶來了最美麗的回憶。難怪導演九把刀在經過這麼多年後,仍然對排列組合的問題念念不忘,更讓它們成為了電影中的重要元素。
本文獲授權轉載,原文見史丹福狂想曲。
相關文章︰
責任編輯:tnlhk
核稿編輯︰歐嘉俊
最新發展:
Tags:
2023迎向雲端浪潮,掌握職場躍進方程式,培養雲端硬實力就在此刻!

我們想讓你知道的是
未來,「雲端」將成為企業運作過程不可或缺的數位競爭力之一,而臺灣雲端服務商龍頭AWS即將於2月23日舉辦AWS線上雲端培訓日,免費傳授基本雲端概念技術,並幫助參與者認識雲端、學習AWS提供之上百種的免費雲端服務。
回首2022年來勢洶洶的數位轉型浪潮,數據運算、資料儲存、提升安全性等雲端技術早已成為企業製程最佳化、擴充業務規模、創造價值的重要利器,而在新的一年中,數據分析公司也指出,整合AI分析平台上雲不只能有效降低部署時間、減少人力成本,亦是在可見的未來中,提升商業價值、邁向永續轉型的科技大勢。因此,許多企業也延續轉型浪潮餘波,積極導入大數據、人工智慧(AI)、機器學習(ML)等進階數據科技,並搭配各式雲端服務來強化企業內部運轉效能,迎戰全新的市場挑戰。
數位革新不落人後,AWS助您入門雲端
當「雲端」從產業發展、轉型的熱門關鍵字轉變為2023年不分產業別,都有強烈需求的職場必備硬實力,每一位在產業中耕耘奮鬥的從業人員、或是初入社會職場的新鮮人,又該如何提升自我,加緊腳步跟上這一波未平一波又起的數位革新呢?
好消息是,臺灣雲端服務商龍頭Amazon Web Services(AWS)即將於2023年2月23日的下午2點至5點,舉辦AWS線上雲端培訓日(AWSome day),透過專為雲端新手設計的一系列實用入門課程,一步步帶領大家了解雲端技術以及AWS服務。
專業講師彙整雲端精華,基本服務、創新應用一次滿足
AWS線上雲端培訓日是針對雲端新手所量身打造的免費入門實用課程。課程內容由AWS的資深業務發展經理KC Liang,以及AWS技術培訓師Stanley Huang共同帶領,兩人將從雲端趨勢、技術概念、產業應用等角度逐一介紹,並透過深入淺出地介紹及示範儲存、資料庫管理、運算和網路、資訊安全等基本雲端概念技術以及AI機器學習、區塊鏈、5G及衛星通訊等熱門創新服務,讓您即刻上手AWS高達100多種的免費服務。

課程結束後,除了獲得AWS提供的培訓證書、養成雲端技術能力,亦能了解如何透過雲端服務掌握市場優勢,所以無論是對雲端服務感興趣的新鮮人、企業或資訊相關的高級主管,還是擁有豐富開發經驗的工程師或技術人員,AWS線上雲端培訓日都能為您建立雲端技術概念、拓展應用視野,為個人或公司帶來正面性的影響。
更棒的是,AWS線上雲端培訓日不只開放免費報名,凡完整參加並填寫會後問卷的參與者皆可參加抽獎,有機會將Air Pods(第三代)與AWS客製露營燈免費帶回家!此外,若您是新用戶,在活動前註冊AWS免費帳號並填寫贈品申請表單,還能直接獲得「AWS不鏽鋼智慧型保溫瓶」,歡迎點此了解更詳細活動規範。
