這是離散數(shù)學(xué)的第四篇，討論高級計數(shù)技術(shù)。同步發(fā)布與個人博客，上一篇（【離散數(shù)學(xué)】計數(shù)/排列組合）討論了計數(shù)以及排列組合，二項式定理等。但是僅憑排列組合等手段依然無法解決許多計數(shù)問題。這里首先討論通過遞推關(guān)系來求解計數(shù)問題，并介紹有遞推關(guān)系引出的兩個算法范式：動態(tài)規(guī)劃和分治。這兩種算法均是通過將問題分割為一系列的子問題來求解的，區(qū)別就是前者分割出來的子問題互相重疊，后者的子問題不重疊。這是兩種很重要的算法，加上貪心、回溯、分支定界為五種很常用的算法。這里僅僅簡單討論思路，并分析其復(fù)雜度。關(guān)于具體的算法分析以及算法設(shè)計以后應(yīng)該會討論。而后介紹了求解一類很常見的特定遞推關(guān)系——常系數(shù)線性齊次與非齊次遞推關(guān)系的形式解法。并且還介紹了一種求解計數(shù)問題的很重要的手段——生成函數(shù)，這是冪級數(shù)的應(yīng)用。最后介紹容斥原理，對，就是集合的容斥原理。以上內(nèi)容以前均有涉及，這里再次探討。

---

遞推關(guān)系的應(yīng)用

經(jīng)典問題——漢諾塔

這是一個及其經(jīng)典的問題，見漢諾塔（Tower of Hanoi），三根柱子，n個盤子，從上到下盤子從小到大。將所有n個盤子從一根柱子移動到另一根柱子，移動過程中小的盤子不能放在大的盤子下面?？梢郧蠼獬鏊枰淖钚〔綌?shù)，還可以編寫算法打印出所有步數(shù)。

n=3的漢諾塔移動方法：

令移動n個盤子到另一個柱子所需最少次數(shù)為 $H_n$ ，考慮最下面一個最大的盤子，由于小的盤子不能放在大的盤子下面，所以必須首先將上面n-1個移動到另一個柱子，再將最下面的最大的一個移動到另一根柱子，再將n-1個移到其上，則完成了n個盤子的移動。則得到遞推關(guān)系 $H_n=2H_{n?1}+1$。初始條件很容易知道：$H_0=0$，$H_1=1$。

求解遞推關(guān)系：容易看出 $H_n+1=2(H_{n?1}+1)$，可以得到 $H_n=2^n?1$?？梢宰C明這便是移動n個盤子所需的最少次數(shù)。

卡特蘭數(shù)

考慮一個在n+1個數(shù) $x_0\cdot x_1 \cdot x_2 \cdots x_n $ 的乘積中插入括號來規(guī)定乘法次序的方式數(shù)，令其為 $C_n$。
這里注意到一定會有一個乘法是在括號外面的（不需要加括號），假設(shè)其在$x_k$和$x_{k+1}$之間，則存在$C_k{C}_{n?k?1}$種方式，考慮最后一個乘號可能取n個位置，則有$$C_n=\sum _{k=0}^{n?1}{C}_k{C}_{n?k?1}$$

初始條件則為$C_0=1$，$C_1=1$。
利用生成函數(shù)的方法可以證明：$C_n=\frac{C(2n,n)}{n+1}$，被稱作第n個卡特蘭（Catalan）數(shù)，序列$\{C_n\}$ 被稱為卡特蘭數(shù)的序列。參見 OEIS A000108，Catalan number - Wikipedia。

動態(tài)規(guī)劃與遞推關(guān)系

動態(tài)規(guī)劃（Dynamic programming，DP）是一種算法范式，遵循動態(tài)規(guī)劃范式的算法是將原問題分解為更簡單的重疊的子問題，通過子問題的求解來求解原問題。常用于求解最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題。此類問題若用分治法來解，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次。所以DP通過保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，從而降低復(fù)雜度。以后單獨討論，這里推薦閱讀：動態(tài)規(guī)劃解決01背包問題，什么是動態(tài)規(guī)劃？動態(tài)規(guī)劃的意義是什么？。

