作者:陈引兰; 左可正 期刊:《湖北师范大学学报·哲学社会科学版》 2009年第01期
证明了模格中的维数计算公式,同时给出了分配格中的维数计算公式。由此证明了代数学其他领域中的几个重要的计数公式:组合学中的容斥原理;数论中多个整数的最大公因数与最小公倍数的计算公式;线性代数中线性子空间的和与交的维数计算公式;群论中有限正规子群的积与交的计算公式。从而将这些计数问题统一起来。
容斥原理是组合数学中的一个重要定理和方法。将这一重要原理应用到排列问题中,会给解决错位排列、有禁区排列和圆形排列等问题带来极大的便利。
作者:郑学谦 期刊:《山西师范大学学报·自然科学版》 2017年第01期
超立方体Q_n具有很好的性质,如连通度κ(Q_n)=n,Q_n是Cayley图、边可迁图和点可迁图、具有高度的对称性,这些性质满足了网络设计的大部分要求.即使如此,它并不是各方面拓扑性质都最好的互联网络.近年来人们提出了超立方体的一些变形,如交叉立方体、Mobius立方体和Twisted立方体.在此基础上本文给出了SQ_n立方体的定义,研究了它的结构,并给出了它的邻接矩阵.
作者:刘文芬; 高光普; 张习勇 期刊:《密码学报》 2014年第04期
旋转对称函数可以极大地提高密码算法的运算效率,节省资源开销,因此在密码学与编码理论中有着广泛的应用.关于旋转对称函数的计数问题一直是该领域研究的重点问题.Li等人将旋转对称布尔函数的概念推广到素域GF(p)上,给出了GF(p)上平衡的旋转对称布尔函数个数的下界,并将次数大于3的齐次旋转对称函数的计数问题作为一个公开的难题.本文进一步研究了这个公开问题,将其转化为对极小旋转对称函数的计数,证明了极小旋转对称函数与GF(p)n...
作者:许普乐; 纪允 期刊:《淮南师范学院学报》 2019年第02期
频繁项集的精简表示是数据挖掘领域中一个研究热点,非可推导项集模型利用了容斥原理压缩频繁项集的数量。传统的挖掘算法在挖掘的过程中,存在多次扫描数据库、重复生成候选项集等效率低下的问题。文章提出一种新的算法MNDIBFP,该算法利用利用FP树压缩数据库,同时结合一定的剪枝策略,达到快速挖掘非可推导项集的目的。实验效果证明,该算法在时间消耗和空间消耗均优于传统算法。
夫妻排刮问题是一种特殊的圆排刮计数问题.今考虑n对夫妻和不是夫妻的N男、N女共2(n+N)个人围圆桌而坐,利用容斥原理的一般形式和生成函数,对夫妻排刮问题敞了三个推广,得到了夫妻均不相邻的排刮数、恰有m(0≤m≤n)对夫妻不相邻的排刮数、偶数对夫妻不相邻的排刮数、奇数对夫妻不相邻的排刮数.
作者:朱静萍 期刊:《佛山科学技术学院学报·自然科学版》 2005年第02期
应用容斥原理解决了不含连续数对的一系列排列的计数问题,并将其进行了推广.
(本讲适合高中) 组合问题常用的原理与方法有:极端原理、容斥原理、抽屉原理与平均值原理、算两次、归纳、对应、概率等.本文举例介绍其应用.
作者:王景周; 崔建英 期刊:《中等数学》 2004年第01期
《中学数学研究》2005年第4期文《对一类放球问题的探究》中,对于将“数字填人方格”等放球问题作出推广和证明,是一个成功地运用归纳、猜想、论证的数学思想方法解决问题的范例.本文用组合数学中容斥原理的理论和方法。给出了该问题一般化的、基本的计数公式,由此计数公式很容易地得到了放球问题的递推式及概率等结论,同时也揭示了基本计数公式与这些结论之间的关系.
容斥原理 设Xi(i=1,2,…,n)为有限集,则有:Card(U1≤i≤nXi)=∑1≤i≤nCard(Xi)-∑1≤i<j≤nCard(Xi ∩Xj)+∑1≤i<j<k≤nCard(Xi ∩ Xj ∩ Xk)+…+(-1)n-1Card(∩1≤i<≤nXi) 1 k集元的定义 若Xi中的某一元素同时属于集合X1,…,Xn中的k个集合,则将该元素称为k集元.故集合Xi中的元素可分类为1集元,2集元,…n集元.
作者:李晓东; 张艳硕; 赵耿; 杨腾 期刊:《北京电子科技学院学报》 2018年第03期
欧拉函数在数论中有着广泛的应用,在密码学中,RSA公钥密码体制也是基于欧拉函数的性质设计出来的。本文探索了任意两个数乘积的欧拉函数分解表示。在此基础上,对任意若干个数乘积的欧拉函数进行了分析,利用集合容斥原理给出了基于乘积性质的欧拉函数的扩展形式表示。这种扩展形式在现实应用中具有很高的实用价值。并且借助基于乘积性质的欧拉函数的扩展形式,构造出一种类似RSA的基于大整数分解困难问题的公钥加密及数字签名算法,对...
作者:高飞; 王光兴; 徐雪初 期刊:《小型微型计算机系统》 2005年第03期
提出计算无线通信网络从源点到汇点(ST)可靠性的一个新拓扑公式.该公式中各项和网络的一类特殊子网络一一对应,与相应的Satyanarayanna公式比较,该公式包含更少的项和更少的算术运算.提出一个计算从网络源点到汇点(ST)可靠性算法.这个算法本质上是通过系统地枚举网络的一类特殊子网络而计算其ST可靠性或生成可靠性表达式.由于所需枚举的子网络数量小于相应的Satyanarayanna算法需枚举的子网络数量,因此新算法性能优于Satyanarayann...
文章对高中学生在排列组合问题中出现的常见错误进行分析整理,挖掘出错的深层原因,帮助学生真正理解 解决排列组合问题的思考方式.同时针对常见的两种错误分别给出纠正办法,介绍了容斥原理和分类讨论的思想,帮助学 生解决在排列组合问题中总是算错的疑惑.
作者:唐保祥; 任韩 期刊:《吉首大学学报·自然科学版》 2017年第03期
计算集合S={1,2,…,2 m}中不同时出现i和i+1,j和j+3(其中m∈{1,2,3,…},i∈{1,2,…,2 m-1},j∈{1,3,5,…,2 m-3})的k元组合数f(2 m,k)=f(2(m-1),k)+f(2(m-1),k-1)+f(2(m-2),k-1).利用容斥原理求出集合N={1,2,3,…,n}的元素i和i+1不相邻的n排列数为p(n)=n.+∑n-1
作者:卢金余; 耿玉仙 期刊:《江苏理工学院学报》 2016年第04期
容斥原理实质为求和变换的逆变换或反演。本文主要研究最值、次序统计量、复杂事件计数、复杂事件概率等容斥公式及其推广。通过复杂集合的结构分析和容斥分析,得出一些基本恒等式;另一方面,研究容斥原理在不同学科的应用实例。
作者:崔军 期刊:《新疆广播电视大学学报》 2006年第04期
对容斥原理进行了简要介绍并推广到了一般情形,给出了一般情况下的结论及其证明,同时从计数的角度给出了简单应用,对深入理解容斥原理并掌握其应用是有帮助的.
作者:廖虎 期刊:《西华师范大学学报·哲学社会科学版》 2007年第04期
介绍了容斥原理求计数的基本定理,并给予了证明,在容斥原理应用中推导出求解绝对错位排列和相对禁止位子排列的计数问题的解法。
作者:张建州 期刊:《数学的实践与认识》 2006年第07期
利用Pólya计数理论给出强度1二元正交阵列计数公式.