中国留学之家从数列递推到N球配对问题

踏雪无痕 - 2008-6-19 9:56:00

本篇给出求简单递推数列通项公式的通用解法，并由此思路解一个老题
以下记A（N）为数列第N项
1、已知A1=1，A（N）=2A（N-1）+1，求数列通项公式
解：由题意，A（N）+1=2[A（N-1）+1]
即 A（N）+1是以2为首项，2为公比的等比数列
因此 A(N)+1=2^N
数列通项公式为 A(N)=2^N-1
2、通用算法
已知A1=M，A（N）=P*A（N-1）+Q，P《》1，求数列通项公式
解：设 A（N）+X=P*[A（N-1）+X]
解得 X=Q/（P-1）
因此 A（N）+Q/（P-1）是以A1+Q/（P-1）为首项，P为公比的等比数列
由此可算出A（N）通项公式
3、已知A1和A2， A（N）=P*A（N-1）+Q*A（N-2），求数列通项公式
解题思路：设 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、现在用上面的思路来解决一个著名的问题：
N个球和N个盒子分别编号从1到N，N个球各放入一个盒子，求没有球与盒子编号相同的放法总数。
解：设A（N）为球数为N时满足条件的放法（以下称无配对放法）总数，
易知A1=0，A2=1
当N》2时，一号球共有N-1种放法，假设1号球放入X号盒子
在剩下的N-1个球和N-1个盒子中，如X号球正好放入1号盒子，
问题等价于有N-2个球的无配对放法，放法总数为：A（N-2）
在剩下的N-1个球和N-1个盒子中，如X号球没有放入1号盒子，
则可以把X号球看作1号球，问题等价于有N-1个球的无配对放法，
放法总数为：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）]
按等比数列得出： A（N）-NA（N-1）=（-1）^N
上式除以N！得出：
A（N） A（N-1）（-1）^N
------- = ---------------- + -----------------
N！（N-1）！ N！
把 A（N）/N！当作新的数列，把（-1）^N/N！也作为一个数列
则 A（N）等于数列（-1）^N/N！从第二项到第N项的和再乘以N
另外可得出：
N球恰有K球与盒子配对的放法总数为： C（N，K）*A（N-K）
文章二
数列之无敌解法
详细研读本篇数列解法和例题，可快速解决任何MBA数列问题。
基本数列是等差数列和等比数列
一、等差数列
一个等差数列由两个因素确定：首项a1和公差d.
得知以下任何一项，就可以确定一个等差数列（即求出数列的通项公式）：
1、首项a1和公差d
2、数列前n项和s(n),因为s(1)=a1,s(n)-s(n-1)=a(n)
3、任意两项a(n)和a(m)，n,m为已知数
等差数列的性质：
1、前N项和为N的二次函数（d不为0时）
2、a(m)-a(n)=(m-n)*d
3、正整数m、n、p为等差数列时，a(m)、a(n)、a(p)也是等差数列
例题1：已知a(5)=8,a(9)=16,求a(25)
解： a(9)-a(5)=4*d=16-8=8
a(25)-a(5)=20*d=5*4*d=40
a(25)=48
例题2：已知a(6)=13,a(9)=19,求a(12)
解：a(6)、a(9)、a(12)成等差数列
a(12)-a(9)=a(9)-a(6)
a(12)=2*a(9)-a(6)=25
二、等比数列
一个等比数列由两个因素确定：首项a1和公差d.
得知以下任何一项，就可以确定一个等比数列（即求出数列的通项公式）：
1、首项a1和公比r
2、数列前n项和s(n),因为s(1)=a1,s(n)-s(n-1)=a(n)
3、任意两项a(n)和a(m)，n,m为已知数
等比数列的性质：
1、a(m)/a(n)=r^(m-n)
2、正整数m、n、p为等差数列时，a(m)、a(n)、a(p)是等比数列
3、等比数列的连续m项和也是等比数列
即b(n)=a(n)+a(n+1)+...+a(n+m-1)构成的数列是等比数列。
三、数列的前N项和与逐项差
1、如果数列的通项公式是关于N的多项式，最高次数为P，则数列的前N项和是关于N的多项式，最高次数为P+1。
（这与积分很相似）
2、逐项差就是数列相邻两项的差组成的数列。
如果数列的通项公式是关于N的多项式，最高次数为P，则数列的逐项差的通项公式是关于N的多项式，最高次数为P-1。
（这与微分很相似）
例子：
1，16，81，256，625，1296 （a(n)=n^4)
15,65,175,369,671
50,110,194,302
60,84,108
24,24
从上例看出，四次数列经过四次逐项差后变成常数数列。
等比数列的逐项差还是等比数列
四、已知数列通项公式A（N），求数列的前N项和S（N）。
这个问题等价于求S（N）的通项公式，而S（N）=S（N-1）+A（N），这就成为递推数列的问题。
解法是寻找一个数列B（N），
使S（N）+B（N）=S（N-1）+B（N-1）
从而S（N）=A（1）+B（1）-B（N）
猜想B（N）的方法：把A（N）当作函数求积分，对得出的函数形式设待定系数，利用B（N）-B（N-1）=-A（N）求出待定系数。
例题1：求S（N）=2+2*2^2+3*2^3+...+N*2^N
解：S（N）=S（N-1）+N*2^N
N*2^N积分得（N*LN2-1）*2^N/(LN2)^2
因此设B（N）=（PN+Q)*2^N
则（PN+Q)*2^N-[P（N-1）+Q)*2^（N-1）=-N*2^N
（P*N+P+Q）/2*2^N=-N*2^N
因为上式是恒等式，所以P=-2，Q=2
B（N）=（-2N+2)*2^N
A（1）=2，B（1）=0
因此：S（N）=A（1）+B（1）-B（N）
=（2N-2）*2^N+2

