2016年在職MBA數(shù)學：從數(shù)列遞推到N球配對問題

2016-04-25 16:32 | 太奇MBA網(wǎng)

　　本篇給出求簡單遞推數(shù)列通項公式的通用解法，并由此思路解一個老題

　　以下記A(N)為數(shù)列第N項

　　1、已知A1=1，A(N)=2A(N-1)+1，求數(shù)列通項公式

　　解：由題意，A(N)+1=2[A(N-1)+1]

　　即 A(N)+1是以2為首項，2為公比的等比數(shù)列

　　因此 A(N)+1=2^N

　　數(shù)列通項公式為 A(N)=2^N-1

　　2、通用算法

　　已知A1=M，A(N)=P*A(N-1)+Q，P《》1，求數(shù)列通項公式

　　解：設(shè) A(N)+X=P*[A(N-1)+X]

　　解得 X=Q/(P-1)

　　因此 A(N)+Q/(P-1)是以A1+Q/(P-1)為首項，P為公比的等比數(shù)列

　　由此可算出A(N)通項公式

　　3、已知A1和A2， A(N)=P*A(N-1)+Q*A(N-2)，求數(shù)列通項公式

　　解題思路：設(shè) A(N)+X*A(N-1)=Y*[A(N-1)+X*A(N-2)]

　　代入原式可得出兩組解，對兩組X，Y分別求出

　　A(N)+X*A(N-1)的通項公式

　　再解二元一次方程得出A(N)

　　注：可能只有一組解，但另有解決辦法。

　　4、現(xiàn)在用上面的思路來解決一個著名的問題：

　　N個球和N個盒子分別編號從1到N，N個球各放入一個盒子，求沒有球與盒子編號相同的放法總數(shù)。

　　解：設(shè)A(N)為球數(shù)為N時滿足條件的放法(以下稱無配對放法)總數(shù)，

　　易知A1=0，A2=1

　　當N》2時，一號球共有N-1種放法，假設(shè)1號球放入X號盒子

　　在剩下的N-1個球和N-1個盒子中，如X號球正好放入1號盒子，

　　問題等價于有N-2個球的無配對放法，放法總數(shù)為：A(N-2)

　　在剩下的N-1個球和N-1個盒子中，如X號球沒有放入1號盒子，

　　則可以把X號球看作1號球，問題等價于有N-1個球的無配對放法，

　　放法總數(shù)為：A(N-1)

　　因此有 A(N)=(N-1)*[A(N-1)+A(N-2)]

　　上式可變換為： A(N)-NA(N-1)

　　=-[A(N-1)-(N-1)*A(N-2)]

　　按等比數(shù)列得出： A(N)-NA(N-1)=(-1)^N

　　上式除以N!得出：

　　A(N) A(N-1) (-1)^N

　　------- = ---------------- + -----------------

　　N! (N-1)! N!

　　把 A(N)/N!當作新的數(shù)列， 把(-1)^N/N!也作為一個數(shù)列

　　則 A(N)等于數(shù)列 (-1)^N/N!從第二項到第N項的和再乘以N

　　另外可得出：

　　N球恰有K球與盒子配對的放法總數(shù)為： C(N，K)*A(N-K)