北京航空航天大学
2011－2012 学年 第二学期期末
离 散 数 学3 《组 合 数 学》
班 级______________学 号 _________
姓 名______________成 绩 _________
2012年6月4日
班号 学号 姓名 成绩 《 组 合 数 学 》期末考试卷
注意事项：1、考试时间120分钟、闭卷。
2、第一题的答案直接填写在题目留出的空白，第二题之后，答题写在后面的空白页上，请标明题号。
一、填空题（每空5分，共35分）
(1) 7颗不同颜色珠子做成一条项链，其中有3颗红、黄、绿珠子任意
2个都不能相邻，共能够有 种项链构成样式。 (2) 构造{1,2，…,8}的排列 ，其逆序列是6，6，1，4，
2，1，0，0.
(3) 对于大小为2n的多重集{n⋅a, 1, 2, 3, …, n}, 求它的n-组合数
= 。
(4) 方程 x1+x2+x3+x4=30, 共有 个满足x1≥2，x2≥0，x3≥ -5，
x4≥9的整数解。
(5) 一个厨师会做n种菜品，要想用这n种菜品做成100桌酒席，且任
何一桌酒席的菜品不会完全出现在另一桌上，则n最少为__________。
(6) 设hn是方程e1+e2+…+ek=n的正整数解的个数，序列h0, h1, …, hn, …
的生成函数是_______________。
(7) 令m和n是非负整数m≥n。有m+n个人排成一队进入电影院，电
1
影票为50元，这m+n人中有m个人只有50元纸币，n个人只有100元纸币。售票处采用一个空的售票箱。人们能够排队总有零钱可找的列队方式数为 。
二、证明：证明对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。（共10分）
三、有两台机器A和B以及若干项需要运行的任务，每个任务在一台机器上运行。采用（k: a,b）表示编号k任务可以在机器A的a模式或机器B的b模式运行，每台机器切换模式需要重启一次。当机器初始为关机状态，每台机器有9种不同的模式，需要执行11项任务：(0:0,1)、(1:0,4)、(2:1,2)、(3:1,5)、(4:3,6)、(5:4,7)、(6:4,8)、(7:5,4)、(8:5,8)、(9:6,7)、(10:8,7)时，这11项任务按照一定顺序在2台机器上调度，机器启动的最小次数是多少？（给出求解过程）。（共10分）
四、求多重集{1·a, 2·b, 3·c, 4·d}存在多少种循环排列，对除a以外每种类型的字母，该类型的所有字母不连续出现，即不出现包含bb、ccc、dddd的循环排列（求出最后数值）。（12分）
2
五、确定方程5x1+6x2+x3+x4=2，满足x1≥0, x2≥0, 0≤x3≤4, 0≤x4≤5的整数解个数。（8分）
六、求解初始值为h0=0的递推关系hn=2hn-1-n+2n (n>=1)。（12分）
七、用匹配算法确定图1中二分图的最大匹配，并找出使得|S|=|M|的覆盖S。(共13分) （1）假设M={(x3,y3), (x4,y4), (x5,y5)}，给出计算最大匹配M*过程（需要给出每步二分图标注结果、交错路径γ及匹配Mi）。（10分） （2）给出求解过程（1）得出的最大匹配M*以及使得|S|=|M|覆盖集S。（3分）
1
x1x2x3x4x5x6图1 y1y2y3y4y5y6 3
