組合數(shù)學(xué)（第二版）遞推關(guān)系

遞推關(guān)系3.1基本概念3.2常系數(shù)線性遞推關(guān)系3.3解遞推關(guān)系的其它方法3.4三種典型數(shù)列3.5應(yīng)用

3.1基本概念

定義3.1.1a對數(shù)列{ai|i≥0}和任意自然數(shù)n,一個關(guān)系到an

和某些個ai(i<n)的方程式,稱為遞推關(guān)系,記作上式只是一種定義方式,也稱為隱式定義.另外,也有顯式定義.

定義3.1.1b對數(shù)列{ai|i≥0},把an與其前若干項聯(lián)系起來的等式對所有n≥k均成立(k為某個給定的自然數(shù)),稱該等式為{ai}的遞推關(guān)系,記為

分類除了有顯式與隱式之分外,還有如下的分法:

(1)按常量部分:①齊次遞推關(guān)系:即常量=0,

如Fn=Fn-1+Fn-2;②非齊次遞推關(guān)系,即常量≠0,如hn-2hn-1=1.

(2)按ai的運算關(guān)系:

①線性關(guān)系:F是關(guān)于ai的線性函數(shù),

如(1)中的Fn與hn均是如此;

②非線性關(guān)系:F是ai的非線性函數(shù),

如hn=h1hn-1+h2hn-2+…+hn-1h1.

(3)按ai的系數(shù)分:

①常系數(shù)遞推關(guān)系,如(1)中的Fn與hn;

②變系數(shù)遞推關(guān)系,如pn=npn-1,pn-1之前的系數(shù)是隨著n而變的.

(4)按數(shù)列的多少:①一元遞推關(guān)系:指方程只涉及一個數(shù)列,如式(3.1.1a)和(3.1.1b)均為一元的;②多元遞推關(guān)系:指方程中涉及多個數(shù)列,如

以上所給出的例子都是顯式的或者可以化為顯式關(guān)系(如(1)中的hn).而在求微分方程的數(shù)值解時,還會碰到如下的隱式遞推關(guān)系:

定義3.1.2(定解問題)稱含有初始條件的遞推關(guān)系為定解問題,其一般形式為

所謂解遞推關(guān)系,就是指根據(jù)式(3.1.1a)或(3.1.2)求an

的且與a0、a1、……、an-1無關(guān)的解析表達(dá)式或數(shù)列{an}的母函數(shù).

【例3.1.1】(Hanoi塔問題)這是組合學(xué)中著名的問題.n個圓盤按從小到大的順序依次套在柱A上,如圖3.1.1所示.規(guī)定每次只能從一根柱子上搬動一個圓盤到另一根柱子上,且要求在搬動過程中不允許大盤放在小盤上,而且只有A、B、C三根柱子可供使用.用an

表示將n個盤從柱A移到柱C上所需搬動圓盤的最少次數(shù),試建立數(shù)列{an}的遞推關(guān)系.圖3.1.1Hanoi塔問題

解易知,a1=1,a2=3,對于任何n≥3,現(xiàn)設(shè)計搬動圓盤的算法如下:第一步,將套在柱A的上部的n-1個盤按要求移到柱B上,共搬動了an-1次;第二步,將柱A上的最大一個盤移到柱C上,只要搬動一次;第三步,再從柱B將n-1個盤按要求移到柱C上,也要用an-1次.由加法法則,{an}的定解問題為

【例3.1.2】(藍(lán)開斯特(Lancaster)戰(zhàn)斗方程)兩軍打仗,每支軍隊在每天戰(zhàn)斗結(jié)束時都清點人數(shù),用a0和b0分別表示在戰(zhàn)斗打響前第一支和第二支軍隊的人數(shù),用an和bn分別表示第一支和第二支軍隊在第n天戰(zhàn)斗結(jié)束時的人數(shù)，那么,an-1-an

