组合数学总复习

《组合数学总复习》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章:1一一对应的应用、排列、组合、圆周排列排列：n个不同的球取r个放进r个不同的盒子，P(n,r)=n(n-1)…(n-r+1)=n!／(n-r)!组合：n个不同的球去r个放进r个相同的盒子，C(n,r)=n!/[r!(n-r)!]圆周排列：将从n中取r个作圆排列的排列数记作Q(n,r)。Q(n,r)=P(n,r)/r，例1.19：5颗不同的红色珠子，3颗不同的蓝色珠子装在圆板的四周,试问有多少种方案？若蓝色珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？例1.20：5对夫妇出席一宴会，围一圆桌而坐，试问有几种不同的方案？若要

2、求每对夫妻相邻又有多少种方案?2.排列的生成算法、组合的生成算法。排列的生成算法:对于给定的字符集，用有效的方法将所有可能的排列无重复无遗漏地枚举出来。（1）.序数法的概要：1、求出0到n!-1之间各数对应的序列{an-1,an-2,…,a1}m=an-1(n-1)!+an-2(n-2)!+…a2*2!+a1*1!2、由{an-1,an-2,…,a1}确定排列序列p1p2…pnan-1,确定n的位置，an-2确定n-1的位置，………………………a1确定2的位置，剩下的是1的位置。（2）字典序法的概要1、求满足关系式pj

3、j的最大值，设为i,i=max{j︱pj

4、组合：r个无标志的球放进n个有区别的盒子的情况:一个盒子中可放一个，也可以放多个。定理1.2在n个不同的元素中取r个进行组合，若允许重复，则组合数为C(n+r-1,r)。即x1+x2+…+xn=b,n和b都是非负整数，求方程的非负整数的解的个数C(n+b-1,b)不相邻的组合：定理1.4从{1,2,…,n}中取r个作不相邻的组合，其组合数为C(n-r+1,r)。4、路径数问题。1、路径数问题：如图从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，问有多少条路径；1.22(P64)求图1.22中从O到P的路径数

5、(a)必须经过A点；(b)必须过道路AB(c)必须过A和C(d)道路AB封锁第二章:1、母函数在组合中的应用例2-3：有红球两个，白球、黄球各一个，试求有多少种不同的组合方案，假设两个红球没有区别。例2-5：求由20个水果组成一袋的可能组合，水果有苹果、香蕉、橘子和梨，其中在每个袋子中苹果数是偶数，香蕉数是5的倍数，橘子数最多是4个，而梨的个数是0和1。在整数的分拆中的应用正整数n的拆分，相当于把n个无区别的球放进n个无区别的盒子，盒子中允许放一个以上的球，也允许空着。求正整数n拆分成1,2,…m的和，并允许重复的拆分数。=展开式中x

6、n项的系数就是要求的拆分数。求正整数n拆分成1,2,…m的和，不允许重复的拆分数。不加1即可。例1求4的拆分数例2求1角、2角、3角的邮票可贴出不同数值邮资的方案数的母函数。例1若有1克、2克、3克、4克的砝码各一枚，问能称出几种可能的重量。2、指数型母函数在排列中的应用。例4求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。（用指数型母函数求解）例4求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。（用递推关系求解）例5用红绿蓝三

7、种颜色去涂1´n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。3、递推关系1．线性常系数齐次递推关系：如果序列{an}满足an+c1an-1+c2an-2+…+ckan-k=0n≥k母函数为：G(x)=a0+a1x+a2x2+…特征多项式C(X)=0的根r1和r2：（1）r1≠r2，实根（2）r1≠r2，复根（3）r1=r2例1：现有n级台阶，一个人上台阶，他只能一次跨一个台阶，也可以一次跨两个台阶，问到n级台阶，共有多少种不同的走法：例2：某人有n元钱，一次可买1元的矿泉水，也可以买2元的（啤酒、方便面）的一

8、种，直到所有的钱花完为止(买东西的顺序不同，也算不同方案)，求n元钱正好花完的买法方案数。例3.令n等于由一些0，1和2组成的长为n的字符串，但0和1从不相邻(00,01,10,11)，求这样的n位符号串的数目。2．非齐