例题2：A（N）=N*（N+1）*（N+2），求S（N）
解法1：S（N）为N的四次多项式，
设：S（N）=A*N^4+B*N^3+C*N^2+D*N+E
利用S（N）-S（N-1）=N*（N+1）*（N+2）
解出A、B、C、D、E
解法2：
S（N）/3！=C（3，3）+C（4，3）+...C（N+2，3）
=C（N+3，4）
S（N）=N*（N+1）*（N+2）*（N+3）/4
文章三
M个球放入N个盒子的放法
N个盒子编号为1到N，把M个相同的球放入这N个不相同的盒子，问共有多少种放法。
很多题目都与这个问题相关, 我把公式贴在这里.一般规律，M个球任意放入N个盒子，放法总数为：C（M+N-1，N-1）思路：把M+N-1个球中任意N-1个球变成隔断，就等于把M个球分成了N组，即装入N个盒子。所以放法总数为：C（M+N-1，N-1）这里无论M和N哪个大,公式都成立.如果要求每个盒子至少有一个球,则要求M>=N先把N个球装入N个盒子,再把M-N个球任意装入N个盒子,放法总数为：C（M-1，N-1）

另一种思考方法：
假设我们把M个球用细线连成一排，再用N-1把刀去砍断细线，就可以把M个球按顺序分为N组。则M个球装入N个盒子的每一种装法都对应一种砍线的方法。而砍线的方法等于M个球与N-1把刀的排列方式（如两把刀排在一起，就表示相应的盒子里球数为0）。所以方法总数为C（M+N-1，N-1）
文章四
重要极限X->0,LIM(1+X)^(1/X)=e的运用
利用X->0,LIM(1+X)^(1/X)=e求极限的题型一般为：
求X-》0（或X-》A，X-》无穷大）时，LIM[1+F（X）]^G（X）
无论F（X）、G（X）形式多复杂，都有两个共同点：X-》0时，F（X）-》0和G（X）-》无穷大，这种情况都能运用重要极限的公式。
由于X-》0时，F（X）-》0，于是LIM[1+F（X）]^[1/F（X）]=E
LIM[1+F（X）]^G（X）
=LIM[1+F（X）]^[1/F（X）*F（X）*G（X）]
=LIM E^[F（X）*G（X）]
最终归结为求F（X）*G（X）的极限，一般可用罗必达法则解决
文章五
组合数的公式和变换技巧
有朋友给出了两道题：
1、设15000件产品中有1000件次品，从中拿出150件，求得到次品数的期望和方差？
2、设某射手对同一目标射击，直到射中R次为止，记X为使用的射击次数，已知命中率为P，求E（X）、D（X）。
这两题都要用到一些技巧。我先列出几个重要公式，证明过程中提供变换技巧，然后把这两个题目作为例题。
先定义一个符号，用S（K=1，N）F（K）表示函数F（K）从K=1到K=N求和。（我不会用求和的符号）
公式1：
C（M-1，N-1）+C（M-1，N）=C（M，N）
证明：方法1、可直接利用组合数的公式证明
方法2、（更重要的思路）
C（M，N）是从M个物品中任选N个的方法。
从M个物品中任意指定一个。则选出N个的方法中，包含这一个的有C（M-1，N-1）种，不包含这一个的有C（M-1，N）种。
因此，C（M-1，N-1）+C（M-1，N）=C（M，N）

