世紀之作:排列組合題型分類

來自專欄數學心得

排列組合一直是我心中的痛,一直沒能把他搞得很明白,我相信很多同學也有一樣的感覺吧.其實是很簡單的,當然你可能說難者不會,會者不難,我說很簡單當然是在我理清楚了前提下,同時,說他簡單是指他使用排列數公式還是組合數公式,真的只是一念之間,而這個一念之間如何判斷,其實只需要你自己模擬下每一輪怎麼取元素就行了,注意這裡每一輪是說每一種情況,排列也好,組合也罷.下面看排列和組合的定義:

排列數:在m個可分辨的元素中任意選取n個元素,並且把他們按順序擺放算作一輪,這時相同元素集合不同順序算作新的一輪排列,而把所有可能情況窮盡的個數叫做排列數,記作P(m,n).

組合數:在m個可分辨的元素中任意從中選取n個元素,並把他們任意擺放,只有在不等於之前任意一輪元素集體條件下,才算作一輪,第一輪不用考慮這個限制,而把所有可能情況窮盡的個數叫做組合數C(m,n).

注意上面兩個定義是我自己給出的,做了一點變化,一是可分辨,為什麼要加可分辨呢?因為排列是建立在可區分元素的基礎上,如果不可區分,如何算順序?所以排列一定是對可分辨物體中進行選取.再看組合,組合相對更複雜點,稍後再說.其實這裡我想說的是這個定義沒有完全把排列組合定義完整,因為還有其他不同的情況也可以用排列數公式或組合數,中學時大家不也是只學了一種排列或組合的定義么?然後發現在其他和定義不同條件下也可以直接用,WC,就不懂了,而且很多老師並沒有把不同場景下歸納出來,讓你感覺一片模糊,不知道到底用什麼公式,怎麼用,我這篇文章其實就是解決這個問題的.首先看題型一,我稱之為選取問題:

當m>=n時,在模為m的集合中選擇n個元素,那麼他們的排列數就是P(m,n);

m至少要等於n,不然一輪元素不夠選不完.

同樣,如果不考慮他們的順序,那麼組合數就是C(m,n),是因為每P(n,n)種情況對於排列數來說映射為一種情況,因為不可以重複,那麼組合數就等於P(m,n)/P(n,n).

我相信這類問題同學們都沒問題,因為根本就是按定義來的嘛,但下面的,也許你就不太明白了,我稱之為填坑問題:

在m個坑中每次填n個元素,n個元素是任意能區分的,在考慮元素順序情況下(就是12和21不同),那麼有多少種可能,答案就是P(m,n),同樣m>=n.

如果不考慮他們的順序(12和21算一種,123和321等等都算一種),那麼他們的組合數就是C(m,n).

我想這裡容易有個疑問,在選取問題時直接運用公式能看懂,但為什麼填坑時也可以直接套用呢?我相信把這個疑問搞明白了,後面的就輕鬆了,方法都是一樣的,就是自己構造一輪看看,看圖:

假如你需要在三個坑中使用12填滿,不同順序算一種(12和21各算一種情況,其他依此類推),不同位置同樣也算一種(ab和ac各算一樣,其他依此類推),總情形數為什麼還是P(3,2)呢?

這裡需要鋪墊兩個東西:

1. 乘法的意義,一個乘數可以看成是"份數",另一個則是"單位數",具體哪個是哪個看情況;
2. 再講下樹這個數據結構,樹是由節點和線段組成的,我們這裡只考慮倒掛的樹,自上而下的,最開始的叫做根節點,我稱之為0層,然後是1層2層這樣,下層節點數一定大於等於上層節點,因為對於每個節點而言,只有1對1或1對多自上而下的映射,那麼自然1<=1或者多,然後兩邊同時乘以一個正整數表示上層的節點數n,自然n<=n或者np,p也是正整數,所以我們就證明了下層節點數一定大於或等於上層節點數.再講一個節點的屬性,我稱之為分支數,除了最低層的全部節點即葉子節點為0外其他節點的分支數都不為0.

開始構造第一輪,這裡有個問題,非常關鍵,我希望大家可以拿筆畫一畫,因為你需要明確,到底是排字母,還是排數字?思考兩分鐘回來

.

.

.

.

.

.

如果是排數字,只有1和2兩種,那麼3個坑你卻只有2個符號去表示,比如a和b坑占以及a和c坑占並且都是1先佔左邊那麼兩種情況表示都是12,根本沒法區分,所以只能是排字母了.其實從另一個角度來講,當坑比物體數多時,你沒法用物體編號表示所有的坑,因為一個編號只能代表一個坑,而在同一個上下文環境中,上一個數字已經表示坑了,那麼就不能再用它來表示坑了,所以必然會有坑無數字可用,那麼也就談上不用數字表示所有情形了,對了,這裡我希望大家分清編號也就是下標或者說是索引和表示數量的數字的含義,比如此例中的1代表下標1,即使用1這個數字去和某個物體進行一一映射以此來代替這個物體,方便指認;而如果是數量的話,同樣用數字2表示,因為只有兩個物體,但這個2表達的含義卻是數目,不是下標,所以我希望大家把這兩個概念區分清楚.

所以我們只能排字母,那麼思考下每輪是怎樣構造成一種滿足題目要求的情況的,這又是一次"整體"的分步動作,因為你需要完成兩個物體的擺放,也就是兩步,第一步是選擇1號的坑,你有三個選擇abc,如果選擇了a,那麼你將剩下bc來放2號,如果....依此類推,下面用圖來表示就是:

0層到2層從左及右的順序,0層的節點數為3,1層的節點數為6,但每個1層元素的節點數為2,也就是1層每個元素的分支數都是2,那麼葉子節點數為6,從上到下就可以數出來,而6就是我們這題的答案,但重點是怎樣得到6?我們先不直接用公式,因為沒弄懂套公式也是白用.

我們觀察到,根節點的分支數是3,即一開始我們有三個坑可以讓你選擇,1層節點的分支數為2,即對應於每個節點,你又有2個坑讓你再次選擇,最終填滿任意兩個坑就算一輪完成了,我們發現,期間不重不漏,邏輯是完整有效的.好像2乘以3得到了答案,回到上面我們講的乘法的意義,如果這裡把0層分支數3看成是乘法意義中的份數的話,那麼每一份中又有2種選擇,即2就是當前這個環境中的單位數,即每一份中又包含了幾個元素,那麼總元素根據乘法,就是份數乘以單位數,這裡就是總共有三堆元素,每一堆中又都有兩個元素,那麼總共就是3*2=6個元素,然後我們再次觀察2層元素,我們可以看成是從2層元素中每兩個元素映射了一個1層元素,這樣可以形成一個二對一的映射,也就是說2層可以看成有六個元素的集合A,1層可以看成是有三個元素的集合B,那麼從B到A形成了一個二對一的滿射,但不是單射.我們如果把每一對映射列舉出來,我們就可以得到ab,ac,ba,bc,ca,cb就是全部三個坑中使用兩個元素填有序排列的排列數,但是這裡蘊含了一個做法,什麼做法呢,就是我默認是第一次一定是把1號放入一個坑,然後再次放入2號的,也就是說這個兩位字母串左邊代表1號的位置,右邊代表2號的位置,我們再次檢驗下有沒有窮盡所有情況,題目要求是不同的順序算做一種,不同的位置也算做一種,我們看ab和ba,分別表示1號佔a坑同時2號佔b坑和1號佔b坑同時2號佔a坑,那麼這樣就滿足了相同的位置但順序不同的窮盡;再看ab和ac,是不是就是1號佔a坑同時2號佔b坑和1號佔a坑同時2號佔c坑,這又滿足了元素順序相同但是位置不同算一種情況的要求,剩下幾種也可以觀察得出滿足這兩個要求的.所以是正確的排列方法.

總結這種填坑問題,它實際上是把用物體填坑換成了在物體占坑順序一定的情況下(比如先1再2),排列坑號的問題,即在總共有m個坑號時,每次排列n個坑號的排列數是多少的問題,而不是表面上說的有m個坑,使用n個物體填滿有多少種不同的填滿方法,表面上是在問物體有多少填法,實際上是指坑號有多少種選取方法,即把這個填坑問題轉化為了選取問題,自然直接用排列數公式的定義就可以直接算出了.因為這裡面一定要控制變數,就是說只有在一種變數一定的情況,另一種發生變化的排列數是多少,比如這個就是在每次編號了的物體占坑的順序全程一致的情況下對坑號進行變化而形成不同的排列數的問題.如果兩個變數都可以變,那麼會發生什麼?比如說我剛開始使用1號物體佔了a坑,2號物體佔了b坑,下次卻從2號物體開始,這時因為上次是從a坑開始的,那麼這次我從b坑開始,即2號佔b坑,1號佔a坑,你會發現,兩種情況就重複,所以我們可以得出一個結論,只有在一種變數不變的情況下,控制另一種變數變化,才能保證不重,如果不這樣,那麼我們總數就需要除以2了,但沒必要這樣做,所以我們控制變數,只讓一個參數發生變化而保持另一個不變.

理清了排列,再討論組合,如果這個問題這樣問,有m個坑,每輪填滿n個物體算一輪,如果把每輪的全部坑號元素組成的集體看成是一個集合,那麼新的一輪的集合只有不等於之前輪集合的情況才算做新的一輪,就是說你必須變換坑號組合,那麼總共有多少種情形呢?

實際你把坑位數對應為集合模數,那麼上面問題就相當於問大小為m的集合A有多少個大小為n的子集?那麼自然就使用C(m,n)就得到了.推理過程就是先使用排列數公式,第一步有多少種選擇,第二步有多少種,一直到第n步,然後再除以P(n,n),即在n個元素中排列n個元素有多少種排列法,我第一輪可以選擇n個,第二輪可以選擇n-1個,一直到最後一輪只剩下一種選擇了,那麼除完後得到的結果就是組合數.

好了,我相信分清這兩類問題,你思路應該比之前更清晰了,真正完全掌握排列數與組合數公式的運用,還需要大量練習,而這個,任何人都不能代替你.

最後給大家支個招,一般來講,如果你計算結果比答案的大了,那麼說明你計數重了;如果你結果比答案小了,說明你漏了,那麼循著這條原則,你一定可以找到是哪裡出問題了,因為邏輯要麼重了,要麼漏了,又重又漏的你可以重學一遍了.

另外,在每一輪排列中,你經常會遇到分類步驟的情況,就是說他們幾類計算方法不同,需要順序完成,所以分別思考不同的順序並找到一個最好的順序,一般不太麻煩.

我們還可以得出一個結論,在排列組合問題中,一定有一個順序是不變的,具體是物體呢還是坑呢,根據實際情況考慮,因為如果兩個變數都變的話就會有重複的發生.