就表示第一支軍隊在第n天戰(zhàn)斗中損失的人數(shù)，同樣,bn-1-bn表示第二支軍隊在第n天戰(zhàn)斗中損失的人數(shù)

假設(shè)一支軍隊所減少的人數(shù)與另一支軍隊在每天戰(zhàn)斗開始前的人數(shù)成比例,因而有常數(shù)A和B,使得

其中常量A、B是度量每支軍隊的武器系數(shù),將上述等式改寫成

這是一個含有兩個未知量的一階線性遞推關(guān)系組.

【例3.1.3】設(shè)

求{an}所滿足的遞推關(guān)系.

解分兩種情況:當(dāng)n為偶數(shù)時,令n=2m,則

其中[]稱為下整函數(shù),其值定義為不大于x的最大整數(shù)。于是an

可寫成

于是得

當(dāng)n為奇數(shù)時,同樣可證上述遞推關(guān)系成立.

因此,an所滿足的遞推關(guān)系是

另外,顯然有a0=a1=1

3.2常系數(shù)線性遞推關(guān)系

常系數(shù)的線性遞推關(guān)系總可以化為如下形式:或分別稱為k階齊次遞推關(guān)系和k階非齊次遞推關(guān)系.其中f(n)稱為自由項.

3.2.1解的性質(zhì)

3.2.2解的結(jié)構(gòu)

定義3.2.1稱多項式

為齊次遞推關(guān)系式(3.2.1)的特征多項式,相應(yīng)的代數(shù)方程C(x)=0稱為式(3.2.1)的特征方程,特征方程的解稱為式(3.2.1)的特征根.

定理3.2.1數(shù)列an=qn是式(3.2.1)的非零解的充分必要條件是q為式(3.2.1)的特征根.

證

an=qn是式(3.2.1)的解?qn+c1qn-1+…+ckqn-k=0?qk+c1qk-1+…+ck=0?q是方程C(x)=0的根,即q是式(3.2.1)的特征根.

定理3.2.1的意義在于將求解常系數(shù)線性齊次遞推關(guān)系的問題轉(zhuǎn)化為常系數(shù)代數(shù)方程的求根問題,從而給出了一個實用且比較簡單的解此類遞推關(guān)系的方法.

定義3.2.2若{a(1)

n},{an(2)},…,{an(s)}是式(3.2.1)的不同解,且式(3.2.1)的任何解都可以表為r1an(1)+r2an(2)+…+rsan(s)=an,則稱an為式(3.2.1)的通解.其中r1,r2,…,rs為任意常數(shù).

此處所說的不同解是指將每一個解{an(i)}都視為一個無窮維的解向量,而這些向量之間是線性無關(guān)的.

所以,通解an=r1an(1)+r2an(2)+…+rsan(s)應(yīng)具備如下3個特征:

(1)通解首先是解,這由性質(zhì)1即可看出.

(2)組成通解的所有解向量線性無關(guān).

(3)任何一個具體的解都被包容在通解an中.

3.2.3特征根法

該方法的思路就是通過解式(3.2.1)的特征方程,從而求得其特征根,再利用特征根即可獲得式(3.2.1)的通解.根據(jù)特征根的不同分布情況,分為下述三種情形予以討論.

1.特征根為單根情形

設(shè)q1,q2,…,qk是式(3.2.1)的互不相同的特征根,則式(3.2.1)的通解為

其中A1,A2,…,Ak為任意常數(shù)(待定).

【例3.2.1】求遞推關(guān)系an-4an-1+an-2=-6an-3的通解.

解特征方程為x3-4x2+x+6=0,解之得特征根

所以通解為

其中,A、B、C為任意常數(shù).

2.重根情形

對于特征方程有重根的情形,不能直接套用單根時的方法.下面先通過實例,再歸納給出此種情況下的通解.

【例3.2.2】求遞推關(guān)系an-4an-1+4an-2=0的通解.

3.復(fù)根情形