---

求解線性遞推關(guān)系

這部分給人的感覺相當(dāng)熟悉，在高等數(shù)學(xué)中有線性微分方程的求解，線性代數(shù)中有線性方程組的求解，與這里的線性遞推關(guān)系的求解十分類似，可以說是如出一轍。

求解常系數(shù)線性齊次遞推關(guān)系

一個常系數(shù)的$k$階線性齊次遞推關(guān)系指的是形如 $a_n=c_1{a}_{n?1}+c_2{a}_{n?2}+?+c_k{a}_{n?k}$，的遞推關(guān)系，其中$c_i$為實數(shù)，$c_k?=0$。

為了求解$k$階常系數(shù)線性齊次遞推關(guān)系，這里的基本方法是尋找形如$a_n=r^n$的解，其中r是常數(shù)。遞推關(guān)系要有形如$a_n=r^n$的解，則當(dāng)且僅當(dāng)$r$是方程$$r^k?c_1{r}^{k?1}?c_2{r}^{k?2}???c_{k?1}r?c_k=0$$的解。
將上述方程稱為該遞推關(guān)系的特征方程。方程的解稱為特征根。（與求解常系數(shù)線性微分方程如出一轍）。特征根有可能是復(fù)數(shù)，但這里僅考慮特征根為實數(shù)的情況。

定理：假設(shè)特征方程$$r^k?c_1{r}^{k?1}???c_k=0$$有k個不相等的根$r_1,r_2,...,r_k$。那么遞推關(guān)系$a_n=c_1{a}_{n?1}+c_2{a}_{n?2}+?+c_k{a}_{n?k}$的解為$$a_n={\alpha }_1{r}_1^n+{\alpha }_2{r}_2^n+?+{\alpha }_k{r}_k^n$$

$n\in N,{\alpha }_1,{\alpha }_2,...,{\alpha }_k$是常數(shù)。
另外，對其中的每一個特征根$r_i$，如果并非一重而是$m_i$重時，則用 $({\alpha }_{i,0}+{\alpha }_{i,1}n+?+{\alpha }_{i,m_i?1}{n}^{m_i?1})r_i^n$ 替代 上述解中的${\alpha }_i{r}_i^n$即可。

例：斐波那契數(shù)列（OEIS A000045）
遞推關(guān)系$f_n=f_{n?1}+f_{n?2}$，初始條件$f_0=0,f_1=1$。
特征方程$r^2?r?1=0$ 根為 $r_1=(1+\sqrt{5})/2$，$r_2=(1?\sqrt{5})/2$。
則$$f_n={\alpha }_1{\left(\frac{1+\sqrt{5}}{2}\right)}^n+{\alpha }_2{\left(\frac{1?\sqrt{5}}{2}\right)}^n$$代入$f_0,f_1$解出${\alpha }_1=\frac{1}{\sqrt{5}}$，${\alpha }_2=?\frac{1}{\sqrt{5}}$
則得到斐波那契數(shù)列的顯式公式為$$f_n=\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^n?\frac{1}{\sqrt{5}}{\left(\frac{1?\sqrt{5}}{2}\right)}^n$$

求解常系數(shù)線性非齊次遞推關(guān)系

常系數(shù)線性非齊次遞推關(guān)系：形如 $a_n=c_1{a}_{n?1}+c_2{a}_{n?2}+?+c_k{a}_{n?k}+F(n)$，與其相伴的齊次遞推關(guān)系為 $a_n=c_1{a}_{n?1}+c_2{a}_{n?2}+?+c_k{a}_{n?k}$，很顯然 通解 = 特解+齊次解。

齊次解即對應(yīng)的常系數(shù)線性齊次遞推關(guān)系的解，記作$a_n^{(h)}$，特解記作$a_n^{(p)}$。

不同形式的F(n)具有不同形式的特解

$F(n)$特解形式

$an+b$	$cn+d$
$\alpha ?c^n$	$\beta ?c^n$

