组合数学作业.

2023年12月9日发(作者：湖北高三化学数学试卷及答案)

作业1

1. 设想一个监狱有64个囚室组成，这些囚室排列得象一张8X8的棋盘。所有相邻的囚室之间都有门相通。一个被囚在某个角上囚室中的犯人被告知，如果他能够恰好通过每个囚室一次而到达对角位置上的囚室，他就将被释放。问：该犯人能否得到自由？

2. 构造一个6阶幻方。

3. 证明3阶幻方必然在中心位置有一个5。试推导：恰好存在8个3阶幻方。

4. 各堆大小分别为22，19，14和11的4-堆Nim取子游戏是平衡的还是非平衡的？游戏人I的第一次取子方式是从大小为19的堆中取走6枚硬币，游戏人II的第一次取子方式是什么？

5. 一局游戏在两个游戏人之间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，他可以往该堆中加进1，2，3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人I还是游戏人II能够确保获胜。获胜的策略是什么？

作业2

1． 证明：有理数m/n展开的十进制小数最终是要循环的。

2． 一个学生有37天用来准备考试。根据过去经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排学习时间（假设每天的学习时间都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13个小时。

3． 证明，从边长为2的正方形中任选5个点，它们当中存在2个点，这2点的距离至多为根号2。

4． 有一个100人的聚会。每个人都有偶数个（可能是0个）熟人。证明，在这次聚会上存在3个人有相同个数的熟人。

5． 确定一副牌中（52张）下列类型的一手牌（5张）的数目。

(1) full house（3张一样大小的牌及2张相同点数的另外的牌）

(2) 顺牌（5张点数相连的牌）

(3) 同花（5张一样花色的牌）

(4) 同花顺（5张点数相连的同样花色的牌）

(5) 恰好两个对

(6) 恰好一个对

6． 15人围坐一个圆桌。如果B拒绝挨着A坐，有多少种围坐方式？如果B只拒绝坐在A的右侧，又有多少种围坐方式？

7． 给定8个车，其中5个红车，3个蓝车。

(1) 将8个车放在8X8棋盘上，使没有两个车可以互相攻击的摆放方法有多少？

(2) 将8个车放在12X12棋盘上，使没有两个车可以互相攻击的摆放方法有多少？

作业3

1. 有20根完全相同的棍列成一行，占据20个位置。要从中选出6根。

(1) 有多少种选择？

(2) 如果所选出的棍中没有两根是相连的，那么又有多少种选择？

(3) 如果在每一对所选的棍之间必须至少有两根棍，有多少种选择？

2. 将10罐橘子汁、1罐柠檬汁和1罐酸橙汁分发给4位学生，并要求每位学生至少得到一罐饮料，并且柠檬汁和酸橙汁要分给不同的学生，确定分发的方法数。

3. 证明{1,2,…,n}的排列的逆序的最大个数等于n(n-1)/2。确定具有n(n-1)/2个逆序的唯一的排列。再确定所有那些具有n(n-1)/2-1个逆序的排列。

4. {1,2,...,n}的r组合A的补是{1,2,...,n}的(n-r)组合A’，它由所有不属于A的元素组成。令M=为{1,2,...,n}的r组合的个数和(n-r)组合的个数。证明：如果A1,A2,...,AM是字典序中的r组合，那么A’M,..., A’2,A’1是字典序中(n-r)组合。

5. 用组合学推理证明恒等式kkk1k1k1

（提示：令S是三个互异元素a,b,c的集合，并计算S的某些k组合）

6. 通过对n用归纳法证明，对n是正整数，nk1kkzn(1Z)k01nrnn3n1n2n3|z|1，假设1zk1Zk0|z|1成立

7. 用牛顿二项式定理近似计算30。

8. 现有6个巧克力的面包圈，6个肉桂的面包圈和3个素的面包圈，要配成含12个面包圈的盒装，问有几种装法？

9. 在一次聚会上，7位男士将他们的帽子上交检查。有多少种方法使得这些帽子被返还时分别满足下列条件？

(1) 没有男士收到他自己的帽子；

(2) 至少有一位男士收到他自己的帽子；

(3) 至少有两位男士收到他们自己的帽子。

10. 证明Dn是偶数当且仅当n是奇数。

作业4

1． 确定方程x1+x2+x3+x4=20满足1≤x1≤6, 0≤x2≤7, 4≤x3≤8, 2≤x4≤6的整数解个数。

2． 把6个非攻击型车放到具有下图所示禁止位置的6X6棋盘上的方法数是多少？

X

X

X

X

X

X

X

X

3． 用红、白和蓝色对1Xn棋盘方格涂色。设hn是没有两个涂成红色的方格相邻的着色方法数。求出hn所满足的递推关系，然后找出hn的公式。 4． 求解非齐次递推关系hn=6hn-1-9hn-2+2n h0=1,h1=0

5． 在同一平面上画一个圆及n条直线，每条直线均与其他直线在圆内相交。若没有三条以上直线共点的情形，则这些直线将圆的内部分成几块区域？

6． 利用生成函数求解下列递推关系：

(1) hn=4hn-2, h0=0,h1=1

(2) hn=hn-1+9hn-2-9hn-3, h0=0,h1=1,h2=2

7． 由0，1，2，3组成的长度为n的序列中，含偶数个0的序列个数记为hn，求hn的递推关系。

作业5

1． 令hn表示用红、白、蓝和绿色以下述方式给1Xn棋盘上方格涂色的方法数，其中涂成红色的方格数为偶数，涂成白色的方格数为奇数。确定序列h0,h1,...,hn,...的指数生成函数，并求出hn。

2． 由字母a,b.c,d,e组成的总字母数为n的单词中，要求a与b的个数之和为偶数，问这样的单词有多少个？

3． 在圆上选择2n个等间隔的点。证明将这些点成对连接起来使得所得到的n条线段不相交的方法数等于第n个Catalan数。

4． 序列的一般项hn是n的一个3次多项式。如果其差分表的第0行的前4个数是1，-1，3，10，确定hn，并计算hk的公式。

k0n5． 试证明序列h0,h1,...,hn,...的下列k阶差分的公式为hn(1)kjhnj

kj0kkj6． 证明第二类stirling数满足下列关系

（1）S(n,2)2n11n2

（2）S(n,n1)n1

n2作业6

1． 确定下列每个分拆的共轭分拆

(1) 12=5+4+2+1

(2) 15=6+4+3+1+1

2． 4X5的棋盘，其禁止位置如图所示。

(1) 找出非攻击型车的最多个数，请给出一实例；

(2) 如果用1X2的多米诺骨牌来覆盖，其最大覆盖个数是多少？请给出一实例。

X

X

X

X

X

X

X

3． 证明在Zn的模n运算中没有两个整数有相同的加法逆元

4． 证明n-1在Zn中总有乘法逆元（n≥2）

5． 判断下列参数的区组设计是否存在BIBD

(1) b=v=14,k=r=6,λ=2

(2) v=15,k=5,b=21,r=7