【例3.2.4】求定解

3.2.4非齊次方程

對于非齊次方程,比較有規(guī)律的解法主要是針對f(n)的幾種特殊情形.

定理3.2.2設(shè)an*是式(3.2.2)的一個特解,是式(3.2.1)的通解,則式(3.2.2)的通解為

證首先由解的性質(zhì)知,an是式(3.2.2)的解.

其次,證明an

是通解.若給定一組初始條件

可以仿照齊次方程通解的證明方法,證得相應(yīng)于條件式(3.2.11)的解一定可以表示為式(3.2.10)的形式.

關(guān)于的求法已經(jīng)解決,這里的主要問題是求式(3.2.2)的特解an

*.遺憾的是尋求特解還沒有一般通用的方法.然而,當(dāng)非齊次線性遞推關(guān)系的自由項f(n)比較簡單時,采用下面的待定系數(shù)法比較方便.

1.f(n)=b(b為常數(shù))

其中m表示1是式(3.2.1)的m重特征根(0≤m≤k).當(dāng)然,若1不是特征根(即m=0),則an*=A.

2.f(n)=bn(b為常數(shù))

其中m表示b是式(3.2.1)的m重特征根(0≤m≤k).同樣,若b不是特征根(即m=0),則an*=Abn.

3.f(n)=bnPr(n)(其中Pr(n)為關(guān)于n的r次多項式,b為常數(shù))

其中Qr(n)是與Pr(n)同次的多項式,m仍然是b為特征根的重數(shù)(0≤m≤k).當(dāng)b不是特征根時(即m=0),an*=bnQr(n).

3.2.5一般遞推關(guān)系化簡

對于某些非線性或變系數(shù)的遞推關(guān)系,可以將其化為線性關(guān)系來求解.

【例3.2.12】設(shè)n≥1,an≥0.解定解問題

解這是非線性的遞推關(guān)系,令bn=an2,將問題變?yōu)?/p>

3.3解遞推關(guān)系的其它方法

3.3.1迭代法與歸納法

對于某些特殊的,尤其是一階的遞推關(guān)系,使用迭代法求解可能更快.而有些遞推關(guān)系則可以通過觀察n比較小時an的表達(dá)式的規(guī)律,總結(jié)或猜出an的一般表達(dá)式,然后再用歸納法證明之即可.

【例3.3.1】解遞推關(guān)系

3.3.2母函數(shù)方法

對于一些較復(fù)雜的遞推關(guān)系,利用母函數(shù)方法求解是很有效的.當(dāng)用它求解數(shù)列{an}的遞推關(guān)系時,一開始并不企圖直接找出an的解析表達(dá)式,而是首先作出{an}的母函數(shù)

由2.2節(jié)母函數(shù)的性質(zhì)3知

于是得到

【例3.3.9】用母函數(shù)方法求解二元遞推關(guān)系.

解設(shè)數(shù)列{an}的母函數(shù)為A(x),{bn}的母函數(shù)為B(x).在第一個方程的兩邊同乘

所以,原遞推關(guān)系的解為

3.4三種典型數(shù)列

3.4.1Fibonacci數(shù)列序列1,1,2,3,5,8,13,21,34,…中,每個數(shù)都是它前兩者之和,這個序列稱為Fibonacci數(shù)列.由于它在算法分析和近代優(yōu)化理論中起著重要作用,又具有很奇特的數(shù)學(xué)性質(zhì),因此,1963年起美國就專門出版了針對這一數(shù)列進(jìn)行研究的季刊《FibonacciQuarterly》.

該數(shù)列來源于1202年由意大利著名數(shù)學(xué)家Fibonacci提出的一個有趣的兔子問題:有雌雄一對小兔,一月后長大,兩月起往后每月生(雌雄)一對小兔.小兔亦同樣如此.設(shè)一月份只有一對小兔,問一年后共有多少對兔子?

