緒論：加法原理、乘法原理

分類計(jì)數(shù)原理：做一件事，有n類辦法，在第1類辦法中有m1種不同的方法，在第2類辦法中有m2種不同的方法，…，在第n類辦法中有mn種不同的方法，那么完成這件事共有N=m1+m2+…+mn種不同的方法。

分步計(jì)數(shù)原理：完成一件事，需要分成n個(gè)步驟，做第1步有m1種不同的方法，做第2步有m2種不同的方法，…，做第n步有mn種不同的方法,那么完成這件事共有N=m1×m2×?×mn種不同的方法。

區(qū)別：分類計(jì)數(shù)原理是加法原理，不同的類加起來就是我要得到的總數(shù)；分步計(jì)數(shù)原理是乘法原理，是同一事件分成若干步驟，每個(gè)步驟的方法數(shù)相乘才是總數(shù)。

排列問題

排列數(shù)

從n個(gè)不同元素種取出m(m≤n)個(gè)元素的所有不同排列的個(gè)數(shù)，叫做從n個(gè)不同元素種取出m個(gè)元素的排列數(shù)，用符號Amn表示。

排列數(shù)公式

Amn=n(n?1)(n?2)?(n?m+1)=n!(n?m)!,n,m∈N?,并且m≤n
（規(guī)定0!=1）

推導(dǎo)：把n個(gè)不同的元素任選m個(gè)排序，按計(jì)數(shù)原理分步進(jìn)行：

取第一個(gè)：有n種取法；
取第二個(gè)：有(n?1)種取法；
取第三個(gè)：有(n?2)種取法；
……
取第m個(gè)：有(n?m+1)種取法；

根據(jù)分步乘法原理，得出上述公式。

排列數(shù)性質(zhì)

Amn=nAm?1n?1 可理解為“某特定位置”先安排，再安排其余位置。

Amn=mAm?1n?1+Amn?1 可理解為：含特定元素的排列有mAm?1n?1，不含特定元素的排列為Amn?1。

組合問題

組合數(shù)

從n個(gè)不同元素種取出m(m≤n)個(gè)元素的所有不同組合的個(gè)數(shù)，叫做從n個(gè)不同元素種取出m個(gè)元素的組合數(shù)，用符號Cmn表示。

組合數(shù)公式

Cmn=AmnAmm=n(n?1)(n?2)?(n?m+1)m!=n!m!(n?m)!,n,m∈N?,并且m≤n

C0n=Cnn=1

證明：利用排列和組合之間的關(guān)系以及排列的公式來推導(dǎo)證明。

將部分排列問題Amn分解為兩個(gè)步驟：?

第一步，就是從n個(gè)球中抽m個(gè)出來，先不排序，此即組合數(shù)問題Cmn；

第二步，則是把這m個(gè)被抽出來的球排序，即全排列Amm。

根據(jù)乘法原理，Amn=CmnAmm，那么
Cmn=AmnAmm=n(n?1)(n?2)?(n?m+1)m!=n!m!(n?m)!

組合數(shù)的性質(zhì)

Cmn=Cn?mn 可以理解為：將原本的每個(gè)組合都反轉(zhuǎn)，把原來沒選的選上，原來選了的去掉，這樣就變成從n個(gè)元素種取出n?m個(gè)元素，顯然方案數(shù)是相等的。

遞推公式Cmn=Cmn?1+Cm?1n?1 可理解為：含特定元素的組合有Cm?1n?1，不含特定元素的排列為Cmn?1。還不懂？看下面。

Example

從1，2，3，4，5（n=5）中取出2（m=2）個(gè)元素的組合（Cmn）：

12 13 14 15 23 24 25 34 35 45

顯然，這些組合中要么含有元素“1”，要么不含。

• 其中含有“1”的是：12 13 14 15

  把里面的“1”都挖掉：2 3 4 5

  而上面這個(gè)等價(jià)于從2，3，4，5（n?1）中取出1（m?1）個(gè)元素的組合。

• 其中不含“1”的是：23 24 25 34 35 45
  上面等價(jià)于從2，3，4，5（n?1）中取出2（m）個(gè)元素的組合。

而總方案數(shù)等于上面兩種情況方案數(shù)之和，即Cmn=Cmn?1+Cm?1n?1。

組合數(shù)求和公式

C0n+C1n+C2n+?+Cnn=2n

我們感性認(rèn)知一下，上面這個(gè)式子的左邊表示什么呢？