公式2：
S（K=N，M）C（K-1，N-1）=C（M，N）（M》=N）
证明：C（M，N）是从M个物品中任选N个的方法。
从M个物品中任意指定M-N个，并按次序编号为第1到第M-N号，而其余的还有N个。
则选出N个的方法可分类为：
包含1号的有C（M-1，N-1）种；
不包含1号，但包含2号的有C（M-2，N-1）种；
。。。。。。
不包含1到M-K号，但包含M-K+1号的有C（K-1，N-1）种
。。。。。。
不包含1到M-N-1号，但包含M-N号的有C（N，N-1）种
不包含1到M-N号的有C（N，N）种，而C（N，N）=C（N-1，N-1）
由于两种思路都是从M个物品中任选N个的方法，因此
S（K=N，M）C（K-1，N-1）=C（M，N）
公式3：
S（K=0，N）C（P，K）*C（Q，N-K）=C（P+Q，N）（P，Q》=N）
证明：一批产品包含P件正品和Q件次品，则从这批产品中任选N件的选法为C（P+Q，N）。而公式里面的K表示选法中正品数量，
C（P，K）*C（Q，N-K）表示N件产品中有K件正品，N-K件次品的选法。K从0到N变化时，就包含了所有不同正品、次品数的组合。
因此，S（K=0，N）C（P，K）*C（Q，N-K）=C（P+Q，N）
公式4（一种变换技巧）：
S（K=0，N）K*C（M，K）=S（K=0，N-1）M*C（M-1，K）
证明：
S（K=0，N）K*C（M，K）
=S（K=1，N）K*C（M，K）
=S（K=1，N）K*M！/K！/（M-K）！
=S（K=1，N）M*（M-1）！/（K-1）！/（M-K）！
=S（K=1，N）M*C（M-1，K-1）
=S（K=0，N-1）M*C（M-1，K）
公式5（公式4的同种）
S（K=0，N）K*（K-1）*C（M，K）
=S（K=0，N-2）M*（M-1）*C（M-2，K）
证明：（类似上式）
S（K=0，N）K*（K-1）*C（M，K）
=S（K=2，N）K*（K-1）*M！/K！/（M-K）！
=S（K=2，N）M*（M-1）*（M-2）！/（K-2）！/（M-K）！
=S（K=2，N）M*（M-1）*C（M-2，K-2）
=S（K=0，N-2）M*（M-1）*C（M-2，K）
公式4用于求数学期望，公式4、公式5结合起来可用于求方差。

例1、设15000件产品中有1000件次品，从中拿出150件，求得到次品数的期望和方差？
解：（本题利用公式3、4、5）
有K件次品的概率为：
P（K）=C（1000，K）*C（14000，150-K）/C（15000，150）
E（X）
=S（K=0，150）K*C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，149）1000*C（999，K）*（14000，149-K）/C（15000，150）
=1000*C（14999，149）/C（15000，150）
=10
D（X）
=S（K=0，150）（K-10）*（K-10）*C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，150）（K*K-K-19*K+100）*C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，150）K*（K-1）*C（1000，K）*C（14000，150-K）/C（15000，150）
-19*S（K=0，150）K*C（1000，K）*C（14000，150-K）/C（15000，150）
+100*S（K=0，150）C（1000，K）*C（14000，150-K）/C（15000，150）
=S（K=0，148）1000*999*C（998，K）*C（14000，148-K）/C（15000，150）
-19*S（K=0，149）*1000*C（999，K）*C（14000，149-K）/C（15000，150）
+100*S（K=0，150）C（1000，K）*C（14000，150-K）/C（15000，150）
=1000*999*C（14998，148）/C（15000，150）
-19*1000*C（14999，149）/C（15000，150）+100
=138600/14999
=9.240616041
此题推广形式为：
设M件产品中有P件次品，从中拿出N件（N《=P），求得到次品数的期望和方差？
E（X）=P*N/M
D（X）=P*（P-1）*C（M-2，N-2）/C（M，N）
+（1-2*P*N/M）*P*C（M-2，N-2）/C（M，N）+（P*N/M）^2

