老师勾选的题
第一章 排列组合
,求除尽的整数个数
显然能除尽的整数个数是
数目为
有男运动7名,女运动3名,列队进场,若要求头尾两名运动员必须是男运动员,且女运动员不相邻,问多少种排列方案?
若女运动员排在一起,排在队的头尾两端,又有多少种方案?
只要女运动员排在一起又有多少种方案
5个女生,7个男生组成一个含5个人的小组,要求该小组不允许男生和女生某乙同时参数,请问有多少种方案??
红,黄,蓝,绿4种颜色的旗帜各4面,共16面排成一列,问有多少种不同的方案??
n对夫妻围一圆桌而坐,求每对夫妻相邻而坐的方案数
有12个人分两桌,每桌6人,围成圆桌而坐。有几种方案数,若有12对夫妻平分为两桌,围圆桌有几种方案?
第二问
线性方程的非负整数解的个数为
从中取个作不相邻的组合,其组合数为
从个不同元素中取个作允许重复分组合,其组合数为
另一个证明
另一个证明
第二章 母函数
Fibonacci数列递推关系
,所对应的特征方程
其中
所以
例子2-10
线性常系数非齐次递推关系
整数拆分成1,2,3,m的和,并且允许重复,求其母函数
设1,2,4,8,16,32克的砝码各一枚,问你能称出那些重量
n拆分成重复数不超过2的数之和的拆分数,等于拆分成不被3除尽的数之和的拆分书
n条直线将平面分成多少个域?假定无三线共点,且两两相交
设条椭圆曲线,两两相交与两点,任意3条椭圆曲线不相交于一点,试问这样子的个椭圆将平面分隔成多少个部分??
定理
第2类司特林满足下面的递推式
的组合意义:将n个有标志的球放入m个无区别的盒子,而且无一空盒的方案数
卡特兰数
第三章 容斥原理和鸽巢原理
求这6个字符构成的全排列中不允许出现和的排列数
求不超过120的素数个数
错排问题
即的全排列中每个元素都不在各位置上的排列数
设表示数仍在第位的全排列
求整数解的个数
解:
设为的解,
设为的解,
设为的解,
n对夫妻问题
n对夫妻围圆桌而坐,夫妻不相邻的方案数?
鸽巢原理举例
从的个正整数中任取个,则这个数中至少有一对数,其中一个数是另一个数的倍数
设所取数是
对序列中的每一个数去掉所有2的因子,直至剩下一个奇数为止,例如,去掉的因子,留下了奇数,结果得到由奇数组成的序列
中只有个奇数,故序列中至少有两个是相同的,设
对应地有,
若,则是的倍数
设是正整数的序列,则至少存在整数和,其中,使得是的倍数
构造一个序列,
其中
有两种情况
(1)若有一个是m的倍数,则定理已经得以证明
(2)设在上面的序列没有任何一个是的倍数,则零
其中,假定上面的序列中所有的项都非的倍数,其中无一为0,而且所有的均小于m,不超过的正整数只有个,根据鸽巢原理,其中至少存在一对,满足,即和满足
不妨设
设是3个任意整数,是的任一排列,则至少有一个是偶数
中至少有两个数同为偶数,或同为奇数,不妨假设这两个数为和,且同为奇数,则中至少有一个偶数。至少有一个是奇数
而且有一个和中某一个相等,奇数与奇数之差为偶数,故中至少有一个为偶数。
设是由1和2组成的序列,已知从其任一数开始的顺序10个数的和不超过16,即
则至少存在和,使得
根据假定,有,相互不相同
做序列共200项。其中最大项
因为一共200项,最大值是199,。所以根据鸽巢原理,必有两项相等。而且必是前段中某个项与后段中某一项相等
第四章 Polya定理
用3个红珠子和2个蓝珠子镶嵌在圆环上,试问有多少种方案?
用红,蓝,绿3种颜色的珠子镶上,试问 有多少种不同的方案?
甲烷的4个键任意用链接,有多少种方案?
的结构是一个空间正4面体,原则居于正4面体的中心。正4面体的转动群按转动轴分类:
不动旋转,共有1个循环
以顶点与对面的中心连线为轴,按反时针方向旋转120度。共有8个循环
以正四面体的对对边之中点联线为旋转转180度,共有3个循环
1表示不动循环有1个,表示进行的4着色,上面的4表示有多少个循环,不动旋转中有4个循环,所以写4
正六面体的6个面分别用红,蓝两种颜色着色,问有多少种不同方案?