把從n個(gè)球中抽出0個(gè)球的組合數(shù)（值為1）、抽出1個(gè)球的組合數(shù)、抽出2個(gè)球的組合數(shù)、……、抽出n個(gè)球的組合數(shù)相加。

換句話說，就是從n個(gè)球中隨便抽出一些不定個(gè)數(shù)球，問一共有多少種組合。

對于第1個(gè)球，可以選，也可以不選，有2種情況。
對于第2個(gè)球，可以選，也可以不選，有2種情況。
對于任意一個(gè)球，可以選，也可以不選，有2種情況。

根據(jù)乘法原理，一共2×2×?×2?n個(gè)2相乘=2n種組合。

想要嚴(yán)謹(jǐn)?shù)淖C明？數(shù)學(xué)歸納法：

1. 當(dāng)m=1時(shí)，C01+C11=2=21成立。

2. 假設(shè)n=k(k∈N?)時(shí)等式成立，即
   k∑i=0Cik=2n
   成立，當(dāng)n=k+1時(shí)，
   C0k+1+C1k+1+C2k+1+?+Ckk+1+Ck+1k+1=C0k+1+(C0k+C1k)+(C1k+C2k)+?+(Ck?1k+Ckk)+Ck+1k+1=(C0k+C1k+C2k+?+Ckk)+(C0k+C1k+C2k+?+Ckk)=2×2k=2k+1
   等式也成立。

3. 由1、2得，等式對n∈N?都成立。

也可偷懶地用二項(xiàng)式定理證明（其實(shí)二項(xiàng)式定理也是用數(shù)學(xué)歸納法證明的）：

(a+b)n=n∑k=0Cknan?kbk
令a=b=1，就得到了
n∑i=0Cin=2n

類似的公式（由Cmn=Cn?mn推導(dǎo)）：

C0n+C2n+C4n+?=C1n+C3n+C5n+?=2n?1

楊輝三角

這個(gè)神奇的圖形和組合數(shù)、二項(xiàng)式定理密切相關(guān)。

楊輝三角可以幫助你更好地理解和記憶組合數(shù)的性質(zhì)：

1. 第n行的m個(gè)數(shù)可表示為 Cm?1n?1，即為從n?1個(gè)不同元素中取m?1個(gè)元素的組合數(shù)。

2. 第n行的數(shù)字有n項(xiàng)。

3. 每行數(shù)字左右對稱（第n行的第m個(gè)數(shù)和第n?m+1個(gè)數(shù)相等，Cmn=Cn?mn），由1開始逐漸變大。

4. 每個(gè)數(shù)等于它上方兩數(shù)之和（第n+1行的第i個(gè)數(shù)等于第n行的第i?1個(gè)數(shù)和第i個(gè)數(shù)之和，即Cin+1=Cin+Ci?1n）。

5. (a+b)n的展開式中的各項(xiàng)系數(shù)依次對應(yīng)楊輝三角的第n+1行中的每一項(xiàng)（二項(xiàng)式定理）。

以下來自維基百科（我只是隨便貼這）

二項(xiàng)式系數(shù)

二項(xiàng)式系數(shù)可排列成帕斯卡三角形。
在數(shù)學(xué)上，二項(xiàng)式系數(shù)是二項(xiàng)式定理中各項(xiàng)的系數(shù)。一般而言，二項(xiàng)式系數(shù)由兩個(gè)非負(fù)整數(shù)n和k為參數(shù)決定，寫作，定義為的多項(xiàng)式展開式中，項(xiàng)的系數(shù)，因此一定是非負(fù)整數(shù)。如果將二項(xiàng)式系數(shù)寫成一行，再依照順序由上往下排列，則構(gòu)成帕斯卡三角形。 \tbinom nk {\displaystyle (1+x)^{n}}x^{k}{\displaystyle {\binom {n}{0}},{\binom {n}{1}},\dots ,{\binom {n}{n}}}{\displaystyle n=0,1,2,\dots }

二項(xiàng)式系數(shù)常見于各數(shù)學(xué)領(lǐng)域中，尤其是組合數(shù)學(xué)。事實(shí)上，可以被理解為從n個(gè)相異元素中取出k個(gè)元素的方法數(shù)，所以大多讀作「n取k」。二項(xiàng)式系數(shù)的定義可以推廣至n是復(fù)數(shù)的情況，而且仍然被稱為二項(xiàng)式系數(shù)。

