4.4筛法原理应用_第1页
4.4筛法原理应用_第2页
4.4筛法原理应用_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

4.4筛法原理应用筛法公式在初等数论中有很多应用，下面给出一些有关因式分解的定理。设x为实数，[x]表示小于或等于x的最大整数。例如[2.8]=2,[3.4]=3等。定理4.5设n为正整数。为小于n的正整数，且，则使得，且的正整数k的个数为证明令S是n个正整数1,2,…,n的集合，性质P(i)是指S中元素能被除尽。也就是说表示S中能被除尽的元素个数，因而，由于表示S中能被整除的元素个数，因而表示能被整除的元素个数，因而由筛法公式如果n为正整数，欧拉函数表示与n互质（比n小）的正整数个数，即满足0<k<n,(k,n)=1的元素k的个数。由上述定理可得以下推论。推论设n为正整数，则这里p取遍n的所有素数因子。证明由定理4.5,把n提出来后，括号里的式子与相同。最后我们利用筛法公式计算“积和式”（permanent）.设m行n列矩阵为定义A的积和式为这里取遍1,2,…,n的所有排列[共有n(n-1)…（n-m+1）]项。所有项都是正号（这与行列式不同）。现在我们设Ar是A中有r个列用0代替所得的矩阵；S（Ar）表示矩阵Ar的每一行元素和的乘积，即第一行的和第二行的和…第m行的和；的和（即取Ar的所有可能选择）。现在计算当n=m时，矩阵A的积和式时也不难计算）。设S的所有下列元素乘积的和为（4-4-1）其中i1,i2,…,in是1,2,…,n的任意可重复排列（共nn项）。显然，S(A)是这nn个元素的和。现在设P(1)表示这样的性质：在（4-4-1）式中i1,i2,…,in这n个数码中没有1出现；…P(i)表示这样的性质：在（4-4-1）式中i1,i2,…,in中没有数码i出现;P(i)P(j)表示i1,i2,…,in中没有数码i与j出现。具有一个性质P(i)的元素显然是中的一项，具有两个性质P(i)P(j)的元素是中的一项，…，per(A)显然是S中没有任何性质P(i)的元素和，由筛法原理得如果A中元素全为1，则当矩阵A的对角线元素全为0，其余元素全为1时=扰乱排列总数因为在乘积（否则乘积为0）积和式在初等排列组合中有很多应用。例如，计算矩阵的积和式per(A),实际上是：排列i1,i2,i3中i1不能取3的排列数。Per(A)=4.而矩阵的积和式per(B)却是排列i1,i2,i3中i1不能取3，i2不能取1的排列数。per(B)=3练习4.40011100111100111100

人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论