容斥原理應(yīng)用和典型的遞歸關(guān)系

• 容斥原理應(yīng)用
• • 前言
• 錯位排列
• 棋陣多項式
• 禁位排列
• 遞歸關(guān)系
• • Hanoi塔問題
  • 平面分割問題

容斥原理應(yīng)用

前言

容斥原理是組合數(shù)學(xué)中的一個重要原理，它在計數(shù)研究中占有重要地位。但容斥原理所研究的計數(shù)是若干有限集的交、并或差的計數(shù)。

由于我們講的是應(yīng)用，因此原理就不再仔細(xì)展開。我們在應(yīng)用的時候要將某一類滿足某種性質(zhì)的元素看成集合，這個是應(yīng)用容斥原理的最基本的技巧。

錯位排列

定義：設(shè)集合S=(1，2，3，…，n}，則S的排列數(shù)為n!。若其中有兩個排列12…n和 i1i2?in, 如果 i1≠1,i2≠2,?,in≠n 則稱排列ji2…1為12…n的一個錯位排列。即是說，一個錯位排列就是使得原排列的每個元素都不在原來位置的排列。簡稱為$D_n$

由規(guī)律我們得到遞推關(guān)系：$D_n=(n?1)(D_{n?1}+D_{n?2}$

由D1 = 0 ， D2 = 1,所以D0 = 1 ，那么通過化簡我們有$D_n=n{D}_{n?1}+(1?{)}^n$

定理：對于n>=1 ，有$$D_n=n!(1?\frac{1}{1!}+...+(?1{)}^n\frac{1}{n!})$$
證明：
證設(shè)S={1，2，…，n}，S0為S的所有n！個排列的集合。令A(yù)j表示排列1,2…,n中使j位置上的元素保持不動的排列的集合，j=1，2，…，n。則排列1,2,…,n的所有錯位排列必是在$\overline{A1}\cap \overline{A2}\cap ?\cap \overline{An}$.中的那些排列，故有。$D_n=\overline{A1}\cap \overline{A2}\cap ?\cap \overline{An}$。而且
$Aj=(n?1)!,j=1,2,??,n$。
$\mid Ai\cap Ai\mid =(n?2)!,i，j=1，2，\dots ，n，但i=j$
對于任意整數(shù)k且1≤k≤n，則有
$\mid An\cap A2\cap ?\mid Ak\mid =(n?k)!$
圖為(1，2，…,k)的k組合為$C(n,k)$個，應(yīng)用容斥原理得到
$D_n=n!(1?\frac{1}{1!}+...+(?1{)}^n\frac{1}{n!})證畢$。

棋陣多項式

概念
n個棋子在n×n的棋盤上的一種布局，并規(guī)定：每行每列有且只有一個棋子，這樣一種布局對應(yīng)n個元素的某一排列。例如，下圖是一個4×4的棋盤，4個棋子在棋盤上的一種布局，如圖所示，其所對應(yīng)的排列為2314。

可以把棋盤C推廣到任意形狀。
$設(shè)為r_k(C)為k個棋子按規(guī)定布置到棋盤C上的不同方案數(shù)$

禁位排列

定義：是指在一個排列中禁止某些元素占據(jù)某些位置。

證明：對于其證明我們是正難則方的思路先求落入禁區(qū)的，在求禁區(qū)的方案數(shù)需要用到容斥原理。
若有n個棋子布入n×n的棋盤。設(shè)$A_i$為i個棋子落入禁區(qū)的排列集合，i=1，2，…，n。

若一個棋子落入禁區(qū)的方案數(shù)為$r1$，剩下的n-1個棋子為無限制的排列，故至少有一個棋子落入禁區(qū)的排列數(shù)為$r_1?(n?1)!$。兩個棋子落入禁區(qū)的方案數(shù)為$r_2$，而其余n-2個棋子為無限制的排列，故至少有兩個棋子落入禁區(qū)的排列數(shù)為$r_2?(n?2)!$，依此類推。由容斥原理，n個棋子無一落入禁區(qū)的排列數(shù)為
$$\begin{gathered} Q_n=\overline{A1}\cap \overline{A2}\cap ?\cap \overline{An} \\ =n!?r_1?(n?1)!+r_2?(n?2)!+?+(?1{)}^{?}{r}_n?0! \end{gathered}$$ 證畢。

而對于$r_1,r_2,..,r_n$的值我們有由禁區(qū)組成圖形的棋陣多項式求出。

遞歸關(guān)系

定義：對于數(shù)列$a_1，a?2，a_3，\dots ，a_n$ 把該數(shù)列中除了有限個數(shù)以外的任何數(shù)a，和它前面的一個或一些數(shù)關(guān)聯(lián)起來的方程叫做遞歸關(guān)系。為了能夠著手計算，必須知道數(shù)列中的一個或一些數(shù)，這樣的數(shù)叫做邊界條件

Hanoi塔問題

我們將n個盤從a柱移動到c柱上，需要移動的次數(shù)分析如下：

令h(n)為n個盤從a柱移到c柱所需移動的盤次。顯然，當(dāng)n=1時，只需移動一個盤次，故h(1)=1。當(dāng)n=2時，先將上面的小盤移到b柱上；然后，將下面的大盤移到c柱上；最后再將b柱上的小盤移到c柱上，共計移動3個盤次，故h(2)=3。依此類推，總之，當(dāng)有n個盤時，設(shè)法先將上面的n-1個盤移到b柱上，再將第n個盤從a柱移到c柱上，然后再把b柱上的n-1個盤設(shè)法移動到c柱上。于是我們得到以下遞歸關(guān)系
$$h(n)=2h(n一1)+1，h(1)=1，n=2，3，\dots .$$

通過母函數(shù)求解后得到：
$$h(n)=2^n?1$$

平面分割問題

1.問題的提出
設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，問這些封閉曲線把平面分割成的區(qū)域個數(shù)。
2.問題的分析
令a點為n條封閉曲線把平面分割成的區(qū)域個數(shù)。顯然，當(dāng)n=1時， a1=2; 當(dāng)n=2時， a2=4; 當(dāng)n=3時， 。a3=8,?。 于是我們發(fā)現(xiàn)一個規(guī)律：若n-1條封閉曲線把平面分割成的區(qū)域個數(shù)為an-，，則第n條封閉曲線與這n-1條封閉曲線相交于2(n-1)個點，這2(n-1)個點把第n條封閉曲線截成2(n-1)段弧，這些弧把原來的2(n―1)個區(qū)域中的每個區(qū)域一分為2，故新增加的區(qū)域個數(shù)為2(n-1)，如圖6.2所示，于是得到以下遞歸關(guān)系

$$a_n=a_{n?1}+2(n?1),a_1=2,a_0=2,n=2,3$$

通過母函數(shù)求解后得到：
$$a_n=n(n?1)+2$$

總結(jié)

以上是生活随笔為你收集整理的算法之组合数学及其算法篇(三） ----- 容斥原理应用以及几个典型的递归关系的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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