若 $F(n)$ 形如 $(b_t{n}^t+b_{t?1}{n}^{t?1}+?+b_{1}n+b_0)s^n$.
則當(dāng) $s$ 不是特征根時，特解形如 $(p_t{n}^t+p_{t?1}{n}^{t?1}+?+p_{1}n+p_0)s^n$.
當(dāng) $s$ 是$m$重特征根時，特解形如 $n^m(p_t{n}^t+p_{t?1}{n}^{t?1}+?+p_{1}n+p_0)s^n$.

---

分治算法與遞推關(guān)系

與動態(tài)規(guī)劃相似，分治算法（Divide and conquer algorithm）范式也會將問題劃分為一個或者多個小問題，不過這些小問題是不重疊的。連續(xù)使用這種劃分直到可以快速找到這些小問題的解，然后將小問題的解合并為原問題的解。即三個步驟：分割原問題，解決子問題，合并得到最終解。常見簡單分治算法：歸并排序、二分查找。這里將說明怎樣用遞關(guān)系來分析分治算法的復(fù)雜度。

分治遞推關(guān)系

假設(shè)一個遞歸算法將規(guī)模為n的問題劃分為a個子問題，每個子問題規(guī)模為n/b，并且需要g(n)的額外運算來合并這些子問題。用f(n)表示求解問題規(guī)模為n的問題所需運算數(shù)，則$$f(n)=af(n/b)+g(n)$$

令$n=b^k$，多次迭代后可以得到：
$$f(n)=a^{k}f(1)+\sum _{j=0}^{k?1}{a}^{j}g(n/b^j)$$

很容易知道，
二分查找的分治遞推關(guān)系：$f(n)=f(n/2)+2$
歸并排序的分治遞推關(guān)系：$M(n)=2M(n/2)+n$

分治算法的復(fù)雜度分析

定理1：設(shè)$f(n)$是滿足$f(n)=af(n/b)+c$ 的增函數(shù)，$n$被$b$整除，$a?1$，
$b$是大于1的整數(shù)，$c$是正實數(shù)。那么
$$f(n)=\{\begin{array}{ll}O(n^{lo{g}_{b}a})& a>1\\ O(\log n)& a=1\end{array}$$證明：令$n=b^k$即可證得，當(dāng)$n?=b^k$時，依然成立。

很容易得出二分查找復(fù)雜度為$O(\log n)$。

主定理：若$f(n)=af(n/b)+c{n}^d$，則$$f(n)=?\begin{array}{ll}O(n^d)& a<b^d\\ O(n^d\log n)& a=b^d\\ O(n^{lo{g}_{b}a})& a?b^d\end{array}$$

同理，令$n=b^k$即可證得。（ps：上面的$?$表示大于號，但其實這個符號并不是這個意思。這里有一個bug，hexo自帶一個功能的會把一段內(nèi)連續(xù)的<>之間的內(nèi)容注釋掉，于是就只好將就一下。）

根據(jù)主定理，很容易得出歸并排序復(fù)雜度為$O(n\log n)$。
可以看到，定理1只是主定理的特殊情況。
這里僅簡單分析分治算法，并解決了其復(fù)雜度的問題，并未涉及分治算法的設(shè)計及具體實現(xiàn)。

---

生成函數(shù)

表示序列的一個有效方法是生成函數(shù)，把序列的項作為形式冪級數(shù)的變量x的冪的系數(shù)?？梢杂蒙珊瘮?shù)解決許多類型的計數(shù)問題。拓展閱讀：Generating function - Wikipedia，什么是生成函數(shù)? | Matrix67: The Aha Moments。

定義

實數(shù)序列$a_0,a_1,...,a_k,...$的（普通）生成函數(shù)是無窮級數(shù)$$G(x)=\sum _{k=0}^{\infty }{a}_k{x}^k$$

例：序列$\{C(n,k)\}$的生成函數(shù)即是$G(x)=(1+x{)}^n$.

使用生成函數(shù)求解計數(shù)問題時，通?？紤]形式冪級數(shù)，即不需要考慮其收斂域（對發(fā)散或收斂并不感興趣）

廣義二項式定理

