近日我在俗稱清交二手格鬥場上看到了一個有趣的數學問題：UberEat 送禮功能的組合數問題
(註: 會稱做格鬥場的原因是，上面常常會公審文，引起各方人馬在上面批鬥，實屬有趣)
那這個問題滿生活化的，由於現在疫情十分嚴重加上所有便當店餐廳都僅能提供外食，因此大部分的學生都懶得出門因此依賴UberEat等外送服務。有趣的是，UberEat還有一個叫做送禮的服務，就是可以指定好餐點送給別人，讓對方去取餐類似這樣的概念。那現在有趣的問題是說，如果有一群人好了，在大家完全沒有約定的狀況下，隨機送禮給別人，那最後大家都剛好有飯吃的機率為何呢? 也就是說每個人都剛好收到餐點的機率有是多少呢?
簡單舉4個人來說好了，如果有4個人(A~D)，在每個人要送禮給別人條件下，若是第一種組合澤剛好大家都有東西吃，反之若是第二種組合，B會收到兩份餐點，而A就變成沒飯吃的狀況。
在了解這樣的狀況以後，我們回到清交版上的問題，若是有6個朋友，大家互相送禮，為了避免兩個朋友私下約定互送(A送B，B回送A)而降低遊戲趣味性，同時又要每個人都收到餐點，請問總共有幾種送禮的排序呢?
那這個問題我起初的想法是這樣：
這個問題其實就是高中的信封放錯問題或是舞會換妻問題，也就是所謂的錯排列問題，最典型的說法是這樣：假設有五封信件分別要給ABCDE，請問這個郵差同時給錯人的機率為何? 或是在一個舞會有五對夫妻參加，那在跳舞的同時交換舞伴的同時，所有夫妻不能同時配對的組合數又為何?
那這個解法高中通常用的就是排容原理的做法，若是用文式圖的概念來說明就是將所有的隨機排列數n!扣掉有一個人重複的狀況加上兩個人重複的狀況在減掉三個人重複的狀況以此類推
那高中通常處理的最多就四個人頂多就五個人，因為再多就有點難算了，那其實這個錯排的組合數(Derangement)有一個有趣的公式可以由遞迴公式得到(之後有空再證明)
也就是說如果是6人，就是計算D6
因此我們得到6個人的錯排列數量為265組，然而這個看是美好的答案卻多計算了互相贈送的狀況了(舉例來說以下的狀況就有E與C互送的狀況)
那我一開始的想法就是想說，竟然我已經算出所有錯排列的狀況了，我再慢慢一組組扣掉互送的情形，因此首先就先計算有一組人互送以及有三組互送(不會有兩組互送，讀者想一下就知道啦)
那一組人互送就是先選出兩個人互送，剩下的四個人錯排。那因為四個人錯排之中又有可能會有兩個人互送，所以要再扣掉兩個人互送的情形，因此又要從四個人之中分兩組。因此只有一組人錯排的組合就是
最後在計算三組人都互送的組合數
因此我們滿足題目要求，所有人既不能送給自己又不能和對方互送且所有人都能拿到餐點的狀況的所有組合數就是
總共有160 組
那算到這裡你以為就結束了嗎，因為這個方法太麻煩了而且很容易漏算，所以我把這個問題轉成Graph(圖表)來理解，問題就可以簡化了。所以我就把送禮的過程想成一個連鎖鍊，第一個人送給第二個人，第二個人要選擇送給下一個人，同時箭頭無法返回，一個個接下去到最後一個人再回送給第一個人。那這樣的結果就剛好可以解決兩人互送的問題了！
那其實這個就是在Graph theory當中的Number of route，從A開始，有五種選擇的路徑，連到B以後，B扣掉A以後還有四種選擇，連到D以後剩下CFE因此剩三種選擇…以此類推可以得到(A→B→D→F→E→C→A)，那你很快就會發現所有的組合數就是
同時整個路徑也可以反過來(A←B←D←F←E←C←A)，因此種共會有2 x 5! = 120種
那有趣的是，在這系統當中送禮的迴圈也有可能形成小迴圈，也就是三個人小團體互送的情形
那在把這樣的條件也考慮進去，就是先分堆兩組各三人，然後兩個迴圈可以互向順或是逆，因此組合數即為
因此我們透過Graph的方式所得到的答案就是
會發現這樣的結果跟剛剛用錯排的解法一樣，但是簡單好算許多。
那最後呢，因為這個問題沒有詳解，為了確定答案是不是正確的，我們就簡單寫個程式讓他暴力解看總共會有幾組組合數會符合我們的條件吧，那我簡單用matlab設定了條件和迴圈得到的結果也是160，可見這個問題的答案我們也可以蓋棺論定了。(機率就是=160/5⁶=1%的機率會剛好大家都有餐點而且沒有人互送)
結語
這個問題既生活化又有趣，同時又是高中的排列組合問題，高中畢業那麼久以後，還是覺得排列組合是個既困難又有挑戰性的問題呢！不過這次的問題又更加的困難了，但又可以有兩種完全不同的解法，十分的有趣味。希望讀者們可以用不同的思考方式，享受這道有趣的生活問題
後記
後來有人跟我說，幹嘛算那麼久，反正不管怎麼樣一定會有損友只送餐給自己然後就會有人沒東西吃啦，什麼1趴都是騙人的，機率是0啦!
我：幹好像也是! 不跟你們玩了!!