有限半序集的结构分析和Dilworth定理的新证明

在本文中我们讨论了有限半序集的结构分析,并给出了Dilworth定理的两种新证明。在(一)中我们对半序集引进了独立集(最大不可比集)的概念、度数的概念和顶集的概念。得到了关于半序集结构的分层定理(定理1),并应用顶集的性质对半序集的度数用归纳法给出了Dilworth定理的一种新的证明(定理2)。在(二)中根据半序集的独立集的不同情形,将半序集分成两种类型——A型和B型,证明了任何一个半序集均可表成有限个B型半序集的併(定理3),并据此给出了Dilworth定理的另一种新证明。在(三)中我们应用顶集的性质,对Dilworth的原证明给出了一种简化证明。     

无单位间隔的组合数的简易求法

引言 以f(n,k)表示从排列在一条线上的n个元中选取k个无单位间隔的元(即任何两个被选元之间不能恰只隔一个元)的方法数,Konvalina在〔2〕中求得了如下的表达式:     

关于Egorychev《积分表示与组合和的计算》一书的评注

在现代组合分析、图论、算法论、概率、统计学等领域中时常会出现组合和的计算问题。苏联数学家G. P. Egorychev成功地发展了一套应用积分表示及残数计算统一地处理组合和的计算方法。他的著作中的大量例子表明那种统一处理法是十分有效的。他的原著出版于1977年,而英文译本(由H. H. McFaden译出)于1984年由美国数学会出版。我们这篇短文指出,有许多的组合和式(包括一些著名的组合恒等式)是可以十分简捷地应用差分算法和某种一般性的反演方法(或称嵌入技巧)去直接得出的。特别地,以Liskovets问题为例,我们指出用反演方法去求解,比之Egorychev的解法过程,显得更为容易而简短得多。事实上,在一定范围内,反演方法也是一种统一处理法。