1、组合数学2011.11教材与参考书 教材 : R. A. Brualdi, 组合数学 , 机械工业出版社 (中译第 4版 ) 参考 : 卢开澄 , 组合数学 (第 4版 ),清华大学出版社课程特点 研究内容：离散结构的存在、 计数 、分析和优化。 技巧的应用来自于经验的积累，所以解决的组合数学问题越多，那么能够解决下一个组合数学问题的可能性就越大。 结合数论思考问题课程内容简介 鸽巢原理 (例 Ramsey定理 ) 排列组合 容斥原理 (例 Euler函数 ) 递推关系与生成函数 二分图匹配 组合设计 Polya计数定理 (例 : 圆排列 ) 例 :棋盘的完美覆盖mn棋盘 : m行 n列方格
2、, b-牌 :1行 b个的方格条mn棋盘被 b-牌的一个 完美覆盖 是b-牌在棋盘上的一个排列 , 满足 :(1) 每个格子恰好只被一张牌覆盖 ;(2) 每条 b-牌覆盖 b个方格 .定理 : mn棋盘有 b-牌的完美覆盖 b|m或 b|n.34棋盘66棋盘有 4-牌的完美覆盖吗 ?有 2-牌的完美覆盖 .棋盘覆盖及其变化1 2 3 4 1 24 1 2 3 4 13 4 1 2 3 42 3 4 1 2 31 2 3 4 1 24 1 2 3 4 166棋盘用 1,2,3,4如图填数， 4牌在任何位置都覆盖 1,2,3,4，去掉成组的 1234, 多余1124。所以 66棋盘不能用 4牌完美
3、覆盖。完美覆盖变化 : 带禁止方格 , 用多米诺牌 (2-牌 )覆盖44棋盘去掉 2格用多米诺牌 (2-牌 )覆盖45棋盘去掉 4格用多米诺牌覆盖 转化为二分图 , 应用二分图匹配算法 . 2n棋盘用 2-牌覆盖有多少种方案 ? 32n棋盘用 2-牌覆盖有多少种方案 ?例 :Nim取子游戏设有 k1堆硬币 ,各堆分别含有 n1,n2,n k枚硬币 .游戏规则 :(1)两游戏人交替取子 ;(2)每人在一次取子时只能取一堆中的硬币 ,取至少一枚 ,至多全堆硬币 ;(3)所有堆都变成空堆时 , 游戏结束 ,最后取子的人获胜 .例 1. (100, 389)例 2. (7, 8, 15)游戏人 I有必
4、胜策略游戏人 II有必胜策略平衡态设有游戏 (n1,n2,n k), 且各数的二进制展开是ni=aisai(s-1)a i1, i=1,2,k若 a11+a21+a k1 (各数第 1位之和 ),a1s+a2s+a ks (各数第 s位之和 )都是偶数 , 则称游戏处于平衡态 . (7,8,15): (100,389):(7,12,13):平衡态非平衡态非平衡态平衡态与非平衡态的转化n1 = a1s a1(s-1) a 11n2 = a2s a2(s-1) a 21nk = aks ak(s-1) a k1 Label = cs c(s-1) c 1(7,8,15):平衡态(100,389):非平衡态(7,8,13):非平衡态 游戏终止时是平衡态 平衡态不能经一次取子达到平衡态 非平衡态可经一次取子达到平衡态 (?)