更一般地,此問題可以變?yōu)閚個月后共有多少對兔子?

將開始有第一對小兔的月份視為第一個月,用Fn表示在第n個月的兔子數(shù),顯然F1=F2=1.其次,可以看出．

【例3.4.1】(上樓梯問題)某人欲登上n級樓梯,若每次只能跨一級或兩級,他從地面上到第n級樓梯,共有多少種不同的方法?

解設(shè)上到第n級樓梯的方法數(shù)為an.那么,第一步無非有兩種可能:

(1)跨一級,則余下的n-1級有an-1種上法;

(2)跨兩級,則余下的n-2級有an-2種上法

【例3.4.2】棋盤染色問題:給一個具有1行n列的1×n棋盤(見圖3.4.1)的每一個方塊涂以紅、藍(lán)二色之一,要求相鄰的兩塊不能都染成紅色,設(shè)不同的染法共有an

種,試求an.圖3.4.11×n棋盤

【例3.4.3】交替子集問題:有限整數(shù)集合Sn={1,2,…,n}的一個子集稱為交替的,如果按上升次序列出其元素時,排列方式為奇、偶、奇、偶、…….例如{1,4,7,8}和{3,4,11}都是,而{2,3,4,5}則不是.令gn表示交替子集的數(shù)目(其中包括空集),證明

且有g(shù)n=Fn+2.

證顯然,g1=2,對應(yīng)S1的交替子集為?和{1}.g2=3,對應(yīng)S2的交替子集為?、{1}、{1,2}.

將Sn

的所有子集分為兩部分:

(1)Sn-1={1,2,…,n-1}的所有子集;

(2)Sn-1的每一個子集加入元素n后所得子集.

例如,n=4,S4={1,2,3,4}的所有子集劃分為兩類,即

(1)?、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3};

(2){4}、{1,4}、{2,4}、{3,4}、{1,2,4}、{1,3,4}、{2,3,4}、{1,2,3,4}.

【例3.4.4】(棋盤的(完全)覆蓋問題)本例的棋盤覆蓋是指用規(guī)格為1×2的骨牌覆蓋p×q的方格棋盤,要求每塊骨牌恰好蓋住盤上的相鄰兩格.所謂完全覆蓋,是指對棋盤的一種滿覆蓋(即盤上所有格子都被覆蓋),而且骨牌不互相重疊.容易看出,一定存在對2×n棋盤的完全覆蓋.現(xiàn)在的問題是,究竟有多少種不同的完全覆蓋方案?

解設(shè)所求方案數(shù)為gn.那么,對圖3.4.2最左面的四格有且僅有兩種可能的覆蓋方式:

(1)一塊骨牌豎著放,覆蓋最左面的兩格11和21,則整個棋盤的這種完全覆蓋方式與2×(n-1)棋盤的完全覆蓋一一對應(yīng),共有g(shù)n-1種方案;

(2)一塊骨牌橫著放,覆蓋第一行的格子11和12,由于是完全覆蓋,因此第二行最左面的兩格21和22也一定被同一塊骨牌覆蓋.于是整個棋盤的這種完全覆蓋方式與2×(n-2)棋盤的完全覆蓋數(shù)相等,有g(shù)n-2種方案.

由加法原理,本例的定解問題為

所以圖3.4.22×n棋盤

3.4.2Stirling數(shù)列

下階乘函數(shù)

在組合分析和有限差分學(xué)中的地位,如同冪函數(shù)xn在數(shù)學(xué)分析中的地位,具有重要的作用,又都是首項系數(shù)為1的特殊的n次多項式,而且可以互相表示.

如:

定義3.4.1設(shè)

則稱S1(n,k)、S2(n,k)分別為第一類和第二類Stirling數(shù).

Striling數(shù)的組合意義:

(1)分配問題:將n個有區(qū)別的球放入m個相同的盒子,要求各盒不空,則不同的放法總數(shù)為S2(n,m);