二項(xiàng)式系數(shù)亦有不同的符號表達(dá)方式，包括：C(n,k)、_nC_k、^nC_k、、[注3]，其中的C代表組合（combinations）或選擇（choices）。很多計(jì)算機(jī)使用含有C的變種記號，使得算式只占一行的空間，相同理由也發(fā)生在置換數(shù)，例如寫作P( n , k )。 {\displaystyle C_{n}^{k}}{\displaystyle C_{k}^{n}}{\displaystyle P_{k}^{n}}

定義及概念
對于非負(fù)整數(shù)n和k，二項(xiàng)式系數(shù)定義為的多項(xiàng)式展開式中，項(xiàng)的系數(shù)，即 \tbinom nk{\displaystyle (1+x)^{n}}x^{k}

{\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0} }+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}}
事實(shí)上，若x、y為交換環(huán)上的元素，則

(x+y)^n=\sum_{k=0}^n\binom nk x^{nk}y^k

此數(shù)的另一出處在組合數(shù)學(xué)，表達(dá)了從n物中，不計(jì)較次序取k物有多少方式，亦即從一n元素集合中所能組成k元素子集的數(shù)量。

計(jì)算二項(xiàng)式系數(shù)

除展開二項(xiàng)式或點(diǎn)算組合數(shù)量之外，尚有多種方式計(jì)算的值。 \tbinom nk

遞歸公式
以下遞歸公式可計(jì)算二項(xiàng)式系數(shù)：

\binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N

其中特別指定：

\binom n0 = 1 \quad \forall n\in\N\cup\{0\}, \binom 0k = 0 \quad \forall k\in\N.

此公式可由計(jì)算(1 + X ) n ?1 (1 + X )中的X k項(xiàng)，或點(diǎn)算集合{1, 2, ..., n }的k個(gè)元素組合中包含n與不包含n的數(shù)量得出。

顯然，如果k > n，則。而且對所有n，，故此上述遞歸公式可于此等情況下中斷。遞歸公式可用作建構(gòu)帕斯卡三角形。 \tbinom nk=0\tbinom nn=1

帕斯卡三角形(楊輝三角)

有關(guān)二項(xiàng)式系數(shù)的恒等式

關(guān)系式

階乘公式能聯(lián)系相鄰的二項(xiàng)式系數(shù)，例如在k是正整數(shù)時(shí)，對任意n有：

{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}} \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}.

兩個(gè)組合數(shù)相乘可作變換：

\binom ni \binom im=\binom nm \binom {nm}{im} \sum_{r=0}^n \binom nr = 2^{n}

{\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}}

{\displaystyle \sum _{r=0}^{nk}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {nk}{r} }={\binom {n}{k}}^{-1}}

\sum_{r=0}^n \binom {dn}{dr}=\frac{1}bh51tjlzh\sum_{r=1}^d (1+e^{\frac{2 \pi ri}{ d}})^{dn}

\sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} - \binom {a+m}{m-1}

\binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + ... + \binom {a+n} {n} = \binom {a+n+1}{n}

F_n=\sum_{i=0}^{\infty} \binom {ni}{i}

F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {ni }{i}=1+\sum_{i=1}^{\infty} \binom {ni}{i-1}+\sum_{i=1}^{\infty} \binom {ni}{i} =1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{ i}=F_{n+1}
主條目：朱世杰恒等式
\sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1} \binom {m}{a+1} + \binom ma + \binom {m+1}a ... + \binom na = \binom {n+1}{a+1}
二階求和公式
{\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}}
\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}=\binom {r_1+r_2+n-1 }{r_1+r_2-1}
(1-x)^{-r_1} (1-x)^{-r_2}=(1-x)^{-r_1-r_2}
(1-x)^{-r_1} (1-x)^{-r_2}=(\sum_{n=0}^{\infty} \binom {r_1+n-1}{r_1-1} x^ n)(\sum_{n=0}^{\infty} \binom {r_2+n-1}{r_2-1} x^n)=\sum_{n=0}^{\infty} (\sum_{ i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}) x^n
(1-x)^{-r_1-r_2}=\sum_{n=0}^{\infty} \binom {r_1+r_2+n-1}{r_1+r_2-1} x^n
主條目：范德蒙恒等式
\sum_{i=0}^k \binom ni \binom m{ki}=\binom {n+m}k
三階求和公式
主條目：李善蘭恒等式
{\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k}