组合数学 第五章 二项式系数 主要内容： 1. 二项式系数及相关性质 2. 链与反链

Pascal公式 Pascal公式 ：若1 k  n1，则

Pascal公式 证法1:

Pascal公式 证法2 设 S = {a1, a2,…, an}. S 的 k-组合由两部分组成. 1、不包含 an 的k-组合，即{a1, a2,…, an1}的 k-组 合，有 个. 2、包含 an 的k-组合，由{a1, a2,…, an1}的k1-组合 加上 an 得到，有 个. 所以，

二项式定理 二项式定理(the binomial theorem)

证法1: 取 k 个 y，n  k 个 x 相乘得出 xnk y k. 证法2 采用数学归纳法. 二项式定理 证法1: 取 k 个 y，n  k 个 x 相乘得出 xnk y k. 证法2 采用数学归纳法.

一些恒等式

二项式系数的单峰性 若 s0  s1  …  st  st+1  …  sn ， 则称 s0, s1,…,sn 是单峰的. 例如，1, 1；1, 2, 1；1, 3, 3, 1 ；1, 4, 6, 4, 1 都是单峰的.

二项式系数的单峰性 n偶 n奇 unimodality

二项式系数的单峰性 证明: 设 1 k  n

二项式系数的单峰性

牛顿二项式定理 Newton’s binomial theorem

偏序与全序 集合A上的关系: 是AA的一个子集. 偏序: 传递的 自反的 反对称的 关系. 全序: 任意两个元素都可比较关系. 例: (Z, ), (R, ) 全序 (R2, ) 偏序 (N, 整除) 偏序 ( P({1,2,3,4}),  ) 偏序 Ordered set, totally ordered set, patially ordered set

链与反链 定义: 设 ( X,  ) 为有限偏序集, 链是X的全序子集; 反链是X的子集, 其任两元素不可比较. 例: X={1,2,3}, ( P(X),  ) {{1}, {1,2}, {1,2,3}}是链 {{1,2}, {1,3}, {2,3}}是反链 定理: 设S是n元集合, ( P(S),  )的反链最多 包含C(n, n/2)个集合. Chian, antichain

幂集的对称链划分 幂集划分成链 n=1: {1} 链中集合每个比 前趋多1个元素 n=2:   {1}  {1,2} {2} 链中集合每个比 前趋多1个元素 |链头|+|链尾|=n n=1: {1} n=2:   {1}  {1,2} {2} n=3:   {1}  {1,2}  {1,2,3} {2}  {2,3} {3}  {1,3} 设已有n-1阶对称链划分, 如下构造n阶: (1) n-1阶链每条添加集合 (链尾{n}); (2) n-1阶链每条去掉链尾, 链中每个集合加入n.

幂集反链的最多集合数 定理: 设S是n元集合, ( P(S),  )的反链最多 包含C(n, n/2)个集合. 构造S的对称链划分: 链中集合每个比前趋多1个元素 |链头|+|链尾|=n 问题: 这个对称链划分有多少条链? 命题: 设1是链, 2是反链, 则 则 1  2 至多有一个元素.

偏序集的链与反链 令X={1,2,…,10}, 则 ( X, | ) 是偏序集 {4,6,7,9,10}是大小为5的反链 {1,2,4,8}是大小为4的链 ( X, | )的极小元有: 1 ( X, | )的极大元有: 10, 9, 8, 7, 6

两个对偶的定理 定理: 设偏序集(X,)的最大链大小为r, 则X可以划分成r条反链(不能再少). 定理: 设偏序集(X,)的最大反链大小为m, 则X可以划分成m条链(不能再少).

两个对偶的定理 定理: 设偏序集(X,)的最大链大小为r, 则X可以划分成r条反链(不能再少). 证明：(1)反链数r； A1={X中的极小元};X1=X-A1 A2={X1中的极小元};X2=X-A2  An={Xn-1中的极小元};Xn= 存在一个链：a1 a2   an,aiAi 所以n r

两个对偶的定理 定理: 设偏序集(X,)的最大反链大小为m, 则X可以划分成m条链(不能再少). 证明：(1) 链数m； 归纳法：对X中的元素个数n归纳。 n=1，结论成立； 假设n=k时结论成立。 分两种情况讨论： ①存在大小为m的反链A，它既不是X的所有极大元的集合，也不是X的所有极小元的集合。 ②最多存在两个大小为m的反链。所有极大元的集合和所有极小元的集合或两者之一。

两个对偶的定理 A－＝{x:x在X内且对A中某个a, x a} ①存在大小为m的反链A，它既不是X的所有极大元的集合，也不是X的所有极小元的集合。 令A＋＝{x:x在X内且对A中某个a,a x} A－＝{x:x在X内且对A中某个a, x a} 有：| A＋|<|X|,| A－|<|X|, A＋ A－= A,A＋ A－=X A＋可被划分为m个链F1,F2,,Fm, A－可被划分为m个链E1,E2,,Em, 则，E1 F1, E2 F2, , Em Fm为X的一个链划分。

两个对偶的定理 ②最多存在两个大小为m的反链，所有极大元的集合和所有极小元的集合或两者之一。 令x是极小元而y是极大元且x y。 X－{x,y}的一个反链的最大的大小为m-1。 X－{x,y}的m-1个链划分加上{x,y}是X的一个m个链的划分。

作业 第五章 P102: ex5, ex47, ex48