(2)集合的劃分:將含有n個元素的集合恰好分成m個無序非空子集的所有不同劃分的數(shù)目即S2(n,m).這種劃分也稱為集合的m劃分.

定理3.4.1第一類Stirling數(shù)有如下性質(zhì):

(6)S1(n,k)滿足遞推關(guān)系

定理3.4.2第二類Stirling數(shù)有如下性質(zhì)

證(1)~(3)由組合意義可以看出,將n個球(n>0)放入0個或1個盒子的方案數(shù)分別為0或1,放入n個盒子也只有一種方案,原因在于盒子不空且不加區(qū)別.所以,性質(zhì)(1)~(3)成立.

(4)n個球放入n-1個盒,各盒不空,必有一盒有兩個球.從n個相異的球中選取2個,共有C(n,2)種組合方案.

(5)n個球,2個盒.任取某一球x,其余的n-1個球每個都有兩種可能的放法,即與x同盒或不同盒,故有2n-1種可能.但要排除大家都與x同盒的情形(這時另一盒將空),所以總的放法有2n-1-1種.

(6)從n個球中任選一個記為x,根據(jù)n的情況將x個球放入k個盒的方案分為兩類:①x獨占一盒,其余n-1個球放入另外k-1個盒,由組合意義知此類放法共有S2(n-1,k-1)種;②x不獨占一盒,相當(dāng)于先將其余n-1個球放入k個盒子,且各盒不空,有S2(n-1,k)種放法,然后再將x放入其中某盒,有k種放法.由乘法原理,此類放法共有k·S2(n-1,k)種.

根據(jù)加法法則,即知性質(zhì)(6)成立.利用上述性質(zhì),可得第二類Stirling數(shù)值表(見表3.4.2).

下面不加證明地給出Stirling數(shù)的其它結(jié)論:

【例3.4.6】Stirling數(shù)的另一個重要應(yīng)用就是分配問題:即將n個球(物體)放入k個盒子,其放法的總數(shù)可以分成8種情況分別予以討論(見表3.4.3).

說明當(dāng)然,上述8種情形還不能包括所有的分配模型,如情形1是指放入同一盒中的球是無次序之分的.否則,方案數(shù)應(yīng)為

其次,各種分配方案中并未考慮盒子中最多能放幾個球的問題.否則,對第一種情形,當(dāng)每個盒中最多只能放入一個球時,其分配方案數(shù)就不是kn,而應(yīng)為Pnk.

3.4.3Catalan數(shù)列

滿足遞推關(guān)系

的數(shù)列稱為Catalan數(shù)列.其解為

【例3.4.7】Euler在精確計算對凸n邊形的對角線三角剖分的個數(shù)時,最先得到了這個數(shù)列.其問題是:將凸n邊形用不相交的對角線分成三角形,有多少種不同的分法?例如,五邊形就有五種剖分方案(見圖3.4.3)圖3.4.3凸五邊形的剖分方案

解所謂凸多邊形,是指該多邊形的任意不相鄰兩點的連線都在多邊形內(nèi)部,如圖3.4.4所示.圖3.4.4任意凸多邊形的剖分

值得指出的是,Catalan數(shù)列還滿足某個一階變系數(shù)的線性遞推關(guān)系.下面從另一個角度考察凸n邊形的對角線三角剖分個數(shù),以得到這個線性遞推關(guān)系.

【例3.4.8】設(shè)P=a1a2…an為n個數(shù)的連乘積,保持原來的排列順序,試問有多少種不同的結(jié)合方案(即根據(jù)乘法的結(jié)合律插入n-1對括號,使得每對括號內(nèi)為恰好是兩個因子的乘積.如n=4,P=((a1a2)(a3a4))=((a1(a2a3))a4)=…)?圖3.4.5n=4時連乘積與凸5邊形三角剖分的對應(yīng)關(guān)系圖3.4.5n=4時連乘積與凸5邊形三角剖分的對應(yīng)關(guān)系圖3.4.5n=4時連乘積與凸5邊形三角剖分的對應(yīng)關(guān)系

