我們都學習過排列與組合，今天我們來探討一下排列組合的基本運算性質。
從n個不同的元素中選取m個元素排成一列的方法數稱為排列數，用符號A(n,m)表示。
A(n,m)=n×(n-1)×…×(n-m+1)
從n個不同的元素中選取n個元素排成一列，也就是直接對這n個元素進行排序，稱為n個數的全排列，簡稱全排。全排數用符號A(n,n)表示。
A(n,n)=n×(n-1)×…×2×1
=1×2×…×(n-1)×n
A(n,n)的計算結果又稱為n的階乘，用符號n!表示。
A(n,n)=n!=1×2×…×(n-1)×n
對於階乘，很顯然有如下性質：
n!=1×2×…×(n-1)×n
=[1×2×…×(n-1)]×n
=(n-1)!×n
n!=(n-1)!×n
有了階乘的概念，我們很容易發現如下關係：
A(n,m)=n×(n-1)×…×(n-m+1)
={[n×(n-1)×…×(n-m+1)]×[(n-m)×(n-m-1)×…×2×1]}/[(n-m)×(n-m-1)×…×2×1]
=n!/(n-m)!
我們得出了排列數與階乘的關係：
A(n,m)=n!/(n-m)!
接下來我們繼續來討論組合數。
從n個不同的元素中選取m個元素組成一組的方法數稱為組合數，用符號C(n,m)表示。
組合數與排列數的區別在於，排列數選出的m個元素是有序的，而組合數選出的m個元素是無序的。所以我們在計算組合數時，首先計算排列數，再把選出的這m個元素的順序除掉，也就是用排列數除以m個數的全排數，那麼這m個元素就沒有順序了，從而求出組合數。
C(n,m)=A(n,m)/A(m,m)
=[n×(n-1)×…×(n-m+1)]/m!
A(n,m)=C(n,m)×A(m,m)
C(n,m)=A(n,m)/A(m,m)
=[n!/(n-m)!]/m!=n!/[m!(n-m)!]
C(n,m)=n!/[m!(n-m)!]
到這裡，我們就得出了排列數、組合數與階乘的關係式：
A(n,m)=n!/(n-m)!
C(n,m)=n!/[m!(n-m)!]
進一步，我們還可以得出組合數的一個很重要的公式。
從n個不同的元素中選取m個元素，則會剩下(n-m)個元素。很顯然，選出m個元素的方法數與選出(n-m)個元素的方法數是一一對應關係。也就是說，從n個不同的元素中選出m個元素的組合數與選出(n-m)個元素的組合數是相等的。
C(n,m)=C(n,n-m)
我們再用階乘的關係式證明一下這個結論：
C(n,m)=n!/[m!(n-m)!]
C(n,n-m)=n!/{(n-m)![n-(n-m)]!}
=n!/[(n-m)!m!]=C(n,m)
C(n,m)=C(n,n-m)
很明顯，從n個不同的元素中選取n個元素的方法數只有一種，那就是把這n個元素全部選出。所以：
C(n,n)=1
為了保證之前的公式對0同樣適用，我們規定：
C(n,0)=C(n,n-0)=C(n,n)=1
C(n,0)=1
這裡特別強調，C(n,0)並沒有實際意義，僅僅是為了滿足運算人為定義的結果。
類似地，我們還可以定義0!
C(n,m)=n!/[m!(n-m)!]
C(n,n)=n!/[n!(n-n)!]
=n!/(n!0!)=1/0!=1
0!=1
接下來，我們來證明組合數中一個非常重要的結論：
C(n,m)+C(n,m-1)=C(n+1,m)
證明：C(n,m)+C(n,m-1)
=n!/[m!(n-m)!]+n!/{(m-1)![n-(m-1)]!}
=[n!(n-m+1)]/[m!(n-m+1)!]+(n!m)/[m!(n-m+1)!]
=[n!(n-m+1)+(n!m)]/[m!(n-m+1)!]
=[n!(n+1)]/[m!(n-m+1)!]
=(n+1)!/[m!(n-m+1)!]
C(n+1,m)
=(n+1)!/[m!(n+1-m)!]
=(n+1)!/[m!(n-m+1)!]
C(n,m)+C(n,m-1)=C(n+1,m)
證畢！
對於這個公式，我們還可以這樣來理解。
從(n+1)個不同的元素中選取m個元素
共有C(n+1,m)種情況
對於這(n+1)個的元素中的某一個元素P，是否選取P分成兩種情況：
①不選P：除了元素P以外還有n個元素，需要從這n個元素中選取m個元素；
共有C(n,m)種情況
②選P：除了元素P以外還有n個元素，還需要從這n個元素中選取(m-1)個元素；
共有C(n,m-1)種情況
C(n,m)+C(n,m-1)=C(n+1,m)
這個公式和著名的楊輝三角還有著非常奇妙的聯繫，具體聯繫我們下次再講。
利用這個公式我們還可以得到一個有趣的結論。
首先從n個不同的元素中選取1個元素的方法數有n種，也就是說：
C(n,1)=n
1+2+3+…+n
=C(1,1)+C(2,1)+C(3,1)+…+C(n,1)
=C(2,2)+C(2,1)+C(3,1)+…+C(n,1)
=C(3,2)+C(3,1)+…+C(n,1)
=C(4,2)+…+C(n,1)
=C(n,2)+C(n,1)
=C(n+1,2)
=[n(n+1)]/2
1+2+3+…+n=[n(n+1)]/2
這不正是正整數前n項和的求和公式嗎？你有沒有被驚艷到，原來組合數還可以對等差數列求和進行如此風騷的操作。
最後我們來討論一下非常著名的二項式定理：
對於(a+b)^n
(a+b)^n=(a+b)×(a+b)×…×(a+b)
這裡一共有n個(a+b)相乘
展開式的第(r+1)項T(r+1)，就是從這n個(a+b)中選出r個(a+b)
這r個(a+b)分別取因數b，剩下(n-r)個(a+b)分別取因數a
T(r+1)=C(n,r)×a^(n-r)×b^r
(a+b)^n=Σ[C(n,r)×a^(n-r)×b^r]
r=0，1，2，…，n
接下來我們來討論這樣一個問題：
對於n道判斷對錯的判斷題，這n道題的答案共有多少種情況？
我們可以從兩個不同的角度來思考這個問題
角度一：這n道題的答案中有0道是對的，共有C(n,0)種情況；有1道是對的，共有C(n,1)種情況；有2道是對的，共有C(n,2)種情況；……；有n道是對的，共有C(n,n)種情況。
這n道題的答案共有
C(n,0)+C(n,1)+C(n,2)+…+C(n,n)
種情況
角度二：這n道題每道題的答案都有對和錯兩種不同的情況
這n道題的答案共有2^n種情況
結合這兩種不同的角度可得
C(n,0)+C(n,1)+…+C(n,n)=2^n
我們再用二項式定理推導一下這個結論：
2^n=(1+1)^n
=Σ[C(n,r)×1^(n-r)×1^r]
=Σ[C(n,r)]，r=0,1,2,…,n
=C(n,0)+C(n,1)+C(n,2)+…+C(n,n)
C(n,0)+C(n,1)+…+C(n,n)=2^n
類似地，我們還可以得到另一個有趣的結論：
0=0^n=(1-1)^n=[1+(-1)]^n
=Σ[C(n,r)×1^(n-r)×(-1)^r]
=Σ[C(n,r)×(-1)^r]，r=0,1,2,…,n
=C(n,0)-C(n,1)+C(n,2)-C(n,3)+…
C(n,0)+C(n,2)+..=C(n,1)+C(n,3)+..
好了，今天關於排列組合的知識點就講到這裡。在今天的內容中我們探討了排列、組合、階乘、二項式定理、等差數列求和、楊輝三角相互之間的聯繫。
我們今天推導出了很多關於排列組合的有趣結論，整體看來並不是很複雜，大家可以再自行推導一遍，加深對這些公式的理解。