排列組合
排列就是指從給定個數(shù)的元素中取出指定個數(shù)的元素進(jìn)行排序；組合則是指從給定個數(shù)的元素中僅僅取出指定個數(shù)的元素，不考慮排序。--------OI Wiki
乘法原理和加法原理
加法原理，就好比一個工作，有 \(n\) 個解決的方案，第 \(i\) 項(xiàng)方案有 \(a_{i}\) 種不同的實(shí)現(xiàn)方式，所以這個工作有 \(a_{1}+a_{2}+a_{3}+\ldots+a_{n}\) 種方式來解決。
乘法原理，就好比一個工作，有 \(n\) 個步驟，第 \(i\) 步有 \(a_{i}\) 種方法來完成，所以這個工作的方式有 \(a_{1}\times a_{2}\times a_{3}\times \ldots \times a_{n}\) 種方式來解決。
排列數(shù)
給定 \(n\) 個數(shù)，從中選取 \(m\) 個數(shù)形成一個排列，可能的排列的數(shù)量，用 \(A_{n}^{m}\) 來表示（給定的數(shù)都為正整數(shù)）。
排列的計(jì)算公式：
其實(shí)就是分子分母同乘一個 \((n-m)!\)。
其中 \(n!=1\times 2\times 3\times \ldots \times n\)。
全排列就是當(dāng) \(n=m\) 的時候的一種特殊情況，此時 \(A_{n}^{n}=n!\)。
組合數(shù)
區(qū)別就是，排列數(shù)是要求順序的，而組合數(shù)是從 \(n\) 個元素里面選取 \(m\) 個數(shù)組成一個集合，問有多少種可能，通常用 \(C_{n}^{m}\) 來表示。
組合數(shù)計(jì)算公式：
可以發(fā)現(xiàn)只比排列的公式分母多了一個 \(m!\)，因?yàn)椴豢紤]順序，所以可以想到，挑出來的 \(m\) 個元素組成的集合，里面的排列數(shù)是 \(m!\)，而這里面的元素組成的集合都是相同的，也就是這 \(m\) 個數(shù)本來應(yīng)該算一個，但是排列里面是算了 \(m!\)，所以排列的公式除以 \(m!\) 即為我們要求的答案。
現(xiàn)在人們習(xí)慣用 \(\binom{n}{m}\) 表示 \(n\) 個元素里面選 \(m\) 個，但是我個人覺得不如用 \(C_{n}^{m}\) 直觀，但我們還是要了解這個表示方式。
插板法
為什么叫插板法呢，因?yàn)樗怯糜诮鉀Q把一些相同種類的元素分成不同的幾組的一種方式， \(n\) 個元素分成 \(k\) 組，每一組至少有一個元素，就相當(dāng)于拿 \(k-1\) 個板子放到 \(n-1\) 個空里，故因此而得名。
因?yàn)樵厥峭耆嗤模晕覀兏鶕?jù)上面的組合數(shù)可以得出公式：
本質(zhì)是求 \(x_{1}+x_{2}+\ldots +x_{k}=n\) 的正整數(shù)解的組數(shù)。
改一下題目，如果要是允許有空的組呢？
如果這樣的話，直接插板是不行的，因?yàn)橛锌赡艹霈F(xiàn)一堆板子都插到一個空隙里，這樣的話求組合數(shù)就是錯誤的了。
所以我們先借來 \(k\) 個元素，在這 \(n+k-1\) 個空隙里插板，保證我們的每一組里面都是至少有 \(1\) 個元素，這樣我們就把這個問題轉(zhuǎn)化成了上一個問題，我們也可以得出公式：
可以想象一下，我們是先借了 \(k\) 個元素來保證我們的每一組里面都至少有一個元素，那么我們就按照第一個問題一樣求解，最后把所有的板子都拿走，那么答案是不會有所變化的。
本質(zhì)上是求 \(x_{1}+x_{2}+\ldots +x_{k}=n\) 的非負(fù)整數(shù)解的組數(shù)。
我們來加一些限制：如果說對于第 \(i\) 組我們需要至少分到 \(a_{i}\) 個元素，\(\sum a_{i}\le n\)，我們又該怎么去求解呢？
和上面一樣，本質(zhì)上就是求 \(x_{1}+x_{2}+\ldots+x_{k}=n，x_{i}\ge a_{i}\) 的解的組數(shù)。
我們淺想一下，設(shè) \(x_{i}'=x_{i}-a_{i}\)，所以 \(x_{i}=x_{i}'+a_{i}\)，那么我們要求的就是：
那么我們知道 \(x_{i}'\) 是一個非負(fù)的整數(shù)，所以我們可以直接用問題二的公式：
\(1\) 到 \(n\) 這 \(n\) 個自然數(shù)選 \(k\) 個，這 \(k\) 個數(shù)種任何兩個數(shù)都不相鄰的組合有 \(\binom{n-k+1}{k}\) 種。
二項(xiàng)式定理
二項(xiàng)式就是由兩項(xiàng)組成的式子，比如 \(2x\) 是一項(xiàng)式，\(2x+3y\) 是二項(xiàng)式，\(2x+3y+4z\) 是三項(xiàng)式，以此類推。
主要是用來解決 \((a+b)^{n}\) 的完全展開式的問題，其實(shí)是有規(guī)律可循的，我們可以通過這個定理快速獲得第 \(i\) 項(xiàng)。
舉一個最常見的例子：初中的完全平方公式 \((a+b)^{2}=a^{2}+2^{ab}+b^{2}\)。
或者高中的完全立方公式 \((a+b)^{3}=a^{3}+3a^{2}b+3ab^{3}+b^{3}\)。
相信你已經(jīng)發(fā)現(xiàn)了他們系數(shù)的規(guī)律，那就是楊輝三角，其實(shí)就是用來解釋 \((a+b)^{n}\) 的各項(xiàng)的系數(shù)才有的楊輝三角，這個東西很奇妙，我們后面會提到他和組合數(shù)的關(guān)系。
公式就是
\((a+b)^{n}=\sum_{i=0}^{n}\binom{n}{i}a^{n-i}b^{i}\)
為什么呢，你可以考慮一下，我們在推導(dǎo)完全立方公式的時候，我們是一項(xiàng)一項(xiàng)暴力拆開成 \(n\) 個 \((a+b)\) 相乘然后拆開合并的同類項(xiàng)，那么我們暴力拆一下可以知道，每一項(xiàng)都是從 \(n\) 個 \((a+b)\) 中選 \(a\) 或者 \(b\) 相乘得到的，也就是說，我們可以把展開后的第 \(i\) 項(xiàng)看作是選了 \(i\) 個 \(a\) 和 \(n-i\) 個 \(b\) 然后相乘得到的，而這樣的組合方案是 \(\binom{n}{i}\)，所以我們得到展開后第 \(i\) 項(xiàng)就是 \(\binom{n}{i}a^{n-i}b^{i}\) ，累加后就得到了上面的公式。
組合數(shù)性質(zhì)
下面挑幾個會的證明一下，不會的先咕了。
-
\[\binom{n}{m}=\binom{n}{n-m} \]
證明：
-
\[\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} \]
-
\[\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1} \]
證明：從 \(n\) 個數(shù)里面選 \(m\) 個數(shù)，就等同于第一個數(shù)選了，然后從 \(n-1\) 個中選 \(m-1\) 個數(shù)和第一個數(shù)沒選，從 \(n-1\) 個數(shù)中選 \(m\) 個數(shù)的方案的和。或者你可以看看楊輝三角
-
\[\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{n}=\sum_{i=0}^{n}\binom{n}{i}=2^{n} \]
-
\[\sum_{i=0}^{n}(-1)^{n}\binom{n}{i}=[n=0] \]
證明：當(dāng) \(m\) 為奇數(shù)的時候，由性質(zhì) \(1\) 得，兩項(xiàng)一一對應(yīng)和為 \(0\) ，顯然成立；當(dāng) \(m\) 為偶數(shù)的時候，利用 \(\binom{n}{0}=\binom{n-1}{0},\binom{m}{m}=\binom{m-1}{m-1}\) 替換，再用遞推式得到：
-
\[\sum_{i=0}^{m}\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}(n\ge m) \]
證明：
在 \((n+m)\) 個數(shù)中選 \(r\) 個數(shù)，在前 \(n\) 個中選 \(i\) 個數(shù)的方案有 \(\binom{n}{i}\) 種，在后 \(m\) 個里選 \((r-i)\) 個數(shù)的方案數(shù)為 \(\binom{m}{r-i}\) 種，相乘求和即可得到
一開始的式子就是這個式子的 \(r=m\) 的情況。
-
\[\sum_{i=0}^{n}\binom{n}{i}^{2}=\binom{2n}{n} \]
證明：其實(shí)是 \(6\) 的特殊情況，取 \(n=m\) 即可。
-
\[\sum_{i=0}^{n}i\binom{n}{i}=n2^{n-1} \]
證明：把左邊拆開得到：
-
\[\sum_{i=0}^{n}i^{2}\binom{n}{i}=n(n+1)2^{n-2} \]
證明：和性質(zhì) \(8\) 類似，先不證了。
-
\[\sum_{i=0}^{n}\binom{i}{k}=\binom{n+1}{k+1} \]
-
\[\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k} \]
證明：
分子與分母同乘 \((n-k)!\)
-
\[\sum_{i=0}^{n}\binom{n-i}{i}=F_{n+1} \]
-
\[\binom{n+m+1}{m}=\sum_{i=0}^{m}\binom{n+i}{i} \]
證明：首先對性質(zhì) \(3\) 變形：\(\binom{n}{m}+\binom{n}{m-1}=\binom{n+1}{m}\)，并且我們知道 \(\binom{n}{0}=\binom{n+1}{0}=1\)，那么就有：
最后就會得到：
其中 \(F\) 指斐波那契數(shù)列，\([n=0]\) 表示如果 \(n\) 為 \(0\) 則值為 \(1\)，反之值為 \(0\)。
其實(shí)還有二項(xiàng)式反演啥的但是我咕了。
組合數(shù)取模
有的時候我們題目里面會看到一些要求取模的那種問題。
當(dāng)然我們都知道取模之后做除法是會出問題的，這個時候我們就需要結(jié)合逆元來做。
我們大致可以把這類問題分為三類：
一、\(1\le n,m\le 1000\) ，\(p\) 為任意實(shí)數(shù)，顯然我們可以利用組合數(shù)的性質(zhì) \(\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\) 來遞推，但很明顯 \(O(n^{2})\) 的復(fù)雜度不足以讓我們在數(shù)據(jù)范圍更大的地方使用。
二、\(1\le n,m\le 10^{6}\)，\(p\) 為質(zhì)數(shù)且 \(p> 10^{6}\) ：\(O(n)\) 預(yù)處理 \(i!\bmod{p}\)，然后用費(fèi)馬小定理，擴(kuò)歐啥的搞一搞 \(m!\) 和 \((n-m)!\) 的逆元一乘就好，詢問是 \(O(\log n)\) 的，當(dāng)然也可以用線性求逆元直接 \(O(n\log n)\) 預(yù)處理 \(i!\) 和 \(i!\) 的逆元，詢問直接 \(O(1)\) 的：
ans=jc[n]*inv[m]*inv[n-m]%P;
三、若 \(p\) 為質(zhì)數(shù)，\(1\le n,m\le 10^{18},p\le 10^{5}\) ，這個時候用盧卡斯定理來解決，具體下面講。
其中最常用的是第二種了，因?yàn)轭}目里一般的取模都是 \(1e9+7\) 之類的某大質(zhì)數(shù)，而且 \(10^{6}\) 也足夠了。
盧卡斯定理
如上文所述，盧卡斯定理一般都是用于求解組合數(shù)取模。
上文中講的，當(dāng) \(p<m\) 的時候，分母的乘法逆元是可能不存在的（\(m\) 可能是 \(p\) 的倍數(shù)），所以我們就要用到盧卡斯定理。
內(nèi)容
對于非負(fù)整數(shù) \(n,m\) 和質(zhì)數(shù) \(p\)
（或許你在其他地方看見的都沒有這個乘號，我覺得打出來更清楚）
引理一
對于組合數(shù) \(\binom{p}{i}\)，其中 \(p\) 為質(zhì)數(shù)，滿足如下同余式子：
\[\binom{p}{i}\equiv 0 \pmod{p}(0<i<p) \]
首先我們由組合數(shù)的定義式可以知道：
由于 \(0<i<p\) ，且 \(p\) 為質(zhì)數(shù)，所以 \(i!\) 和 \((p-i)!\) 都不可能是 \(p\) 的因子。又因?yàn)榻M合數(shù)一定是一個整數(shù)，所以 \(i!(p-1)!\) 一定是 \((p-1)!\) 的因子，這樣組合數(shù)就可以表示成：
等式兩邊模 \(p\) 得到：
引理二
對于整數(shù) \(x\) 和素?cái)?shù) \(p\)，滿足如下同余式：
\[(1+x)^{p}\equiv (1+x^{p})\bmod{p} \]
還記得我們之前的二項(xiàng)式定理嗎，我們用它來對左邊進(jìn)行二項(xiàng)式展開，然后用引理一：
在第二步中將中間的多項(xiàng)都利用定理一給抹除了（因?yàn)槟?\(p\) 是 \(0\) 嘛）。
第三步中，因?yàn)?\(\binom{p}{p}=\binom{p}{0}=1\) 所以最后得到了這個式子。
證明
對于組合數(shù) \(\binom{n}{m}\)，將 \(n\) 和 \(m\) 分別除上 \(p\) 得到商和余數(shù)，設(shè)：
將 \((1+x)^{n}\bmod{p}\) 轉(zhuǎn)化成同余式：
第四步是用到了二項(xiàng)式定理。
或者：
由于這里 \(x\) 為未知數(shù)，所以等式左側(cè)的 \(x^{i}\) 系數(shù)必然與等式右側(cè)的系數(shù) \(x^{i}\) 的系數(shù)一致。
對于左側(cè) \((1+x)^{n}\) 中，$x^{m} $ 對應(yīng)的系數(shù)為 \(\binom{n}{n-m}=\binom{n}{m}=\binom{sp+q}{tp+r}\)
對于右側(cè)，\(x^{m}=x^{tp+r}=x^{tp}x^{r}\)，這有一種可能，即：
從而得到盧卡斯定理如下：
還可以表示成：
這樣就把問題轉(zhuǎn)化為了遞歸的問題，只要 \(n\ge p\) 時，我們就可以調(diào)用這個公式，將問題轉(zhuǎn)化為 \(\binom{n}{m}\bmod{p} (n<p)\) 的問題，而 \(p\le 10^{5}\) 時滿足：\(n<p\le 10^{5}\)
可以通過 \(O(n)\) 的復(fù)雜度計(jì)算出 \(n!\bmod{p}\) 和 \(inv_{n!}\bmod{p}\)，預(yù)處理完直接調(diào)用。文章來源：http://www.zghlxwxcb.cn/news/detail-451967.html
感謝OI Wiki以及bloodstalk的幫助文章來源地址http://www.zghlxwxcb.cn/news/detail-451967.html
到了這里，關(guān)于數(shù)論——組合數(shù)學(xué)入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