【例3.4.9】求具有n個結(jié)點的二叉樹的個數(shù).

解二叉樹是一種重要的樹形結(jié)構(gòu).其特點是每個結(jié)點都是一棵子樹的根,而且它至多有兩棵子樹.因此可以歸納定義二叉樹為結(jié)點的有限集合,該集合或者是空集,或者是由一個根(一個特定結(jié)點)及兩個不相交的被稱作這個根的左子樹和右子樹所組成.二叉樹與計算機算法關(guān)系密切,在算法研究中引出了二叉樹的計數(shù)問題,即具有n個結(jié)點的所有結(jié)構(gòu)上不同的二叉樹有多少個?圖3.4.6具有3個結(jié)點的二叉樹

【例3.4.10】證明有n個結(jié)點的所有不同的有序樹的個數(shù)是Cn.

證有序樹是實際應(yīng)用中另一種重要的樹形結(jié)構(gòu).當(dāng)一棵樹中任何一個結(jié)點的諸子樹的相對次序要考慮時,它就是有序樹.眾所周知,任何一個有序樹都可用二叉樹表示.同時注意到,這棵二叉樹的根的右子樹是空二叉樹,故具有n個結(jié)點的有序樹和具有n-1個結(jié)點的二叉樹之間存在一一對應(yīng)的關(guān)系.因此,有n個結(jié)點的有序樹的個數(shù)為bn-1,即Cn.圖3.4.7具有4個結(jié)點的有序樹

例如,有4個結(jié)點的結(jié)構(gòu)不同的有序樹共有C4=5個,如圖3.4.7所示,它們分別與圖3.4.6的有3個結(jié)點的二叉樹一一對應(yīng).

有序樹與二叉樹的對應(yīng)規(guī)則:有序樹的長子樹作二叉樹的左子樹,次子樹作右子樹.參見圖3.4.8.圖3.4.8用二叉樹表示有序樹

【例3.4.11】由n個1和n個0組成的2

位的二進(jìn)制數(shù),要求從左向右掃描,1的累計數(shù)不小于0的累計數(shù),問這樣的二進(jìn)制數(shù)有多少個.

解

解法一設(shè)滿足條件的二進(jìn)制數(shù)有an個.將其視為由字符0和1構(gòu)成的二進(jìn)制串,現(xiàn)分類統(tǒng)計其個數(shù)如下:設(shè)從左向右掃描到第2k位時(1≤k≤n),第一次出現(xiàn)了0的個數(shù)等于1的個數(shù).那么在此之前,掃描到任何一位時,1的個數(shù)總是大于0的個數(shù).例如下面的二進(jìn)制串:

這是因為可以將符合題目要求的串分為前后兩個子串,前子串共2k位,后子串有2(n-k)位.首先,由題目的條件知,后子串也是符合題目要求的二進(jìn)制串,只是其長度為2(n-k),故有an-k個.其次,針對前子串,由其性質(zhì)知,當(dāng)去掉第1位和第2k位時,剩下的2(k-1)位串也符合題目條件,故前子串有ak-1個.由乘法法則,具有此性質(zhì)的串共有ak-1an-k個.而相應(yīng)于不同的k值(k=1,2,…,n),兩類這樣的二進(jìn)制串不可能互相有重復(fù)的情況,故由加法法則,所求的串的個數(shù)為

且有a1=1.另外,觀察上式,可知應(yīng)有a0=1.

參照例3.4.9中關(guān)于數(shù)列{bn}所滿足的遞推關(guān)系的解法,可知

解法二用排列組合的方法求解.詳見本教材的配套書———《<組合數(shù)學(xué)>學(xué)習(xí)指導(dǎo)》中關(guān)于第一章題32的求解過程.

3.5應(yīng)用

