?k??k?k?k??????????(?1)???0。 ?0??1??k?
定理3.4.1（Mobius反演定理） 设f(n)和g(n)是定义在自然数集N上的两个函数，若对任意正整数n，有
nf(n)??g(d)??g()
dd|nd|n则可将g表示为f的函数：
ng(n)???(d)f()。
dd|n
例1 欧拉函数?(n)满足
?(n)?n?d|n?(d)d,
并由Mobius反演定理可得
nn???(d)???()
dd|nd|n
例2（可重圆排列问题） 求集合S?{1,2,?,m}的n可重圆排列数。
n1d解：T(n)???(d)m。
nd|n
本章小结：
本章介绍了容斥原理的基本定理，共三条。利用这些基本定理，我们解决了错排问题，有禁止模式的排列问题等问题，并讨论了Mobius反演问题。这些都是组合数学中重要且经典的问题。
容斥原理应用的要点在于对所考虑计数的集合中的元素进行恰当的分组，同时必须使得这些分组所产生的子集合，任意两个、三个、?、n个子集合的交都能容易地计数。要想熟练地利用容斥原理解决问题，还需同学们多思考、多作练习。
第4章 递推关系
第一节 递推关系建立
定义4.1.1 给定一个数的序列H(0),H(1),?,H(n),?，若存在整数 ,使当n?n0时，可以用等号（或大于号,小于号）将H(n)与其前面的某些项H(i)(0?i?n)联系起来，这样的式子就叫做递推关系。
例1（Hanoi 塔问题） 现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如下图所示。要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一个立柱上，且不允许大盘压在小盘上。问至少要搬多少次？
汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在
一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去， 庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己 运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏。
例2 在信道上传输由a,b,c三个字母组成的长为n的字符串，若字符串中有两个a连续出现，则信道就不能传输，令表示信道可以传输的长为n的字符串的个数，求满足的递推关系。
解：信道上能够传输的长为n(n?2)的字符串可分成如下四类： （1）最左边字符为b； （2）最左边字符为c；
（3）最左边两个字符为ab； （4）最左边两个字符为ac
如图所示，前两类字符串分别为f(n?1)个，后两类字符串有f(n?2)个。
b
?????? c
?????? a
b c ?????? a ??????
易求得f(1)?3，f(2)?8，从而得 ?f(n)?2f(n?1)?2f(n?2)(n?3), ?f(1)?3,f(2)?8.?
例3 考虑0，1字符串中“010”子串的相继出现问题，例如，在110101010101中，我们说“010”在第5位和第9位出现，而不是在第7位和第11位出现，在整个字符串中“010”共出现两次，计算n位0，1字符串中“010”子串在第n位出现的字符串有多少？
解：设n位0，1字符串中“010” 子串在第n位出现的字符串的个数为f(n)，则有
?f(n)?2n?3?f(n?2)(n?5) ??f(3)?1,f(4)?2
例4 设P平面上n个连通区域的公共交界点，如右图所示。现用k种颜色对其着色，要求有公共边界的相邻区域着以不同的颜色。令表示不同的着色方案数，求它所满足的递推关系。
例5 设X是一具有乘法运算的代数系统，乘法不满足结合律，用xy表示x对y之积。如果
x1,x2,?,xn?X
而且这n个元素依上面列出的顺序所能作出的一切可能的积彼此不同，其个数记为
f(n)，求f(n)满足的递推关系。
第二节 常系数线性齐次递推关系的求解
定义4.2.1 设k是给定的正整数，若数列f(0),f(1),?f(n),? 的相邻k+1项间满足关系
f(n)?c(n)f(n?1)?c(n)f(n?2)???
c(n)f(n?k)?g(n),(4.2.1)对n?k成立，其中ck(n)?0，则称该关系为{f(n)}的k阶线性递推关系。如果
c1(n),c2(n),?,ck(n)都是常数，则称之为k阶常系数线性递推关系。如果g(n)?0，则称之为齐次的。
如果有一个数列代入递推关系（4.2.1），使得其对任何n，k都成立，则称这个数列是递推关系（4.2.1）的解。
常系数线性齐次递推关系的一般形式为：
f(n)?c1f(n?1)?c2f(n?2)???ckf(n?k)定义4.2.2 方程
(n?k,ck?0),(4.2.2)
xk?c1xk?1?c2xk?2???ck?0(4.2.3)
叫做递推关系（4.2.2）的特征方程。它的k个根q1,q2,?,qk（可能有重根）叫做该递推关系的特征根，其中qi,i?1,2,?,k是复数。
引理4.2.1 设q是非零复数，则f(n)?qn是递推关系（4.2.2）的解，当且仅当q是它的特征根。
引理4.2.2 如果h1(n),h2(n)都是递推关系（4.2.2）的解，b1,b2是常数，则
b1h1(n)?b2h2(n)也是递推关系（4.2.2）的解。
定义 4.2.3 如果对于递推关系（4.2.2）的每个解h(n)，都可以选择一组常数
c1?,c2?,?,ck?， 使得
nnh(n)?c1?q1n?c2?q2???ck?qk
nn成立，则称b1q1?b2qn1,b2,?bk 2???bkqk是递推关系（4.2.2）的通解，其中，b为任意常数。
定理 4.2.1 设q1,q2,?,qk是递推关系（4.2.2）的k个互不相等的特征根，则
nn f(n)?b1q1n?b2q2???bkqk是递推关系（4.2.2）的通解。
例1 求解4.1节例2的递推关系
?f(n)?1f(n?1)?2f(n?2), ??f(1)?3,f(2)?8.
例2 核反应堆中有?和?两种粒子，每秒钟内一个?粒子可反应产生三个?粒
子，而一个?粒子又可反应产生一个?粒子和两个?粒子。若在时刻t?0 时反应堆中只有一个?粒子，问t?100秒时反应堆中将有多少个?粒子？多少个
?粒子？共有多少个粒子？
例3 求递推关系
?f(n)?4f(n?1)?4f(n?2), ??f(0)?1,f(1)?3.
定理 4.2.2 设q1,q2,?,qk是递推关系（4.2.2）的全部不同的特征根，其重数分别为e1,e2,?,et(e1?e2???et?k)，那么递推关系（4.2.2）通解为
f(n)?f1(n)?f2(n)???ft(n),
其中f(n)?(bi1?bi2n?bieinei?1)?qin(1?i?t)。
例4 求解递推关系
?f(n)??f(n?1)?3f(n?2)?f(n?3)?2f(n?4), ??f(0)?1,f(1)?0,f(2)?1,f(3)?2.