本日天氣：晴天
本日心情：心情不錯
我很喜歡排列組合，但是有一個一直都沒有學到概念，到了後來查資料才曉得，這種模式叫做【錯位】。
【班上共有5個小朋友，上課時間都沒有在自己的位子上，而是在別人的。】
【有四對夫妻，男女兩兩共舞，但是都不是和自己的配偶。】
這樣會有幾種可能？
這種問題就和雞兔同籠一樣匪夷所思，到底是怎樣可以錯到這麼誇張啊。
不過該解的題目還是要解就是了....
查資料應馬上就會找到，搞不好還有公式（還真的有）。但是我想先自己來。這種題目講就是數組單一配對組合，都沒有任何一組是配對的。所以我試著把一組到六組的組合情況都列出來，然後再來觀察它們之間的可能性。
一組組合，全對是1種，全錯是0種（不可能）
二組組合，全對是1種，一組對一組錯是0種（不可能），全錯是1種。
三組組合，全對是1種，兩組對一組錯是0種（不可能），一組對兩組錯是3種，全錯是2種。
到這邊我們已經可以看得出一點規則了，
全對就只有一種可能（廢話）
只錯一組0種，完全不可能。（都只剩一組了還配不對？）
只錯兩組的話，可以先決定對的組別有幾組組合，再乘上二組組合全錯有幾種（前面算過了，1種），也就是C(3,1) x 1 = 3。
至於全錯，就是把所有可能減掉之前的可能數，以三組組合為例，就是3! -1 - 0 - 3 = 2。
那我們就來用四組組合去做映證吧！
全對：就只有一種可能。
只錯一組：0種，完全不可能。
只錯兩組：對的組別C(4,2) ，再乘上二組組合全錯有1 種，也就是C(4,2) x 1 = 6。
只錯三組：對的組別C(4,1) ，再乘上三組組合全錯有2 種，也就是C(4,1) x 2 = 8。
至於全錯：就是把所有可能減掉之前的可能數，就是4! -1 - 0 - 6 - 8 = 9。
所以到這邊差不多就確認了。接著就可以來看看公式，上維基一查，原來真的有一個很漂亮的公式
Dn=(n-1)(Dn-1+Dn-2)
而且它有很完整的說明，清楚解釋這個公式導出的思維，就不在此細說，附上連結：
https://zh.wikipedia.org/wiki/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98
但有件事我其車很在意，就像明勳大哥有一次解題，之後也是找我問，因為數字之間好像有一些關係。雖然事後證明應該只是巧合，但對數字的感覺有時就是那麼奇怪....
D1 = 0，D2 = 1，D3=2，D4 = 9，D5 = 44，D6 = 265，D7 = 1854
(說明：Dn 代表n 種組合時的錯排數)
由小到大是理所當然的，組合越多當然錯排數越多。
但是這個遞增的模式讓我總覺得似乎有種規律，尤其那個44 就是讓我覺得不舒服，好像把它弄成45 就會感覺好一點。
維基再往下查，果然還有另一個公式！
Dn = nDn-1 +(-1)n
這個公式更加簡明清楚，當然要推導要更難，我是看不太懂維基的說明。
但我很開心自己還是對數字有一點點的敏銳度。
沒有留言:
張貼留言