组合计数理论种的初等数学问题doc.doc

《组合计数理论种的初等数学问题doc.doc》由会员分享，可在线阅读，更多相关《组合计数理论种的初等数学问题doc.doc（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1组合数学和初等数学组合数学和初等数学 若干选题若干选题华南师范大学数学科学学院华南师范大学数学科学学院 吴吴 康康组合数学的核心内容组合计数理论中有许多问题与初等数学有关系，有些可以认为就是初等数学问题，有些以初等数学的结果为重要基础，继续发展到所谓高等组合学中的内容.本文谨介绍笔者了解到的若干组合计数理论中的有关初等数学的问题.一、一、 有序集组计数问题有序集组计数问题用表示有限集的元素的个数,且；用表示是的子集.AA0 KAKA定义 1 有序集组简称为集组或集组.12(,)()mA AAmA ,m定义 2 （1）若,则称为的子集组12,mA AAA ,12(,)mA AA ,Am或子集组

2、.（2）若,则称12,mA AAA ,12mAAAA为的有序覆盖.12(,)mA AA ,Am（3）若,则称为的以12,mA AAA ,1mAAK12(,)mA AA ,A为核的子集组.Km设为集合的全体子集组的集合，即Am,11,|,mmAAAAA 2称映射为定义在 A 上的集组函数，简称为集组函数或集函数，而:g Am简记为，称为集组的（集函数）值.1(,)mgAA1(,)mg AA1(,)mAA以下令，以记的子集的元素和，1,2, nANn( )BAB.约定( )b BBb( )0. 定义 3 12 种集函数分别命名为（1）长度：；m（2）宽度：；1mAA（3）广度：；1mAA（4）丰度

3、：；1mAA（5）浓度：；1mAA（6）密度：； 1mAA（7）跨度：； 1mAA（8）高度：；1max(,)mAA（9）深度：min；1(,)mAA（10）强度：max； 1(,)mAA（11）烈度：min 1(,)mAA（12）厚度：，为对称差.1mAAAAA我们来研究有限定条件的定义在上的集组函数的求和问题，也称为限nNm定条件的（有序）集组计数问题.例如和式11(,)mnm AANg AA （*）表示对所有满足限定条件的（有序）集组的集函1mnAAN1(,)mAA数的值求和.1(,)mg AA我们重点关注以下几个限定条件： ； 12,mnA AAN3（1） ； 1mnAAN（2）； 1

4、2,mA AA（3）. 12mAAA（4）我们首先探讨，在限定条件的基础上，以下一些集函数12,mnA AAN， 1 111(,)mAA mmg AAxx（5）， 1 211(,)mAA mgAAx（6）， 1 311(,)mAA mgAAx（7）， 1 411(,)mAA mgAAx（8）， 1()() 511(,)mAA mmgAAxx（9）， 1()() 611(,)mAA mgAAx（10）分别产生的计数问题，其中.1,mxxxA定理 1 和式4； （11）1 11111 (1)(1)( , )(,)(1)(1)mAAnn mmmm ng AAxxxx. （12）1 2211 (1)(

5、1)( , )(,)(1)mAAmn mmm ngAAxxx定理 2 和式； （13）1 331 (1)(1)( , )(,)(21)1mAAmn mm ngAAxx. （14）1 441 (1)(1)( , )(,)(21)mAAmn mm ngAAxx定理 3 和式. 1()()2 5511 (1)(1)1( , )(,)(1)(1)(1)mm AAn mmiii im ngAAxxxxx（15）. 1()()2 661 (1)(1)( , )(,)(1) (1)(1)mAAmmnm mm ngAAxmxx（16）定理 4 和式， （17）1 11111 (1)(3)(1)(3)( , )

6、(,)(1)1(1)1mAAnn mmmm ng AAxxxx. （18）1 2211 (1)(3)(1)(3)( , )(,)(1)1mAAnm mmm ngAAxx定理 5 和式， （19） 1 331 (1)(3)(1)(3)0( , )(,)( 1)(21)1mmAAm iin m imm ngAAxxi. （20）1 441 (1)(3)(1)(3)( , )(,)(21)(21)2mAAmnmmn mm ngAAxx5定理 6 和式， 1()()2 5511 (1)(3)(1)(3)1( , )(,)(1)(1)(1) 1mm AAn mmiii im ngAAxxxxx（21）.