例2、设某射手对同一目标射击，直到射中R次为止，记X为使用的射击次数，已知命中率为P，求E（X）、D（X）。
解：射中R次，使用的射击次数为K次(K>=R)，则前K-1次射中R-1次，第K次射中了，概率为：
P（K）=C（K-1，R-1）*P^R*(1-P)^(K-R)
(以下暂时用W表示无穷大）
射中R次，使用的射击次数可为R次、R+1次...W次
因此S（K=R，W）P（K）=1 （这是概率的特点）
即：S（K=R，W）C（K-1，R-1）*P^R*(1-P)^(K-R)=1
以上证明的式子是另一个公式，即无论P，R是什么数都成立，以下将应用这一公式。
E（X）
=S（K=R，W）K*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）K*（K-1）！/（R-1）！/（K-R）！*P^R*(1-P)^(K-R)
=S（K=R，W）R*K！/R！/（K-R）！*P^R*(1-P)^(K-R)
=S（K=R，W）R*C（K，R）*P^R*(1-P)^(K-R)
=R/P*S（K=R，W）C（K，R）*P^（R+1）*(1-P)^(K-R)
令K1=K+1，R1=R+1，则
E（X）=R/P*S（K1=R1，W）C（K1-1，R1-1）*P^R1*(1-P)^(K1-R1)
利用以上公式得
E（X）=P/R
D（X）
=S（K=R，W）（K-R/P）^2*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）（K*K-2*K*R/P+R*R/P/P）*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）[K*（K+1）-（K+2*K*R/P）+R*R/P/P]*C（K-1，R-1）*P^R*(1-P)^(K-R)
=S（K=R，W）[K*（K+1）*C（K-1，R-1）*P^R*(1-P)^(K-R)
-S（K=R，W）（K+2*K*R/P）*C（K-1，R-1）*P^R*(1-P)^(K-R)
+S（K=R，W）R*R/P/P*C（K-1，R-1）*P^R*(1-P)^(K-R)
=（推导过程同求E（X），略）
=R（R+1）/P/P-（2*R+P）*R/P/P+R*R/P/P
=（1-P）*R/P/P
文章六
I 节约脑力--怎样构造函数，解决有关柯西定理的证明题
先举个例子
设函数F（X）在[A，B]连续，在（A，B）可导，且F（A）=F（B）=0，求证存在S属于（A，B），使
S*F（S）+F‘（S）=0
这类问题都可以化成求S，使F（S）=G（S）*F’（S）的问题，
解决方法是构造函数。
令 G1（X）=-1/G（X）的积分
Q（X）=e^G1(X)
则我们构造出F（X）*Q（X）这个函数，再用柯西定理去解决。
试试看，不用再绞尽脑汁去构造函数。

文章开头的例子的解法：
求S 使S*F（S）+F‘（S）=0
即F（S）=-1/S*F‘（S）
令G（X）=-1/X
则G1（X）=-1/G（X）积分=X积分=X*X/2
则Q(X)=e^(X*X/2)
现在我们构造出函数 P（X）=F（X）*Q（X）=F（X）*e^(X*X/2)
则函数P（X）在[A，B]连续，在（A，B）可导，且P（A）=P（B）=0
根据柯西定理，存在一点S，使P’（S）=0
P‘（X）=F（X）*e^(X*X/2)*X+F’（X）*e^(X*X/2)
=[X*F（X）+F‘（X）]*e^(X*X/2)
存在S使P’（X）=0，
因为e^(X*X/2)《》0
所以S*F（S）+F‘（S）=0

留学之家留学DIY社区