廣義二項式系數(shù)：
$u$為實數(shù)，$k$為非負(fù)整數(shù)，廣義二項式系數(shù)定義為
$${(}_k^u)=\{\begin{array}{ll}u(u?1)?(u?k?1)/k!& k>0\\ 1& k=0\end{array}$$

當(dāng)u為負(fù)整數(shù)時，展開即可有下列式子成立$${(}_k^{?n})=(?1{)}^{r}C(n+r?1,r)$$

廣義二項式定理：
$x$是實數(shù)，$|x|<1$，$u$ 是實數(shù)，那么$$(1+x{)}^u=\sum _{k=0}^{\infty }{(}_k^u)x^k$$

其實這就是$(1+x{)}^u$的冪級數(shù)展開，使用麥克勞林級數(shù)（即在x=0處泰勒展開）即可證明。

常用生成函數(shù)

這里給出一些最常用生成函數(shù)，以及其對應(yīng)的序列一般項。

(1). $(1+ax{)}^n={\sum }_{k=0}^{n}C(n,k)a^k{x}^k$，$a_k=C(n,k)a^k$，二項式定理得到
(2). $\frac{1?x^{r+1}}{1?x}={\sum }_{k=0}^n{x}^k$，$a^k=1,k?n$；否則為0，幾何級數(shù)求和得到
(3). $\frac{1}{1?ax}={\sum }_{k=0}^{\infty }{a}^k{x}^k$，$a_k=a^k$，對$|x|<1$的幾何級數(shù)求和取極限得到
(4). $\frac{1}{(1?x{)}^2}={\sum }_{k=0}^{\infty }(k+1)x^k$，$a_k=k+1$，對$\frac{1}{1?x}$求導(dǎo)得到
(5). $\frac{1}{(1?x{)}^n}={\sum }_{k=0}^{\infty }C(n+k?1,k)x^k$，$a_k=C(n+k?1,k)=C(n+k?1,n?1)$，由廣義二項式定理得到
(6). $e^x={\sum }_{k=0}^{\infty }\frac{x^k}{k!}$，$a_k=1/k!$，泰勒展開即可得到
(7). $\ln (1+x)={\sum }_{k=0}^{\infty }\frac{(?1{)}^{k+1}}{k}{x}^k$，$a_k=(?1{)}^{k+1}/k$，同上泰勒展開得到

生成函數(shù)可以用來求解計數(shù)問題，還可以用來求解遞推關(guān)系和證明組合恒等式。這里不想寫了，略過吧！（笑）

---

容斥原理及其應(yīng)用

兩個集合的容斥原理是很熟悉的，$|A\cup B|=|A|+|B|?|A\cap B|$，那么對于多個幾個呢？很容易想到，但可能并不容易寫出來。Inclusion–exclusion principle。

容斥原理

設(shè)$A_1,A_2....,A_n$是有窮集，則$$\begin{gathered} |A_1\cup A_2\cup ?\cup A_n|=\sum _{1?i?n}|A_i|?\sum _{1?i<j?n}|A_i\cap A_j| \\ +\sum _{1?i<k<j?n}|A_i\cap A_j\cap A_k|+?+(?1{)}^{n+1}|A_1\cap A_2\cap ?\cap A_n| \end{gathered}$$

可以看到加號和減號是交替出現(xiàn)的，保證了沒有遺漏也沒有重復(fù)。

三個集合的容斥原理：

應(yīng)用很多，此處愉快地略過。

---

結(jié)語

其實我只想快速看完這本書，寫完了之后，好好想一想應(yīng)該怎樣去寫。還有慢慢肝算法導(dǎo)論，重新回顧數(shù)據(jù)結(jié)構(gòu)，一堆技術(shù)書等著去肝呢！所有省略了很多內(nèi)容，對自己還未掌握的東西抄上來就沒有多大意義了。給了很多鏈接，但其實大部分鏈接我都未曾去認(rèn)真看過（笑）。

逐步積累，隨性記錄，知道自己要去的地方、要走的路，一直寫著就好?！?01.3.7

---

參考資料：《離散數(shù)學(xué)及其應(yīng)用》（本科教學(xué)版，Kenneth H.Rosen著，原書第七版）

總結(jié)

以上是生活随笔為你收集整理的【离散数学】高级计数技术的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。