Skip to content

老师勾选的题

第一章 排列组合

,求除尽的整数个数

显然能除尽的整数个数是

数目为


有男运动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个面分别用红,蓝两种颜色着色,问有多少种不同方案?