主要内容1.二项式系数及相关性质2.链与反链.ppt

《主要内容1.二项式系数及相关性质2.链与反链.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、主要内容：1.二项式系数及相关性质2.链与反链组合数学第五章二项式系数1Pascal公式Pascal公式：若1kn1，则证法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得到，有个.所以，Pascal公式二项式定理二项式定理(thebinomialtheorem)证法1:取k个y，nk个x相乘得出xnkyk.证

2、法2采用数学归纳法.二项式定理一些恒等式例如，1,1；1,2,1；1,3,3,1；1,4,6,4,1都是单峰的.若s0s1…stst+1…sn，则称s0,s1,…,sn是单峰的.二项式系数的单峰性二项式系数的单峰性n偶n奇证明:设1kn二项式系数的单峰性二项式系数的单峰性牛顿二项式定理偏序与全序集合A上的关系:是AA的一个子集.偏序:传递的自反的反对称的关系.全序:任意两个元素都可比较关系.例:(Z,),(R,)全序(R2,)偏序(N,整除)偏序(P({1,2,3,4}),)偏序链与

3、反链定义:设(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)个集合.幂集的对称链划分n=1:{1}n=2:{1}{1,2}{2}n=3:{1}{1,2}{1,2,3}{2}{2,3}{3}{1,3}幂集划分成链链中集合每个比前趋多1个元素

4、链头

5、+

6、链尾

7、=n设

8、已有n-1阶对称链划分,如下构造n阶:(1)n-1阶链每条添加集合(链尾{n});(2)n-1阶链每条去掉链尾,链中每个集合加入n.幂集反链的最多集合数定理:设S是n元集合,(P(S),)的反链最多包含C(n,n/2)个集合.构造S的对称链划分:含有S的每个子集链中集合每个比前趋多1个元素

9、链头

10、+

11、链尾

12、=n问题:这个对称链划分有多少条链?命题:设1是链,2是反链,则则12至多有一个元素.偏序集的链与反链令X={1,2,…,10},则(X,

13、)是偏序集{4,6,7,9,10}是大小为5的反

14、链{1,2,4,8}是大小为4的链(X,

15、)的极小元有:1(X,

16、)的极大元有:10,9,8,7,6两个对偶的定理定理:设偏序集(X,)的最大链大小为r,则X可以划分成r条反链(不能再少).定理:设偏序集(X,)的最大反链大小为m,则X可以划分成m条链(不能再少).两个对偶的定理定理:设偏序集(X,)的最大链大小为r,则X可以划分成r条反链(不能再少).证明：(1)反链数r；(2)找一个正好有r条反链的划分。A1={X中的极小元};X1=X-A1A2={X1中的极小元};X2=X-A2An={Xn

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

18、它既不是X的所有极大元的集合，也不是X的所有极小元的集合。令A＋＝{x:x在X内且对A中某个a,ax}A－＝{x:x在X内且对A中某个a,xa}有：

19、A＋

20、<

21、X

22、,

23、A－

24、<

25、X

26、,A＋A－=A,A＋A－=XA＋可被划分为m个链F1,F2,,Fm,A－可被划分为m个链E1,E2,,Em,则，E1F1,E2F2,,EmFm为X的一个链划分。两个对偶的定理②最多存在两个大小为m的反链，所有极大元的集合和所有极小元的集合或两者之一。令x是极小元而y是极大元且xy。X－{x,y}的一个反链的最

27、大的大小为m-1。X－{x,y}的m-1个链划分加上{x,y}是X的一个m个链的划分。作业第五章P102:ex5,ex47,ex48