7、 1()()2 641 (1)(3)(1)(3)( , )(,)(1)(1)(1) 1mAAnm mm ngAAxxxx（22）以上为文1的主要结果，文2则推导得， （23） (1)(2)( , ),1,2,3,4,5,6iim ng i， （24） (1)(2)(3)( , ),1,2,3,4,5,6iim ng i的全部结果.论文34567分别研究对有序集组产生的集函数施加更多限制条件时的有序集组求和问题，特别是56研究对称差条件下是有序集组求和问题，获得很多有趣的结果.二、二、 关于最小值函数和最大值函数组成的级关于最小值函数和最大值函数组成的级数求和问题数求和问题约定：I：=（ ， ）

8、 ， T：（ ， ） ， ，1ini1tnt:IT11itni ntP：=， Q：= ， I 0：=0， 0，1(1)t(1)nt1tnt1i ni ，110,000:nnIiiii 00: ii 000( ) :1,( )11rxxxxx xxr :11 .rxx xxr61设为的函数，约定 P xx 11111 0,0:,:min:min,nniiI ppnnn IiiFtFttpI Tpiitt :,ppfxFtt定理 1 在适当收敛范围内，有1 11111 11,.11n n pnpnn n nnt tFttFttt ttt 定理 2 101.i p iFTpQp i Q定理 3 01

9、1.nni pn iftttp i t定理 4 1min10,:min!11.rIIrr rr IGa TIaTr a P QQaQ 定理 5 1min10,:min!11.rIIrr IGa TIaTr aP QQaQ 定理 7 min1011.1minI IIaTaPQQ InaQI 2引理 1 设为 的函数，则 P xxxR 111 11 11max,1min, ,. nnk njjn k njjpiipiiiiR 定理 87 111101110:max11. kkikI pjjjj Ik njjk niHTpI TPttp itt 三、三、 关于容斥原理的各种推广及应用关于容斥原理的各

10、种推广及应用设为有限集，映射AAn1,mAAA:,fAR则 1111111 imii jj a AAi mjjmf afAA 这是加权形式（也称为一般形式）的阶容斥原理。m发展方向：1. 元素的隶属；2.“至少” 、 “至多”与刚好；3. 截断型；4. 反问题；5. 其他。四、 关于图的着色（染色）的计数在图论中，用 种颜色给一个有限图的顶点着色，每个k顶点着一种颜色，求着色方法的种数。1. 正常着色 树图 圈图 轮图 二部图 其它2.非正常着色 距离 颜色的限制3 边着色、面着色与混合着色五、 其它问题1. 组合几何计数问题；82. 限位、限距、限邻排列与组合计数问题；3. 数列、数阵的计数

11、问题；4. 路径的计数问题；5. 子集构造计数问题；6. 幻方计数问题；7.方程组解数问题；8 循环数谜解数问题。参考文献：参考文献：1 吴 康,苏文龙,罗海鹏,许晓东.限定条件的有序集组计数（I）J.中学数学研究（广州）,2007,6:43-47.2 吴 康,苏文龙,罗海鹏,许晓东.限定条件的有序集组计数（II）J.中国初等数学研究,2009(1):1-6.3 丁 瑜.限定条件的集函数求和问题D.广州：华南师范大学数学科学学院,2008.4 肖志祥.有序子集系为约束变元的和式及在竞赛的应用D.广州：华南师范大学数学科学学院,2006.5 庄丽纯.集合的对称差运算及其产生的和式D.广州：华南师范大学数学科学学院,2005.6 方金财.对称差条件下的有序集组计数D.广州：华南师范大学数学科学学院,2008.7 郭丹洵 吴 康. 关于交并混合型集组计数问题的研究D.广州：华南师范大学数学科学学院,2009.9