2025年同等学力离散数学与组合数学---三、填空题：

2025年同等学力离散数学与组合数学三、填空题1A{12345678910}偏序关系R是A的整除关系该偏序包含的有序对个数为27最长链的长度为4最长链的总条数为1,最长反链长度为4最长反链的总条数为80。分析整除关系R{1,1,1,21,3,1,41,5,1,61,7,1,81,9,1,102,2,2,42,6,2,82,10,3,33,6,3,94,4,4,85,5,5,106,6,7,78,8,9,910,10}最长链的长度链中元素个数最多的任意两个元素互相整除。长度为元素个数。{1,2,4,8}最长反链长度反链中元素个数最多即任意两个元素互不整除。根据 Dilworth 定理及集合层数分布最大反链出现在中间层。最长反链的总条数:第一步明确反链条件集合 S⊆A满足∣S∣4对任意 a≠b∈S互不整除第二步把元素按整除层次分类层 0L0{1}层 1素数L1{2,3,5,7}层 2L2{4,6,9,10}层 3L3{8}观察1整除所有数 → 只要包含 1就不可能和任何元素构成反链⇒反链里一定不含 18被 4,2,1 整除 → 若选 8则不能选 2,4L1内部素数之间互不整除本身就是反链L2内部4,6,9,10 之间也互不整除本身也是反链第三步分类枚举所有大小为 4 的反链情况 1全部选自 L1{2,3,5,7}只有 1个集合{2,3,5,7}共 1 条情况 2全部选自 L2{4,6,9,10}只有 1 个集合{4,6,9,10}共 1 条情况 3混合 L1,L2,L3且大小为 4因为总大小 4我们按选几个L1、几个L2、几个{8}来分子情况 3.1选 8选 8⇒不能选 2,4剩余 3 个元素要从L1′{3,5,7},L2′{6,9,10}中取 3 个且互不整除。可行组合{8,3,5,7}{8,3,5,9}{8,3,7,9}{8,5,7,9}{8,3,5,10}{8,3,7,10}{8,5,7,10}{8,3,9,10}{8,5,9,10}{8,7,9,10}共 10 条子情况 3.2不选 8从 L1∪L2中取 4 个设从 L1 取 k 个L2 取 4−k个k1,2,3k1L1 1 个 L23个任意组合都合法共 4×416 条k2L12个 L22个任意组合都合法共 ()×()6×636条k3L13个 L21个任意组合都合法共 ()×44×416条合计16361668 条第四步总和11106880最终结论在 A{1,2,…,10} 的整除偏序集中最长反链大小为 4的总条数 80(2)已知A的子集上的一个划分π{{1}{23}{345}} 则π所对应的等价关系R包含的有序对个数是14分析一、核心知识点集合的划分与等价关系是一一对应的划分中的每个块子集对应等价关系中块内所有元素两两构成的有序对包括自反对 (x,x)。不同块之间的元素不存在等价关系的有序对。二、分步计算1.计算每个块内的有序对数量对于一个大小为 k 的块其内部的有序对总数为 k2每个元素与块内所有元素配对包括自身。块 {1}大小 k1有序对数量 121对应有序对(1,1)块 {2,3}大小 k2有序对数量 224对应有序对(2,2),(2,3),(3,2),(3,3)块 {4,5,6}大小 k3有序对数量 329对应有序对(4,4),(4,5),(4,6),(5,4),(5,5),(5,6),(6,4),(6,5),(6,6)2.总有序对数量将各块的有序对数量相加149143表达式11-3t2的级数展开式中t^3项的系数是(108).分析根据扩展二项式1-x-nk0∞cnk-1kxk1-3t-2k0∞c23-133t3c41⋅27⋅t34*27108