组合数学第二章

组合数学第二章Tag内容描述：<p>1、第二章 递推关系与母函数 组合数学 递推关系 例一.Hanoi问题：这是个组合数学中的 著名问题。N个圆盘依其半径大小，从下而 上套在A柱上，如下图示。每次只允许取一 个移到柱B或C上，而且不允许大盘放在小 盘上方。若要求把柱A上的n个盘移到C柱上 请设计一种方法来，并估计要移动几个盘 次。现在只有A、B、C三根柱子可用。 递推关系 Hanoi问题是个典型的问题，第一步要设 计算法，进而估计它的复杂性，集估计工作量 。 算法：N=2时 第一步先把最上面的一个圆盘套在B上z z第二步把下面的一个圆盘移到C上 最后把B上的圆盘移到C上 到此转移完。</p><p>2、第二章 母函数与递推关系,组合数学,2.1 母函数,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,2.1 母函数,项的系数 中所有的项包括n个元素a1，a2， an中取两个组合的全体；同理项系数包含了从n个元素a1，a2， an中取3个元素组合的全体。以此类推。,2.1 母函数,若令a1=a2= =an=1，在（2-1-1）式中 项系数： 中每一个组合有1个贡献，其他各项以此类推。故有：,2.1 母函数,另一方面：,2.1 母函数,比较等号两端项对应系。</p><p>3、第二章容斥原理和鸽巢原理 1 容斥原理,例 把1,2,n作全排列,计算1不在第一个位置的排列个数 例 1到600中所有整数不能被6整除的个数,在集合S中考虑计算问题 设A在S中的补集为 则： 所以,例 在1,2,n所有排列里, 1不在第一个位置且2不在第二个位置的排列个数 例 1到600中所有整数不能被5、6、8整除的个数,容斥原理,例 在字母M 、A、T、H、I、S、F、U、N的排列中M。</p><p>4、Chapter2 Pigeonhole Principle,4 periods,Roadmap,2.1 鸽巢原理的简单形式 2.2 鸽巢原理的加强形式 2.3 Ramsey定理,Pigeonhole Principle的简单形式,Theorem 1.1 若n+1个物体被放进n个盒子，则至少有一个盒子包含两个或更多的物体； 或n+1个物体用n种颜色涂色，则至少有两个物体的颜色相同。,例1.113。</p><p>5、第二章 母函数与递推关系,组合数学,2.1 母函数,递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如,2.1 母函数,项的系数 中所有的项包括n个元素a1，a2， an中取两个组合的全体；同理项系数包含了从n个元素a1，a2， an中取3个元素组合的全体。以此类推。,2.1 母函。</p>