【例3.5.2】(錯排問題)n個有序元素的一個排列,若每個元素都不在其原來應(yīng)在的位置,則稱該排列為錯位排列,簡稱錯排.具體地說,如自然數(shù)1,2,…,n本身就是一個由小到大的有序排列,現(xiàn)在打亂順序重排,要求數(shù)i不在第i個位置,就是錯位排列.求所有錯位排列的數(shù)目Dn,就是錯排問題.例如:

n=1,1的錯排數(shù)為D1=0.

n=2,12的錯排為21,錯排數(shù)D2=1.

n=3,123的錯排為312和231,錯排數(shù)D2=2.兩個錯排可以理解為在自然排列123中先將12錯排后得213,再在213中將3分別與1或2互換位置而得.

n=4,錯排情形分為三種(共兩類):

(1)4321,3412,2143:4分別與1,2,3中某一個互換位置,其余兩元素錯排;

(2)4123,3421,3142:4與123的一個錯排312構(gòu)成3124,再將4分別與各數(shù)互換;

(3)4312,2413,2341:針對123的錯排231,方法同(2).

其中(2)、(3)為同一類.由此可以看出產(chǎn)生錯排的一種方法:

針對n個數(shù)1~n的自然順序排列12…n,任取其中一數(shù)i(1≤i≤n),將所有錯排分為兩類:

(1)i與其它某數(shù)互換位置后,其余的n-2個數(shù)錯排,共得(n-1)Dn-2個錯排;

(2)i在原位置不動,其它n-1個數(shù)先錯排,然后i再與其中每一個數(shù)互換位置可得(n-1)Dn-1個錯排.

綜合以上分析得Dn的遞推關(guān)系為

反推可知,D0=1.

用歸納法可以證明,當(dāng)n≥2時,此遞推關(guān)系與例3.3.4中的遞推關(guān)系同解.因此有(見例3.3.4)

當(dāng)n充分大時,可得Dn的非常簡單的近似公式

【例3.5.4】某粒子反應(yīng)器內(nèi)有高能自由粒子、低能自由粒子和核子三種,假設(shè)在每一個時刻,一個高能粒子撞擊一個核子且被吸收引起它放射出3個高能粒子和一個低能粒子,一個低能粒子撞擊核子且被吸收并引起它放出兩個高能粒子和一個低能粒子.設(shè)開始即n=0時刻時,在具有核子的系統(tǒng)里放入一個高能粒子,問第n個時刻時,系統(tǒng)中高能、低能粒子各有多少.

【例3.5.5】核反應(yīng)堆中有α、β兩種粒子,每單位時間,1個α粒子分裂為3個β粒子,1個β粒子分裂為2個β粒子和1個α粒子,假設(shè)t=0時刻,反應(yīng)堆中只有1個α粒子,那么,在t=100時刻,該反應(yīng)堆中α、β粒子各有多少?總數(shù)為多少?

另法就堆內(nèi)總粒子數(shù)而言,由于α粒子和β粒子都是分解為3個粒子,故t=1時刻,共有3個粒子(3個β粒子),t=2時刻共有3×3=32個粒子(3×2β個粒子,3個α粒子),……,到t=n時刻,應(yīng)為3n個粒子.

【例3.5.10】求圖3.5.1所示的n級電路網(wǎng)絡(luò)的等效電阻Rn.圖3.5.1n級電路網(wǎng)絡(luò)

解所謂等效電阻,即用一個電阻Rn取代整個電路,使在兩端點n和n'之間的效果與原電路的一樣,Rn稱為等效電阻,可以看作是由Rn-1等效電阻及最后一級電路串并聯(lián)構(gòu)成的(見圖3.5.2).圖3.5.2等效電阻．

則有

【例3.5.11】(排序算法)據(jù)統(tǒng)計,在計算機的全部運行時間里,幾乎有1/4的時間是用在排序上.因此,尋找高效